配套资源下载
第 3 章 栈和队列
第2章介绍了线性表的概念,从数据结构上看,栈和队列也是线性表,只不过是两种特殊的 线性表。栈只允许在表的一端进行插入或删除操作,而队列只允许在表的一端进行插入操作、在另一端进行删除操作。因而,栈和队列也可以被称为操作受限的线性表。从数据类型的角度来看，栈与队列是与线性表不同的抽象数据结构。
3.1 应用实例
应用实例一 迷宫求解问题
这是实验心理学中的一个经典问题，心理学家用一个无顶盖的大盒子做成“迷宫”从然后把一只老鼠从入口处赶进迷宫。迷宫中设置了很多隔断，对老鼠的前进方向构成多处障碍，在迷宫的唯一出口处放置了一块奶酪,吸引老鼠寻找正确的通路以到达出口。
可以用一个mxn的方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计
一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得到没有通路的结论。
计算机解迷宫时,通常是采用“穷举求解”的方法,即从入口出发,沿某方向向前探索,若能 走通则继续往前走;否则沿原路返回,换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然要用具有后进先出特性的栈来保存从入口到当前位置的路径。
应用实例二“马”踏棋盘问题
将棋子“马”随机地放在国际象棋8x8棋盘Board[8][8]的某个方格中,“马”按走棋规则进 行移动,要求每个方格只进入一次,走遍棋盘上所有的64个方格。编写（非）递归程序,求出“马” 的行走路线,并按求出的行走路线将数字1,2,…,64依次填入一个8x8的方阵并输出。
求解时可采用栈的数据结构,即将“马”的行走顺序压人栈中。每次在多个可走的位置中选 择其中一个进行试探,其余未曾试探过的可走位置必须用适当的结构妥善管理,以备试探失败时 的“回溯”(悔棋)使用。
以上实例的分析与实现将在3.4节详细介绍。
3.2栈
3.2.1 栈的概念及运算
栈(stack)是一种只允许在一端进行插人和删除操作的线性表,它是一
种操作受限的线性表。
在表中允许进行插入和删除的一端称为“栈顶”(top),另一端称为“栈底”(bottom)。
栈的插入操作通常称为“入栈”或“进栈”(push)，
而栈的删除操作则称为“出栈”或“退栈”(pop)。
当栈中无数据元素时,称为“空栈”。
栈具有后进先出的特性,因此又称为“后进先出”(Last In First Out,LIFO)表。
栈的示意图
栈的基本运算有以下几种。 ① InitStack(S) 初始化:初始化一个新的栈。 ② Empy(S )栈的非空判断:若栈S不空,则返回TRUE;否则,返回FALSE。 ③ Push(S.x) 入楼:在栈S的顶部插入元素x,若栈满,则返回FALSE;否则,返回TRUE ④ Pop(S) 出栈:若栈S不空,则返回栈顶元素,并从栈顶中删除该元素;否则,返回空元素 ⑤ GetTop(S) 取栈顶元素:若栈S不空,则返回栈顶元素;否则返回空元素NULL。 ⑥ SetEmpty(S) 置栈空操作:置栈S为空栈。
栈是一种特殊的线性表,因此栈可采用顺序存储结构存储,也可以使用链式存储结构存储。
3.2.2栈的顺序存储结构
1. 顺序栈
利用顺序存储的方式实现的栈称为“顺序栈”。类似于顺序表的定义，栈中的数据元素用一个 预设的足够长度的一维数组来实现:ElemType elem[MAXSIZE]。栈底位置可以设置在数组任 一个端点,而栈顶是随着插人和删除而变化的。用int top来作为栈顶的指针,指明当前栈顶的 位置,同时将elem和top封装在一个结构中。顺序栈的类型描述如下。
#define MAXSIZE<栈最大元素数> typedef struct{ ElemType elem[MAXSIZE]; int top; }SeqStack;
定义一个指向顺序栈的指针:
SeqStack *s;
常将0下标端设为栈底,这样空栈时校顶指针s->top=-1;入栈时,栈顶指针加1,即s->top++；出栈时,栈顶指针减1,即s->top–。
栈的基本操作如下
相关代码请看配套资源
1-顺序栈.c
#include<stdio.h> #include<stdlib.h> int main(){ SeqStack *s=InitStack(); printf("%d",Empty(s));//1 int x1=1; Push(s,x1); int x2=2; Push(s,x2); printf("%d",Empty(s));//0 int x3; Pop(s,&x3); printf("%d",x3);//2 int t=GetTop(s); printf("%d",t);//1 }
运行结果如下
2. 多栈共享邻接空间
栈的共享中最常见的是两栈共享。
假设两个栈共享一维数组elem[MAXSIZE],则可以利用栈的“栈底位置不变,栈顶位置动态变化”特性,两个栈底分别为-1和MAXSIZE,而它们的栈顶都往中间方向延伸。因此,只要整个数组elem[MAXSIZE]未被满,无论哪个栈的人栈都不会发生上溢。
两栈共享的数据结构可定义如下。
typedef struct{ ElemType elem[ MAXSIZE]; int lefttop;//左栈栈顶位置指示器 int righttop;//右栈栈顶位置指示器 } Dupsqstack;
两个栈共享邻接空间的示意图如图3-4所示。左栈入栈时,栈顶指针加1,右栈人栈时,栈顶指针减1。由于两个栈顶均可向中间伸展,互补余缺,因此使得每个栈的最大空间均大于MAXSIZE/2。
为了识别左右栈,必须另外设定标志:
char status; status ='L'; //左栈 status ='R';//右栈
在进行栈操作时,需指定栈号status=L’为左栈,status='R’为右栈;判断栈满的条件如下:
s->lefttop+1=s->righttop;
