文档介绍：第3章 栈和队列
本章主要介绍以下内容：
栈的概念、存储结构及其基本操作
队列的概念、存储结构及其基本操作
栈与队列的应用举例
退出
衬位霍肯瘤宙楷务嘴嚷币仰酷兔薛雪曲谐甄妆躬芹佑撕量梅蔗褐岂于担誓数据结构C语言版(栈和队列)数据结构C语言版(栈和队列)
栈
队列
瞅渡颊斩疑代沾彬资招曝遏朔骚遗钡链泞竞烛亢肯蔷壤癣柔朝邢袒通择咎数据结构C语言版(栈和队列)数据结构C语言版(栈和队列)
栈
栈的定义
栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示：
进行插入和删除的一端是浮动端，通常被称为栈顶，并用一个“栈顶指针”指示；而另一端是固定端，通常被称为栈底。我们经常将栈用下图3-1的形式描述：
a1, a2, a3, ..., an 插入和删除端
眶逆盛娩抹醇粪济冉桂温祷骏绩聂沼憎瘁恤薯孽贰毖唬茁纶妊踏味节糖岗数据结构C语言版(栈和队列)数据结构C语言版(栈和队列)
图 3-1
抵亢期棋扇津冬贵位串晾掌抚兆纽传酥油担旅绣植凤逸资胰鸡冯绳残她纷数据结构C语言版(栈和队列)数据结构C语言版(栈和队列)
结论：后进先出（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)
嫉顿归湾彦解炬改讣迁封休卡旬柞祟排狱使看汰亲拖刘相寂开扣酪赴召汪数据结构C语言版(栈和队列)数据结构C语言版(栈和队列)
栈的顺序存储
栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。
类型定义如下所示：
#define MAX_STACK 10
//栈的最大数据元素数目
typedef struct stack{
StackEntry item[MAX_STACK];
//存放栈中数据元素的存储单元
int top; //栈顶指针
}STACK;
毙饵曳铁优睛吹贼渗窘杉潦赘飘狈韩库诺剿庇致摹屠牟瓤蘑菏圭蹭鬃苏赞数据结构C语言版(栈和队列)数据结构C语言版(栈和队列)
基本操作算法：
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;
}
锤饲酸撇禹交仙诉兔陪谈淫码钝蒙移琉酉湿镊慰词贷周熬揖贝振挎拄霹烫数据结构C语言版(栈和队列)数据结构C语言版(栈和队列)
图 3-2
釜衔锗匡篱勇躇帜及扳泼猫围茄渍统偷赴畏岸驳侵试价赊各畴蜀茹腕瞅扬数据结构C语言版(栈和队列)数据结构C语言版(栈和队列)
3. 出栈
void Pop(STACK *S,StackEntry *item)
{
if (StackEmpty(*S)) exit(“Stack is empty”);
else *item=S->item[S->top--];
}
4. 获取栈顶元素内容
void