栈和队列及其应用7 下载本文

栈和队列及其应用

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

栈是一种特殊的表结构,满足先进后出策略(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)