[关闭]
@guoxs 2015-12-05T07:25:32.000000Z 字数 7931 阅读 4291

数据结构之栈与队列

数据结构与算法


一、栈的概念

栈(stack)是限定仅在表尾进行插入和删除操作的线性表,允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又称为后进先出(LastIn First Out)的线性表,简称LIFO结构

栈元素具有线性关系,即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作,这里表尾是指栈顶,而不是栈底。

栈的插入操作,叫作进栈,也称压栈、入栈;栈的删除操作,叫作出栈,也有的叫作弹栈。

栈的抽象数据类型

  1. ADT 栈(stack)
  2. Data
  3. 同线性表。元素具有相同的类型,相邻元素具有前驱和后继关系。
  4. Operation
  5. InitStack(*S): 初始化操作,建立一个空栈S
  6. DestroyStack(*S): 若栈存在,则销毁它。
  7. ClearStack(*S): 将栈清空。
  8. StackEmpty(S): 若栈为空,返回true,否则返回false
  9. GetTop(S, *e): 若栈存在且非空,用e返回S的栈顶元素。
  10. Push(*S, e): 若栈S存在,插入新元素e到栈S中并成为栈顶元素。
  11. Pop(*S, *e): 删除栈S中栈顶元素,并用e返回其值。
  12. StackLength(S): 返回栈S的元素个数。
  13. endADT

二、栈的顺序存储结构及实现

通常定义一个top变量来指示栈顶元素在数组中的位置,这个top就如同物理中的游标卡尺的游标,可以来回移动,意味着栈顶的top可以变大变小,无论如何游标不能超出尺的长度。若存储栈的长度为StackSize,则栈顶位置top必须小于StackSize。当栈存在一个元素时,top等于0,因此通常把空栈的判定条件定为top等于-1

栈的结构定义

  1. /* SElemType类型根据实际情况而定,这里假设为int */
  2. typedef int SElemType;
  3. typedef struct
  4. {
  5. SElemType data[MAXSIZE];
  6. /* 用于栈顶指针 */
  7. int top;
  8. }SqStack;

栈状态

2.1 栈的顺序存储结构——进栈操作

进栈

  1. /* 插入元素e为新的栈顶元素 */
  2. Status Push(SqStack *S, SElemType e)
  3. {
  4. /* 栈满 */
  5. if (S->top == MAXSIZE - 1)
  6. {
  7. return ERROR;
  8. }
  9. /* 栈顶指针增加一 */
  10. S->top++;
  11. /* 将新插入元素赋值给栈顶空间 */
  12. S->data[S->top] = e;
  13. return OK;
  14. }

时间复杂度O(1)。

2.2 栈的顺序存储结构——出栈

  1. /* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */
  2. Status Pop(SqStack *S, SElemType *e)
  3. {
  4. if (S->top == -1)
  5. return ERROR;
  6. /* 将要删除的栈顶元素赋值给e */
  7. *e = S->data[S->top];
  8. /* 栈顶指针减一 */
  9. S->top--;
  10. return OK;
  11. }

时间复杂度O(1)。

2.3 两栈共享空间

栈的顺序存储只准栈顶进出元素,所以不存在线性表插入和删除时需要移动元素的问题,但是有一个明显的缺陷:必须事先定义存储空间的大小。万一不够用了,就需要编程手段来扩展数组的容量,非常麻烦。
解决方案:两栈共享空间
两栈共享空间
基本思路:栈存储从两端向中间靠拢,top1和top2是栈1和栈2的栈顶指针,只要top1和top2相差大于1,则说明栈不满。若指针之间相差1时,即top1+1==top2为栈满。若栈2是空栈,栈1的top1等于n-1时,就是栈1满了。反之,当栈1为空栈时,top2等于0时,为栈2满。

两栈共享空间的结构的代码:

  1. /* 两栈共享空间结构 */
  2. typedef struct
  3. {
  4. SElemType data[MAXSIZE];
  5. int top1; /* 栈1栈顶指针 */
  6. int top2; /* 栈2栈顶指针 */
  7. } SqDoubleStack;

两栈共享空间的push方法

  1. /* 插入元素e为新的栈顶元素 ,stackNumber:判断是栈1还是栈2*/
  2. Status Push(SqDoubleStack *S, SElemType e,
  3. int stackNumber)
  4. {
  5. /* 栈已满,不能再push新元素了 */
  6. if (S->top1 + 1 == S->top2)
  7. return ERROR;
  8. /* 栈1有元素进栈 */
  9. if (stackNumber == 1)
  10. /* 若栈1则先top1+1后给数组元素赋值 */
  11. S->data[++S->top1] = e;
  12. /* 栈2有元素进栈 */
  13. else if (stackNumber == 2)
  14. /* 若栈2则先top2-1后给数组元素赋值 */
  15. S->data[--S->top2] = e;
  16. return OK;
  17. }

