第3章 限定性线性表—栈和队列
3.1 栈 3.2 队列
1
栈与队列
栈是限定仅在表尾进行插入和删除的线性表。 队列是限定仅在表尾进行插入、在表头进行 删除的线性表。
线性表
Insert(L,i,x) 1≤i≤n+1 Delete(L,i) 1≤i≤n
栈
Insert(S,n+1,x)
Delete(S,n)
栈低 栈顶
18
〖例〗若一个栈的输入序列是1，2，…，n，输出 序列的第一个元素是n，则第i个输出元素是 ______
n-i n-i+1 i n-i-1
top=n-1
n
n-1 …
2
1
top=-1
19
5. 顺序栈上溢的解决方法
当程序中同时使用几个栈时，如何防止栈 的上溢？ 方法一：将栈的容量加到足够大，但这种方法 由于事先难以估计容量，有可能浪费空间。
234
top=1001H
1
top=1000H
输出序列：
17
〖例〗在一个n个单元的顺序栈中，假定以地址高 端(下标为n-1的单元)作为栈底，则向栈中压入一 个元素时，栈顶指针top的变化是______
top 不变 top=n top=top
n-2 …
1 0 top=-1
栈底
进栈
an … a2 a1
出栈
进栈
6
3.1.2 栈的表示和实现
栈在计算机中主要有两种基本的存储结构： 顺序存储结构和链式存储结构。
顺序存储的栈为顺序栈； 链式存储的栈为链栈。
7
一、顺序栈
1、顺序栈的存储结构定义
#define MaxSize 50 StackElementType S[MaxSize];
int IsEmpty(int *S) /*判栈S为空栈时返回值为1，反之为0*/
{ return(top==-1?1:0);
}
12
3） 判栈满
int IsFull(int *S) /*判栈S为满时返回真，否则返回假*/
{ return(top== MaxSize-1?TRUE:FALSE); }
/*用来存放栈中元素的一维数组*/ int top; /*栈顶指针，全局变量*/
8
2、顺序栈中的进栈和出栈图例
top=-1
栈空
top=0 A
top=5 F E D C B A
插入A
栈满
top=2 C B A
栈长度3
9
3. 顺序栈的基本操作特点
1）栈底位置固定在顺序表的低端，即
S[0]----表示栈底元素 2）入栈：top++ ，保存元素； 3）出栈：取元素, top -- ；
4
基本操作：
InitStack(S) 初始化一个空栈 S。 ClearStack (S) 将 S 清为空栈
IsEmpty(S) 若 S 为空栈,则返回true,否则false。
IsFull(S) Push(S, e) Pop(S)
GetTop(S)
若 S 为满栈,则返回true,否则false。
入栈, 插入元素 e 为新的栈顶元素。
栈又被称为后进先出(lifo)的线性表。
ADT Stack {
数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n }
约定an 端为栈顶，a1 端为栈底。
基本操作:
} ADT Stack
共享栈的空间示意为：top[0]和top[1]分别为 两个栈顶指示器 。
Stack：0
M-1
top[0]
top[1]
21
6、两栈共享的数据结构定义
#define M 100 StackElementType S [M]; int top[2]; /*全局变量*/
/*栈为空*/
return(FALSE);
else
{*x= S[top]; top--;
/* 修改栈顶指针 */
return(TRUE);
}
}
15
6） 取栈顶元素
int GetTop（int *S, int *x） { /* 将栈S的栈顶元素取出，放入x所指的单元，但 栈顶指针保持不变 */
if(top==-1) /*栈为空*/ return(FALSE); else {*x = S[top];
出栈, 若 S 非空, 则删除并返回它的栈 顶元素,否则返回' false '。 若 S 非空,则返回它的栈顶元素, 否则 返回' false '。
5
二、进栈、出栈图例
根据栈定义，每次进栈的元素都被 放在原栈顶元素之上而成为新的栈顶， 而每次出栈的总是当前栈中“最新” 的元素，即最后进栈的元素。
出栈 栈顶
队列
Insert(Q,n+1,x)
Delete(Q,1)
栈和队列是两种常用的数据类型
2
3.1 栈
3.1.1 栈的定义 3.1.2 栈的表示和实现 3.1.3 栈的应用举例 3.1.4 栈与递归的实现
3
3.1.1 栈的定义：
一、栈的类型定义
栈是限定仅在表尾进行插入和删除的线性表。
表尾被称为栈顶，表头被称为栈底 。
13
4）进栈
int Push(int * S, int x) { if(top== MaxSize-1) return(FALSE); /*栈已满*/ top++; S[top]=x; return(TRUE); }
14
5）出栈
int Pop(int * S, int *x) { if(top==-1)
方法二：使用两个（或多个）栈共享存储空间 办法。两栈的栈底分别设在给定存储空间的两 端，然后各自向中间伸延，当两栈的栈顶相遇 时才可能发生溢出。
20
利用栈“栈底位置不变，而栈顶位置动态变 化”的特性，为两个栈申请一个共享的一维数 组空间S[M]，将两个栈的栈底分别放在一维 数组的两端，分别是0，M-1。
return(TRUE); } }
16
〖例〗设有一个空栈，栈顶指针为1000H，现有输 入序列为12345，PUSH , PUSH , POP , PUSH , POP , PUSH , PUSH后，输出序列为______，栈
顶2指,3针为_______ 1003H
top=1003H
5
top=1002H
4）空栈：top=-1 ； 5）栈满：top=MaxSize-1；
上溢：栈满时再做进栈运算（一种出错状态，应 设法避免）。 下溢：栈空时再做退栈运算将产生溢出。
10
3、顺序栈基本操作的实现
1）初始化 void InitStack(int *S) {/*构造一个空栈S*/
top= -1; }
11
2）判栈空
