栈和队列及其应用

栈和队列通常用来存储程序执行期间产生的一些临时信息。这两种特殊表结构的共同特点是，只做插入和删除，不做查找，而且所有的插入和删除只在端点进行。

栈是一种特殊的表结构，满足先进后出策略（LIFO:last in first out）,栈的插入和删除操作只在同一端点进行。

可以进行插入的端点叫栈顶(top)，另一个端点叫栈底(bottom)。

栈的插入操作又叫进栈(push)或压栈，栈删除操作又叫退栈(pop)或出栈。

栈的结构示意图

注意：进栈和退栈可以不定期地、反复交替进行。

生活中类似栈的应用的例子：装药片的小圆桶，军用子弹卡等。

思考：假设有编号为1，2，3的3辆车，如果按照编号为1，2，3的顺序入栈，那么可能的出栈顺序有几种情况？？？

栈的存储方式： 1. 顺序存储 2. 链式存储

栈的常见操作（顺序存储方式实现） 数组s[M]存储一个栈（M代表栈的容量），top变量指示栈顶指针（下标）。 M=6时：

进栈算法： //宏定义 #define M 6

#define EMPTY -1

void pushs(int s[],int &top) {

int x,k;

cout<<\请输入要进栈的元素值x=\ cin>>x;

if(top==M-1) {

cout<< \栈已经满，进栈失败!\ return; }

//s[++top]; top++; s[top]=x;

cout<

出栈算法：

void pops(int s[],int &top) {

int x,k;

if(top==EMPTY) {

cout<<\栈已经空，退栈失败!\ return ; }

//x=s[top--]; x=s[top]; top--;

cout<<\已退栈顶元素\}

课堂实践：

结合入栈和出栈算法完成入栈、出栈、显示栈的当前元素程序(stack.cpp)。

队又称为队列，是一种特殊的表结构，满足先来先服务策略（FIFO:first in first out）, 队的插入和删除只在两个端点进行。

允许插入的一端交队尾（last）,允许删除的一端叫队头(first)。 队的插入和删除操作分别称为进队和出队。

队结构示意图 生活中队的例子很多：排队上车或购物等。

同栈的结构一样，进队和入队操作是不定期地、反复地进行的。

队的存储方式： 1.顺序存储 2.链式存储

队的常见操作（顺序存储方式实现） （详见板书）

循环队列 （详见板书）

数据结构---栈和队列

栈和队列的基础知识

栈：栈是一种特殊的表结构，满足先进后出策略（LIFO:last in first out）,栈的插入和删除操作只在同一端点进行。

栈的常见操作：入栈、出栈（栈空和栈满的判断）

队：队又称为队列，是一种特殊的表结构，满足先来先服务策略（FIFO:first in first out）, 队的插入和删除只在两个端点进行。 队的常见操作：入队、出队（队空、队满的判断）

数据结构---栈和队列简单应用

文字输入 （enter.cpp）