文档介绍：内容提要
栈
顺序栈
链式栈
栈的应用
栈和递归的实现
基本概念
基本问题
队列
顺序队列
链式队列
队列的应用
栈和队列的应用范例
栈
1、定义
栈(Stack):一种后进先出(LIFO)的线性表。
栈顶(top):允许插入和删除的一端
栈底(bottom):不允许插入和删除的一端
栈的主要操作:
建立空栈进栈
出栈判断栈是否空
判断栈是否满获取栈顶元素值
向栈中插入和删除元素,必须在栈的一端进行。因此,栈是操作受限的!
栈(cont’d)
a1
a2
…
an
进栈
出栈
栈顶
栈的示意图
栈的修改是按后进先出
(Last In First Out,简称
LIFO)的原则进行的。
栈之顺序栈
2、顺序栈:用顺序表实现的栈
(1) 顺序栈的数据类型定义:
#define MAXSIZE 50
typedef struct
{
elemtype elem[MAXSIZE];
int top; /*栈顶*/
}SQSTACK;
栈之顺序栈(cont’d)
(2) 顺序栈的基本操作(建栈):
void initstack(SQSTACK *s)
{
stop= -1; /*-1表示空栈*/
}
建立空栈
栈之顺序栈(cont’d)
(3) 顺序栈的基本操作(判断):
int stackempty(SQSTACK s)
{
return == -1;
}
判断栈是否空
栈之顺序栈(cont’d)
(4) 顺序栈的基本操作(入栈):
int push(SQSTACK *s, elemtype e)
{
if(stop==MAXSIZE-1)
return 0; /*栈满,入栈失败*/
stop++;
selem[stop]=e;
return 1;
}
入栈
栈之顺序栈(cont’d)
(5) 顺序栈的基本操作(出栈):
int pop(SQSTACK *s, elemtype *e)
{
if(stop==-1)
return 0; /*栈空,出栈失败*/
*e=selem[stop];
stop--;
return 1;
}
出栈
栈之顺序栈(cont’d)
(6) 顺序栈的基本操作(获取):
int gettop(SQSTACK s,elemtype *e)
{
if(stop==-1)return 0;
*e=selem[stop];
}
获取栈顶值
栈之链式栈
3、链式栈:用链表实现的栈
(1) 链式栈的数据类型定义(与链表相同):
typedef struct node
{
elemtype data;
struct node *next;
}NODE ,*NODEPTR, *LKSTACK;
#define LEN sizeof(NODE)