栈和队列

介绍

栈和队列是在软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同

特点

栈和队列在运算上受到了限制：栈是按照“后进先出”的规则进行操作，队列按照“先进先出”的规则进行操作，它们也被称作运算受限的线性表。

栈和队列是限定插入和删除只能在表的端点进行的线性表

栈、队列与一般线性表的区别

栈和队列是一种特殊的（操作受限）线性表

区别：
仅在于运算规则不同

• 一般线性表：
  逻辑结构：一对一
  存储结构：顺序表、链表
  运算规则：随机、顺序存取
• 栈：
  逻辑结构：一对一
  存储结构：顺序栈、链栈
  运算规则：后进先出
• 队列：
  逻辑结构：一对一
  存储结构：顺序队、链队
  运算规则：先进先出

栈——stack

定义：限定仅在表尾进行插入或删除操作的线性表

表尾——栈顶 表头——栈底

不含元素的空表称为空栈
特点：
先进先出（FILO）或后进后出（LIFO）

栈的基本运算

1、栈初始化：	InitStack(&S)初始条件：	栈S不存在操作结果：	构造一个空栈2、判栈空：	StackEmpty(S)初始条件：	栈S已存在操作结果：	若栈S为空栈 则返回TRUE 否则FLASE3、入栈：		Push(&S,e)初始条件：	栈S已存在操作结果：	插入元素e为新的栈顶元素，栈发生变化4、出栈：		Pop(&S,&e)初始条件：	栈S已存在且非空操作结果：删除S的栈顶元素，并用e返回值，栈发生变化5、读栈顶元素：	GetTop(S,&e)		初始条件：	栈S已存在且非空操作结果：	用e返回S的栈顶元素，栈不变化

由于栈还没有定义存储结构类型所以没有具体实现这些功能，具体实现看下文

栈的存储结构

顺序栈

利用顺序存储方式实现的栈称为顺序栈，类似于顺序表的定义，栈中的数据元素用一个预设的足够长度的一维数组来实现

通常0下标端设为栈底，top为栈顶，其初值指向栈底，则空栈是S.top = S.base。入栈时，栈顶指针加一，即S.top++；出栈时，栈顶指针减一即S.top–

非空栈中的栈顶指针始终在栈顶元素的下一个位置。

类似于线性表的顺序映像实现，指向表尾的指针可以作为栈顶指针

• 栈的顺序存储表示

#define STACK_INIT_SIZE  100 
#define STACKINCREMENT   10 typedef struct { SElemType *base;    //栈底指针 SElemType *top;     //栈顶指针 int stacksize;      //当前已分配的存储空间 
}SqStack;

• 初始化栈

Status InitStack(SqStack &S){//构造一个空栈SS.base = (SElemType*)malloc(STACK_INITSIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);     //存储分配失败S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;
}

• 判栈空

Status StackEmpty(SqStack S){if(S.top == S.base)return TRUE;elsereturn FALSE;}

• 求顺序栈的长度

int StackLength(SqStack S){return S.top - S.base;
}

• 清空顺序栈

Status ClearStack(SqStack S){if(S.base)S.top = S.base;return OK; 
}

• 销毁顺序栈

Status DestroyStack(SqStack &S){if(S.base){delete S.base;S.stacksize = 0;S.base = S.top = NULL;}return OK;
}

• 取栈顶元素

Status GeTOP(SqStack S,SELemType &e){if(S.top == S.base)return ERROR;e = *(S.top-1);return OK;
}

• 入栈

