内容发布更新时间 : 2024/12/23 23:51:09星期一 下面是文章的全部内容请认真阅读。

目录

栈和队列........................................................................................................................................... 1

1. 栈....................................................................................................................................... 1

1.1 1.2 1.3 1.4

栈的基本概念 ....................................................................................................... 1 栈的顺序存储结构 ............................................................................................... 1 栈的链式存储结构 ............................................................................................... 3 习题 ....................................................................................................................... 3

2. 队列 ................................................................................................................................... 6

2.1 2.2 2.3 2.4

队列的基本概念 ................................................................................................... 6 队列的顺序存储结构 ........................................................................................... 6 队列的链式存储结构 ........................................................................................... 8 习题 ....................................................................................................................... 9

3. 栈和队列的应用 ............................................................................................................. 14

3.1

习题 ..................................................................................................................... 14

栈和队列

1. 栈 1.1

栈的基本概念

1.1.1 栈的定义

栈(Stack)：只允许在一端进行插入或删除操作的线性表。 栈顶(Top):线性表允许进行插入和删除的那一端

栈底(Bottom): 固定的，不允许进行插入和删除操作的另一端。 空栈：不含任何元素的空表。

栈的一个明显的操作特性：后进先出(Last In First Out, LIFO),故又称为后进先出的线性表。

1.1.2 栈的基本操作

InitStack(&S)：初始化一个空栈S。

StackEmpty(S):判断一个栈是否为空，若栈S为空返回true,否则返回false。 Push(&S,x):进栈，若栈S未满，将x加入使之成为新栈顶。 Pop(&S,&x)出栈，若栈S非空，弹出栈顶元素，并用x返回。 GetTop(S,&x):读栈顶元素，若栈S非空，用x返回栈顶元素。 ClearStack(&S):销毁栈，并释放栈S所占的存储空间。

在解答算法题时，若题干没有做出限制，可以直接使用这些基本的操作函数。

1.2 栈的顺序存储结构

1.2.1 顺序栈的实现

栈的顺序存储称为顺序栈，它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针(top)指示当前栈顶的位置。 栈的顺序存储类型可描述为:

#defineMaxSize 50 //定义栈中元素的最大个数 typedefstruct {

ElemType data[MaxSize]; //存放栈中元素 int top; //栈顶指针

}SqStack;

栈顶指针：S.top，初始时设置S.top=-1；栈顶元素:S.data[S.top]。 进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素。 出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1。

栈空条件：S.top==-1；栈满条件：S.top==MaxSize-1；栈长：S.top+1。

1.2.2 顺序栈的基本运算

(1) 初始化

voidInitStack(SqStack&S) {

1

}

S.top = -1; //初始化栈顶指针

(2) 判空栈

boolStackEmpty(SqStack&S) { }

if (S.top == -1) //栈空

returntrue;

returnfalse; else//不空

(3) 进栈

bool Push(SqStack&S, ElemTypex) { }

if (S.top == MaxSize - 1) //栈满，报错

returnfalse;

S.data[++S.top] = x; //指针先加1，再入栈 returntrue;

(4) 出栈

bool Pop(SqStack&S, ElemType&x) { }

if (S.top == -1) //栈空，报错

returnfalse;

x = S.data[S.top--]; //先出栈，指针再减1 returntrue;

(5) 读栈顶元素

boolGetTop(SqStack&S, ElemType&x) { }

if (S.top == -1) //栈空，报错

returnfalse;

x = S.data[S.top]; //x记录栈顶元素 returntrue;

注意：这里栈顶指针指向的就是栈顶元素，所以进栈时的操作是S.data[++S.top] = x；出栈时的操作时x = S.data[S.top--]。如果栈顶指针初始化为S.top=0，即栈顶指针指向栈顶元素的下一个位置，则入栈操作变为S.data[S.top++] = x；出栈操作变为x = S.data[--S.top]。相应的栈空、栈满条件也会发生变化。

1.2.3 共享栈

利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。

两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=MaxSize时1号栈为空；仅当两个栈顶指针相邻(top1-top0=1)时，判断为栈满。当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减1再赋值；出栈时则刚好相反。 共享栈是为了更有效地利用存储空间，两个栈地空间相互调节，只有在整个存储空间被占满时才发生上溢。其存取数据的时间复杂度均为O(1)，所以对存取效率没有什么影响。

2