文档介绍：第3章栈和队列
本章主要介绍以下内容:
栈的概念、存储结构及其基本操作
队列的概念、存储结构及其基本操作
栈与队列的应用举例
退出
1
栈
队列
2
栈
栈的定义
栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示:
进行插入和删除的一端是浮动端,通常被称为栈顶,并用一个“栈顶指针”指示;而另一端是固定端,通常被称为栈底。我们经常将栈用下图3-1的形式描述:
a1, a2, a3, ..., an 插入和删除端
3
图 3-1
4
结论:后进先出(Last In First Out),简称为LIFO线性表。
举例1:家里吃饭的碗,通常在洗干净后一个一个地落在一起存放,在使用时,若一个一个地拿,一定最先拿走最上面的那只碗,而最后拿出最下面的那只碗。
举例2:在建筑工地上,使用的砖块从底往上一层一层地码放,在使用时,将从最上面一层一层地拿取。
下面我们先给出栈结构的基本操作:
(1)初始化栈 InitStack(S)
(2)入栈 Push(S,item)
(3)出栈 Pop(S,item)
(4)获取栈顶元素内容 GetTop(S,item)
(5)判断栈是否为空 StackEmpty(S)
5
栈的顺序存储
栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素,并用起始端作为栈底。
类型定义如下所示:
#define MAX_STACK 10
//栈的最大数据元素数目
typedef struct stack{
StackEntry item[MAX_STACK];
//存放栈中数据元素的存储单元
int top; //栈顶指针
}STACK;
6
基本操作算法:
1. 初始化栈S
void InItStack(STACK *S)
{ s->top=-1; }
2. 入栈
void Push(STACK *S,StackEntry item)
{
if (S->top==MAX_STACK-1) exit(“Stack is full”);
else S->item[++S->top]=item;
}
7
图 3-2
8
3. 出栈
void Pop(STACK *S,StackEntry *item)
{
if (StackEmpty(*S)) exit(“Stack is empty”);
else *item=S->item[S->top--];
}
4. 获取栈顶元素内容
void GetTop(STACK S,StackEntry *item)
{
if (StackEmpty(S)) exit(“Stack is empty”);
else *item=[];
}
9
5. 判断栈S是否为空
int StackEmpty(STACK S)
{
if (==-1) return TRUE;
else FALSE;
}
结论:由于栈的插入和删除操作具有它的特殊性,所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题,但栈容量难以扩充的弱点仍就没有摆脱。
10