Status Push(SqStack &S,SElemType e){if(S.top - S.base >= S.stacksize){//栈满 追加存储空间S.base = (SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);     //存储分配失败S.top = S.base+S.stacksize;S.stack += STACKINCREMENT;}*S.top++ = e;return OK;
}

• 出栈

Status Pop(SqStack &S,SElemType &e) {//若栈不空 则删除S的栈顶元素if(S.top == S.base)return ERROR;e = *--S.top;return OK;
}

注意：

• 对于顺序栈，入栈时，首先判断栈是否已满：S.top - S.base >= S.stacksize,栈满时不能入栈，否则出现空间溢出引起错误
• 出栈和读取栈顶元素操作，先要判断栈是否为空，栈空的条件：S.top = S.base,为空时不能操作否则引起错误。
  通常栈空作为一种控制转移条件

链栈

用链式存储结构实现的栈称为链栈
通常链栈用单链表来表示，因此其节点结构和单链表的结构相同

链栈定义结构如下：

typedef struct LNode{LElemType data;struct LNode *next;}LNode,*LinkStack;
LinkStack S;

运算是受限的单链表，只能在链表头部进行操作，所以没有必要附加头结点。栈顶指针就是链表的头指针

链栈的具体操作：

• 链栈的初始化

Status InitStack(LinkStack &S){S = NULL;return OK;
}

• 判断链栈是否为空

Status StackEmpty(LinkStack S){if(S == NULL)return TRUE;elsereturn FALSE;}

• 取链栈栈顶元素‘

Status GetTop(LinkStack S,LElemType &e){if(!S)return ERROR;elsee = S->data;return OK;}

• 入栈

Status Push_l(LinkStack &S,LElemType e) {//链栈的入栈操作p = new LNode;//p = (LinkStack)malloc(sizeof*(LNode));if(!p)exit(OVERFLOW);p->data = e;p->next = S;S = p;return OK;
}

• 出栈

Status Pop_l(LinkStack &S,LElemType &e) {//链栈的出栈操作if(!S)return ERROR;e = S->data;q = S;S = S->next;delete q; //free(q);return OK;
}

栈的应用

1. 递归的实现
   多个函数嵌套调用的规则：后调用先返回

递归：函数直接或间接的调用自身
实现方法：建立递归工作栈

当一个函数在运行期间调用另一个函数时，在运行该被调用函数之前需要先完成三个任务：

• 将所有的实在参数、返回地址等信息传递给被调用函数保存
• 为被调用函数的局部变量分配存储区
• 将控制转移到被调用函数的入口

从被调用函数返回调用函数之前，应该完成三个任务：

• 保存被调函数的计算结果
• 释放被调函数的数据区
• 依照被调函数保存的返回地址将控制转移到调用函数

案例：汉诺塔问题

问题描述：有A,B,C三个塔座，A上套有n个 直径不同的圆盘，按直径从小到大叠放， 形如宝塔,编号1,2,3……n。要求将n个圆盘 从A移到C，叠放顺序不变，移动过程中遵 循下列原则：

• 每次只能移一个圆盘
• 圆盘可在三个塔座上任意移动
• 任何时刻，每个塔座上不能将大盘压到小盘上

解决方法：

n=1时，直接把圆盘从A移到C
n>1时，先把上面n-1个圆盘从A移到B,然后将n 号盘从A移到C,再将n-1个盘从B移到C。即把求解n 个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题。依次类推，直至转化成只有一个圆盘的Hanoi问题

main(){int m;printf("Input number of disks");scanf("Step:%3d disks ",m);hanoi(m,'A','B','C');;
}void hanoi(int n,char x,char y,char z) {if(n == 1)move(1,x,z);else {hanoi(n-1,x,z,y);move(n,x,z);hanoi(n-1,y,x,z);}}

2. 数制转换
   
   算法步骤：

1.初始化一个空栈S
2.当十进制N非零时，循环执行以下操作：

• 把N与8求余得到的八进制压入栈S
• N更新为N与8的商

3.当栈S非空时，循环执行以下步骤：

• 弹出栈顶元素e
• 输出e

void conversion() {//对于任意一个非负十进制数 打印输出与其值等值的八进制数InitStack(S); //初始化空栈cin>>N; //或 scanf("%d",N);while(N)    //当N非零时 循环｛Push(S,N%8);        //将N与8求得的余数压入栈SN = N/8;            //N更新为N与8的商｝while(!StackEmpty(S)) //当栈S非空时 循环｛Pop(s,e);       //弹出栈顶元素cout<<e;        //输出e或printf("%d",e);｝
}

3. 括号匹配检验

假设在表达式中 （［］（））或［（［］［］）］ 等为正确的格式， ［（］）或（［（））或（（）］) 均为不正确的格式。

算法的设计思想：

1.凡是出现左括号 则进栈
2.凡是出现右括号 首先检查栈是否为空 。如果栈为空则表明该右括号多余；否则和栈顶元素比较：如果匹配则左括号出栈，否则表明不匹配
3.表达式检验结束时：若栈空，则表明表达式中匹配正确；否则表明左括号有余

两种实现：

Status matching() {InitStack(S);flag = 1;cin>>ch;while(ch!='#' && flag) {switch(ch) {case '[' || '(':Push(S,ch); break;case ')':if(!StackEmpty(S) && GeTop(S)='(')Pop(S,x);elseflag = 0;break;case ']':if(!StackEmpty(S) && GeTop(S)='[')Pop(S,x);elseflag = 0;break;}cin>>ch;}if(StackEmpty(S) && flag) return TRUE;else{return FALSE;}}

Status matching(string exp) {int state = 1;while(i<=Length(exp) && state) {switch(exp[i]) {case "(" || "[":Push(S,exp[i]);i++;break;case ")":if(!StackEmpty(S) &&　GeTop(S)="(") {Pop(S,e);i++;}else{state = 0;}break;case "]":if(!StackEmpty(S) &&　GeTop(S)="[") {Pop(S,e);i++;}else{state = 0;}break;}if(StackEmpty(S) && state) return TRUE; else return FALSE;}
}