两栈共享空间的pop方法

  1. /* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */
  2. Status Pop(SqDoubleStack *S, SElemType *e, int stackNumber)
  3. {
  4. if (stackNumber == 1)
  5. {
  6. /* 说明栈1已经是空栈,溢出 */
  7. if (S->top1 == -1)
  8. return ERROR;
  9. /* 将栈1的栈顶元素出栈 */
  10. *e = S->data[S->top1--];
  11. }
  12. else if (stackNumber == 2)
  13. {
  14. /* 说明栈2已经是空栈,溢出 */
  15. if (S->top2 == MAXSIZE)
  16. return ERROR;
  17. /* 将栈2的栈顶元素出栈 */
  18. *e = S->data[S->top2++];
  19. }
  20. return OK;
  21. }

三、栈的链式存储结构及实现

3.1 栈的链式存储结构

栈的链式存储结构,简称为链栈
链栈中,栈顶放在单链表的头部。链栈不需要头结点。
对于链栈来说,基本不存在栈满的情况,除非内存已经没有可以使用的空间,如果真的发生,那此时的计算机操作系统已经面临死机崩溃的情况,而不是这个链栈是否溢出的问题。链栈的空就是top=NULL的时候。

链栈的结构代码:

  1. typedef struct StackNode
  2. {
  3. SElemType data;
  4. struct StackNode *next;
  5. } StackNode, *LinkStackPtr;
  6. typedef struct LinkStack
  7. {
  8. LinkStackPtr top;
  9. int count;
  10. } LinkStack;

3.2 栈的链式存储结构——进栈操作

对于链栈的进栈push操作,假设元素值为e的新结点是s,top为栈顶指针,示意图如下图所示。
进栈

  1. /* 插入元素e为新的栈顶元素 */
  2. Status Push(LinkStack *S, SElemType e)
  3. {
  4. LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
  5. s->data = e;
  6. /* 把当前的栈顶元素赋值给新结点的直接后继,如图中① */
  7. s->next = S->top;
  8. /* 将新的结点s赋值给栈顶指针,如图中② */
  9. S->top = s;
  10. S->count++;
  11. return OK;
  12. }

3.3 栈的链式存储结构——出栈操作

  1. /* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */
  2. Status Pop(LinkStack *S, SElemType *e)
  3. {
  4. LinkStackPtr p;
  5. if (StackEmpty(*S))
  6. return ERROR;
  7. *e = S->top->data;
  8. /* 将栈顶结点赋值给p,如图③ */
  9. p = S->top;
  10. /* 使得栈顶指针下移一位,指向后一结点,如图④ */
  11. S->top = S->top->next;
  12. /* 释放结点p */
  13. free(p);
  14. S->count--;
  15. return OK;
  16. }

链栈的进栈push和出栈pop操作都很简单,没有任何循环操作,时间复杂度均为O(1)。

对比顺序栈与链栈:
时间复杂度: 均为O(1)
空间性能:
顺序栈需要事先确定一个固定的长度,可能会存在内存空间浪费的问题,但它的优势是存取时定位很方便;
链栈则要求每个元素都有指针域,这同时也增加了一些内存开销,但对于栈的长度无限制

如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈会更好一些。

四、栈的应用

4.1 递归:斐波那契数列(Fibonacci)

f(n)=01f(n1)+f(n2)n = 0n = 1n > 1

用循环实现:

  1. int main()
  2. {
  3. int i;
  4. int a[40];
  5. a[0] = 0;
  6. a[1] = 1;
  7. printf("%d ", a[0]);
  8. printf("%d ", a[1]);
  9. for (i = 2; i < 40; i++)
  10. {
  11. a[i] = a[i - 1] + a[i - 2];
  12. printf("%d ", a[i]);
  13. }
  14. return 0;
  15. }

用递归实现:

  1. /* 斐波那契的递归函数 */
  2. int Fbi(int i)
  3. {
  4. if (i < 2)
  5. return i == 0 ? 0 : 1;
  6. /* 这里Fbi就是函数自己,它在调用自己 */
  7. return Fbi(i - 1) + Fbi(i - 2);
  8. }
  9. int main()
  10. {
  11. int i;
  12. for (i = 0; i < 40; i++)
  13. printf("%d ", Fbi(i));
  14. return 0;
  15. }

