程序中的栈和队列是什么意思
发布网友
发布时间：2022-04-20 06:32
共1个回答
热心网友
时间：2022-03-29 17:02
的修改是按后进先出的原则进行的，我们又称栈为LIFO表(Last
In
First
Out)。通常栈有顺序栈和链栈两种存储结构。
栈的基本运算有六种：
·构造空栈：InitStack(S)
·判栈空:
StackEmpty(S)
·判栈满：
StackFull(S)
·进栈：
Push(S,x)
·退栈：
Pop(S)
·取栈顶元素：StackTop(S)
在顺序栈中有"上溢"和"下溢"的现象。
·"上溢"是栈顶指针指出栈的外面是出错状态。
·"下溢"可以表示栈为空栈,因此用来作为控制转移的条件。
顺序栈中的基本操作有六种：·构造空栈·判栈空·判栈满·进栈·退栈·取栈顶元素
链栈则没有上溢的*，因此进栈不要判栈满。链栈不需要在头部附加头结点，只要有链表的头指针就可以了。
链栈中的基本操作有五种：·构造空栈·判栈空·进栈·退栈·取栈顶元素
队列(Queue)是一种运算受限的线性表，插入在表的一端进行，而删除在表的另一端进行，允许删除的一端称为队头(front)，允许插入的
一端称为队尾(rear)
,队列的操作原则是先进先出的，又称作FIFO表(First
In
First
Out)
。队列也有顺序存储和链式存储两种存储结
构。
队列的基本运算有六种：
·置空队：InitQueue(Q)
·判队空：QueueEmpty(Q)
·判队满：QueueFull(Q)
·入队：EnQueue(Q,x)
·出队：DeQueue(Q)
·取队头元素：QueueFront(Q)
顺序队列的"假上溢"现象：由于头尾指针不断前移，超出向量空间。这时整个向量空间及队列是空的却产生了"上溢"现象。
为了克服"假上溢"现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列。
判定循环队列是空还是满，方法有三种：
·一种是另设一个布尔变量来判断；
·第二种是少用一个元素空间，入队时先测试（(rear+1)%m
=
front）?
满：空；
·第三种就是用一个计数器记录队列中的元素的总数。
队列的链式存储结构称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾进行插入(入队)的操作，在表尾增加一个尾指
针，一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢的问题。在链队列的出队算法中，要注意当原队中只
有一个结点时，出队后要同进修改头尾指针并使队列变空。