4. 回文游戏

顺读与逆读字符串一样
算法：

• 读入字符串
• 压入栈
• 原串字符与出栈字符依次比 较，若不等，非回文；若直到栈空都相等，回文。

Status palindrome(char str[],int n) {//回文游戏for(i = 0; i<n; i++) Push(S,str[i]);for(i = 0; i<n; i++){Pop(S,ch);if(str[i] != ch)return FALSE;}return TRUE;
}

5. 迷宫求解
   问题：

这是实验心理学中的一个经 典问题，心理学家把一只老鼠从一 个无顶盖的大盒子的入口处赶进迷 宫。迷宫中设置很多隔壁，对前进 方向形成了多处障碍，心理学家在 迷宫的唯一出口处放置了一块奶酪， 吸引老鼠在迷宫中寻找通路以到达 出口。

求解思想：回溯法

回溯法是一种不断试探且及时纠正错误的搜索 方法。下面的求解过程采用回溯法：
从入口出发，按某一方向向前探索，若能走通 （未走过的），即某处可以到达，则到达新点，否 则试探下一方向; 若所有的方向均没有通路，则沿原路返回前一 点，换下一个方向再继续试探， 直到所有可能的通路都探索到，或找到一条通 路，或无路可走又返回到入口点。

在求解过程中，为了保证在到达某一点后不能 向前继续行走（无路）时，能正确返回前一点以便 继续从下一个方向向前试探，则需要用一个栈保存 所能够到达的每一点的下标及从该点前进的方向。

需要解决的问题：

1.表示迷宫的数据结构
2.试探方向
3.栈的设计
4.防止重复到达某点，避免发生死循环

1/表示迷宫的数据结构：

设迷宫为m行n列，利用maze[m][n]来表示一个迷宫， maze[i][j]=0或1;其中：0表示通路，1表示不通，当从某 点向下试探时，中间点有4个方向可以试探，见下图，而 四个角点有2个方向，其它边缘点有3个方向，为使问题简 单化我们用maze[m+2][n+2]来表示迷宫，而迷宫的四周的 值全部为1。这样做使问题简单了，每个点的试探方向全 部为4，不用再判断当前点的试探方向有几个，同时与迷 宫周围是墙壁这一实际问题相一致

入口坐标为（1，1），出口坐标为（m，n）

//迷宫的定义：
#define m 6     /*迷宫的实际行*/#define n 8		/*迷宫的实际列*/int maze[m+2][n+2];

2/试探方向

在上述表示迷宫的情况下，每个点有4个方向去试探。

如当前点的坐标(x,y)，与其相邻的4个点的坐标都可根 据与该点的相邻方位而得到。因为出 口在（m，n），因此试探顺序规定为：从当前位置 向前试探的方向为从正东沿顺时针方向进行。

为了简化问题，方便的求出新点的坐标，将从正东开 始沿顺时针进行的这4个方向的坐标增量放在一个结 构数组move [ 4 ]中，在move 数组中，每个元素有两 个域组成，x：横坐标增量，y：纵坐标增量。

3/栈的设计

当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个 方向继续试探。

因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一 点到达本点的方向和本通道块在路径中的序号。

栈中元素的类型定义：