递归图示:
递归
递归定义
迭代和递归的区别:迭代使用的是循环结构,递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容易让人理解,从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本,会耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。
递归与栈的联系
在前行阶段,对于每一层递归,函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段,位于栈顶的局部变量、参数值和返回地址被弹出,用于返回调用层次中执行代码的其余部分,也就是恢复了调用的状态。

4.2 栈的应用——四则运算表达式求值

后缀表达法:一种不用括号的表达式,由波兰逻辑学家Jan·ukasiewicz发明,也称为逆波兰(Reverse Polish Notation,RPN)。
对于“9+(3-1)×3+10÷2”,使用后缀表达式表示为:“9 3 1-3*+102/+”。
规则:从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终获得结果。
中缀表达式转后缀表达式
中缀表达式“9+(3-1)×3+10÷2”转化为后缀表达式“9 3 1-3*+10 2/+”。
规则:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括号或优先级不高于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式为止。

五、队列

队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。
队列是一种先进先出(First In First Out)的线性表,简称FIFO。允许插入的一端称为队尾,允许删除的一端称为队头。假设队列是q=(a1,a2,......,an),那么a1就是队头元素,而an是队尾元素。这样我们就可以删除时,总是从a1开始,而插入时,列在最后。这也比较符合我们通常生活中的习惯,排在第一个的优先出列,最后来的当然排在队伍最后,如图6所示。
队列

5.1 队列的抽象数据类型

  1. ADT 队列(Queue)
  2. Data
  3. 同线性表。元素具有相同的类型,相邻元素具有前驱和后继关系。
  4. Operation
  5. InitQueue(*Q): 初始化操作,建立一个空队列Q
  6. DestroyQueue(*Q): 若队列Q存在,则销毁它。
  7. ClearQueue(*Q): 将队列Q清空。
  8. QueueEmpty(Q): 若队列Q为空,返回true,否则返回false
  9. GetHead(Q, *e): 若队列Q存在且非空,用e返回队列Q的队头元素。
  10. EnQueue(*Q, e): 若队列Q存在,插入新元素e到队列Q中并成为队尾元素。
  11. DeQueue(*Q, *e): 删除队列Q中队头元素,并用e返回其值。
  12. QueueLength(Q): 返回队列Q的元素个数
  13. endADT

5.2 循环队列

假设一个队列有n个元素,则顺序存储的队列需建立一个大于n的数组,并把队列的所有元素存储在数组的前n个单元,数组下标为0的一端即是队头。所谓的入队列操作,其实就是在队尾追加一个元素,不需要移动任何元素,因此时间复杂度为O(1),如图7所示。
队列
与栈不同的是,队列元素的出列是在队头,即下标为0的位置,那也就意味着,队列中的所有元素都得向前移动,以保证队列的队头,也就是下标为0的位置不为空,此时时间复杂度为O(n),如图8所示。
队列
这样的结构对于出列来说非常不便利,为什么队列中的每个元素都要移动呢?所以引进了循环队列。
循环队列定义:队列中头尾相接的顺序存储结构称为循环队列。
引入两个指针,front指针指向队头元素,rear指针指向队尾元素的下一个位置,这样当front等于rear时,此队列不是还剩一个元素,而是空队列或者满队列。满队列情况如下:
队列
那么如何判断此时的队列究竟是空还是满呢?
办法一是设置一个标志变量flag,当front==rear,且flag=0时为队列空,当front==rear,且flag=1时为队列满。
办法二是当队列空时,条件就是front=rear,当队列满时,我们修改其条件,保留一个元素空间。也就是说,队列满时,数组中还有一个空闲单元。例如图10所示,我们就认为此队列已经满了,也就是说,我们不允许图9的右图情况出现。
队列
第二种方法中队列满的条件为:(rear+1)%QueueSize==front
通用的计算队列长度公式为:(rear-front+QueueSize)%QueueSize
循环队列的顺序存储结构代码如下:

  1. /* QElemType类型根据实际情况而定,这里假设为int */
  2. typedef int QElemType;
  3. /* 循环队列的顺序存储结构 */
  4. typedef struct
  5. {
  6. QElemType data[MAXSIZE];
  7. /* 头指针 */
  8. int front;
  9. /* 尾指针,若队列不空,
  10. 指向队列尾元素的下一个位置 */
  11. int rear;
  12. } SqQueue;

循环队列的初始化代码如下:

  1. /* 初始化一个空队列Q */
  2. Status InitQueue(SqQueue *Q)
  3. {
  4. Q->front = 0;
  5. Q->rear = 0;
  6. return OK;
  7. }