typedef struct {int no;     //通道块在路径上的序号PosType seat;       //通道块在迷宫中的坐标位置int d;          //从此通道走向下一通道块的方向}SElemType;// 其中PosType 为结构体
typedef struct {int x;int y;
}PosType;

4/防止重复到达某点 避免发生死循环

一种方法是另外设置一个标志数组mark[m][n]， 它的所有元素都初始化为0，一旦到达了某一点 ( i, j )之后，使mark[i][j] 置1，下次再试探这个位 置时就不能再走了

另一种方法是当到达某点（i, j）后，使maze[i][j] 置-1，以便区别未到达过的点，同样也能起到防 止走重复点的目的。

砖家建议使用后一种方法，因为可以在算法结束前恢复原迷宫

设定当前位置的初值为入口位置
do {若当前位置可通则{将当前的位置插入栈顶;   //纳入路径若该位置是出口位置，则结束;    //求得路径放在栈中否则切换当前位置的东临方块为行的当前位置;}否则，若栈不空且栈顶位置尚有其他方向未经探索，则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一块邻块；若栈不空但栈顶位置的四周均不可通， 则{删去栈顶位置；//从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置，直到找到一个可通的相邻快或出栈至栈空；｝
}while(栈不空)

具体算法：

Status MazePath(MazeType maze,PosTpe move,PosType start,PosType end) {InitStack(S);curpos = start;no = 1;do{if(pass(curse)) {  //当前位置可以通过（未走过的通道块）maze[curse.x][curse.y] = -1; // 留下足迹temp = (no.curse,0);        Push(S,temp);               //加入路径if(curse == end) return TRUE;            //到达终点，出口curpos.x=curpos.x+move[temp.d].x; curpos.y=curpos.y+move[temp.d].y; //下一位置是当前位置的东邻 no++;//探索下一步 }else        //当前位置不能通过{if(!StackEmpty(S)){ Pop(S,temp); while(temp.d==3&&!StackEmpty(S)){ maze[temp.seat.x][temp.seat.y]=0; pop(s,temp);no--;//迷宫中数据还原，并退回一步 }if(temp.d<3){ temp.d++;Push(S,temp);//换下一个方向探索 curpos.x=temp.seat.x+move[temp.d].x; curpos.y=temp.seat.y+move[temp.d].y; //设定当前位置是该方向上的相邻块 }}}}while(!StackEmpty(S));return FALSE;
}

6. 表达式求值
   转换规则及算法：

需要两个栈：对象栈s1和运算符栈s2。当自左至 右扫描表达式的每一个字符时，若当前字符是运 算对象，入对象栈

是运算符时，若这个运算符比栈顶运算符高则入 栈，继续向后处理

若这个运算符比栈顶运算符低则从对象栈出栈两 个运算量，从运算符栈出栈一个运算符进行运算， 并将其运算结果入对象栈，继续处理当前字符， 直到遇到结束符。

运算符的优先关系：

算法步骤：
设定两栈：OPND-----操作数或运算结果OPTR------运算符

①初始化OPTR栈和OPND栈，将表达式起始符“#”压入OPTR栈。
②扫描表达式，读入第一个字符ch，如果表达式没有扫描完毕至“#”或 OPTR的栈顶元素不为“#”时，则循环执行以下操作：

• 若ch不是运算符，则压入OPND栈，读入下一字符ch
• 若ch是运算符，则根据OPTR的栈顶元素和ch的优先级比较结果，做 不同的处理：
  • 若是小于，则ch压入OPTR栈，读入下一字符ch；
  • 若是大于，则弹出OPTR栈顶的运算符，从OPND栈弹出两个数，进行 相应运算，结果压入OPND栈，继续处理当前字符；
  • 若是等于，则OPTR的栈顶元素是“(”且ch是“)”，这时弹出OPTR栈顶 的“(”，相当于括号匹配成功，然后读入下一字符ch

③ OPND栈顶元素即为表达式求值结果，返回此元素。

OperandType  EvaluateExpression( ) { InitStack (OPTR);  Push (OPTR，'#') ; InitStack (OPND);  ch = getchar( ); while (ch!= '#' || GetTop(OPTR)! = '#') { if (! In(ch)){Push(OPND,ch); ch = getchar(); }  // ch不是运算符则进栈 else switch (Precede(GetTop(OPTR),ch)) { //比较优先权 case '<' :    //当前字符ch压入OPTR栈，读入下一字符ch Push(OPTR, ch);  ch = getchar();  break; case '>' :    //弹出OPTR栈顶的运算符运算，并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b);  Pop(OPND, a); Push(OPND, Operate(a, theta, b)); break; case '=' :    //脱括号并接收下一字符 Pop(OPTR,x);    ch = getchar();   break; } // switch 
} // while 
return GetTop(OPND);} // EvaluateExpression

示例：

表达式“3 * 2^（4+2 * 2-１* 3）-5” 求值过程

后缀表达式求值步骤：
1、读入表达式一个字符
2、若是操作数，压入栈，转4
3、若是运算符，从栈中弹出2个数，将运算结果再压入栈
4、若表达式输入完毕，栈顶即表达式值； 若表达式未输入完，转1

为了简单起见，这里的数都是一位整数，运算只含加减乘除且后缀表达式是合法的：

Float Postexpression(char *exp){ InitStack(S);i=0; While (i<length(exp)) {Switch  (exp[i]++) Case “0”： case  ”1”: Case ”2”: Case  ”3”: Case ”4”: Case  ”5”: Case  ”6”:case  ”7”: Case ”8”: Case ”9”:Push(S,exp[i]);break; Case  “+”:Pop(S,op1);Pop(S,op2);res=op1 + op2;Push(S,res);break; Case  ”-”:Pop(S,op1);Pop(S,op2);res=op1 -op2;Push(S,res);break; Case  ”*”:Pop(S,op1);Pop(S,op2);res=op1 *op2;Push(S,res);break; Case  ”/”:Pop(S,op1);Pop(S,op2);res=op1 / op2;Push(S,res);break; } Pop(S,res);return res;
}