循环队列求队列长度代码如下:

  1. /* 返回Q的元素个数,也就是队列的当前长度 */
  2. int QueueLength(SqQueue Q)
  3. {
  4. return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
  5. }

循环队列的入队列操作代码如下:

  1. /* 若队列未满,则插入元素e为Q新的队尾元素 */
  2. Status EnQueue(SqQueue *Q, QElemType e)
  3. {
  4. /* 队列满的判断 */
  5. if ((Q->rear + 1) % MAXSIZE == Q->front)
  6. return ERROR;
  7. /* 将元素e赋值给队尾 */
  8. Q->data[Q->rear] = e;
  9. /* rear指针向后移一位置, */
  10. Q->rear = (Q->rear + 1) % MAXSIZE;
  11. /* 若到最后则转到数组头部 */
  12. return OK;
  13. }

循环队列的出队列操作代码如下:

  1. /* 若队列不空,则删除Q中队头元素,用e返回其值 */
  2. Status DeQueue(SqQueue *Q, QElemType *e)
  3. {
  4. /* 队列空的判断 */
  5. if (Q->front == Q->rear)
  6. return ERROR;
  7. /* 将队头元素赋值给e */
  8. *e = Q->data[Q->front];
  9. /* front指针向后移一位置, */
  10. Q->front = (Q->front + 1) % MAXSIZE;
  11. /* 若到最后则转到数组头部 */
  12. return OK;
  13. }

5.3 队列的链式存储结构及实现

队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,简称为链队列。为了操作上的方便,将队头指针指向链队列的头结点,而队尾指针指向终端结点,如图11所示。
 队列的链式存储
空队列时,front和rear都指向头结点。
链队列的结构为:

  1. /* QElemType类型根据实际情况而定,这里假设为int */
  2. typedef int QElemType;
  3. /* 结点结构 */
  4. typedef struct QNode
  5. {
  6. QElemType data;
  7. struct QNode *next;
  8. } QNode, *QueuePtr;
  9. /* 队列的链表结构 */
  10. typedef struct
  11. {
  12. /* 队头、队尾指针 */
  13. QueuePtr front, rear;
  14. } LinkQueue;

5.3.1 队列的链式存储结构——入队操作

入队操作时,其实就是在链表尾部插入结点:
 入队
其代码如下:

  1. /* 插入元素e为Q的新的队尾元素 */
  2. Status EnQueue(LinkQueue *Q, QElemType e)
  3. {
  4. QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
  5. /* 存储分配失败 */
  6. if (!s)
  7. exit(OVERFLOW);
  8. s->data = e;
  9. s->next = NULL;
  10. /* 把拥有元素e新结点s赋值给原队尾结点的后继, */
  11. Q->rear->next = s;
  12. /* 见上图中① */
  13. /* 把当前的s设置为队尾结点,rear指向s,见上图中② */
  14. Q->rear = s;
  15. return OK;
  16. }

5.3.2 队列的链式存储结构——出队操作

出队操作时,就是头结点的后继结点出队,将头结点的后继改为它后面的结点,若链表除头结点外只剩一个元素时,则需将rear指向头结点:
 出队
代码如下:

  1. /* 若队列不空,删除Q的队头元素,用e返回其值,
  2. 并返回OK,否则返回ERROR */
  3. Status DeQueue(LinkQueue *Q, QElemType *e)
  4. {
  5. QueuePtr p;
  6. if (Q->front == Q->rear)
  7. return ERROR;
  8. /* 将欲删除的队头结点暂存给p,见上图中① */
  9. p = Q->front->next;
  10. /* 将欲删除的队头结点的值赋值给e */
  11. *e = p->data;
  12. /* 将原队头结点后继p->next赋值给头结点后继, */
  13. Q->front->next = p->next;
  14. /* 见上图中② */
  15. /* 若队头是队尾,则删除后将rear指向头结点,见上图中③ */
  16. if (Q->rear == p)
  17. Q->rear = Q->front;
  18. free(p);
  19. return OK;
  20. }

5.3.3 循环队列与链队列的比较

选项 循环队列 链队列
时间 基本操作O(1),循环队列是事先申请好空间,使用期间不释放 基本操作O(1),链队列每次申请和释放结点也会存在一些时间开销
空间 必须有一个固定的长度,所以就有了存储元素个数和空间浪费的问题 需要一个指针域,会产生一些空间上的开销,但也可以接受。所以在空间上,链队列更加灵活。

总的来说,在可以确定队列长度最大值的情况下,建议用循环队列,如果无法预估队列的长度时,则用链队列。

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注