devbox
花生_TL007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

初学数据结构——从零开始的数据结构学习总结篇（栈和队列）_数据结构队列心得总结

作者：花生_TL007 | 2024-02-29 23:15:19

赞

踩

数据结构队列心得总结

前言

之前鸽了真的抱歉，肝了一段时间把栈和队列全部更完。

简介：

你有没有想过，为什么我们吃饭的时候，总是先吃掉最后放进嘴里的那一口？为什么我们排队的时候，总是先让最先来的人先走？这些生活中的现象，其实都和栈和队列的数据结构有关。

栈和队列是两种常见的数据结构，它们分别对应了后进先出（LIFO）和先进先出（FIFO）的原则。

栈就像是一叠盘子，你只能从最上面拿走或放上一个盘子，这个盘子就是栈顶。

队列就像是一条长龙，你只能从尾巴加入或从头部离开，这两个位置就是队尾和队首。

本文将向你大致介绍栈和队列的概念、特征和应用场景。

注：

本博客为本人在学习数据结构路途上的知识整理，如觉得对有你有所帮助，还希望不要吝啬你的赞，整理知识点是真的很累|*´Å`)ﾉ 。由于博主只是一名大一新生，在文章难免会出现错误，还希望指正。如果想要转载，附上链接就行。

本文中的颜色标记

  • 红色部分为重点内容
  • 蓝色部分为注释

目录

前言

简介：

注：

本文中的颜色标记

一、栈和队列的概念

栈

定义：

相关概念：

逻辑结构

存储结构

运算规则

实现方式

栈与一般线性表的区别

队列

定义：

相关概念

逻辑结构

存储结构

运算规则

实现方式

栈和队列的实际运用

栈的实际运用

队列的实际运用

 二、栈的表示和实现 

栈的抽象数据类型定义

栈的基本操作

注意事项

栈的顺序实现

使用数组作为顺序栈存储方式的特点：

存储方式：

栈的状态表示

顺序栈的代码实现

栈的链式存储实现

使用链表作为顺序栈存储方式的特点：

存储方式：

链栈的代码实现

三、队列的实现和操作

队列的抽象数据类型定义

基本操作：

 队列的顺序存储方式实现

存储方式：

状态：

顺序队的代码实现

循环队列

队列的链式存储方式 

存储方式

代码实现

 

总结

一、栈和队列的概念

栈

定义：

  • 栈（stack）是一个特殊的线性表，是限定仅在一端（通常是表尾）
    进行插入和删除操作的线性表。
  • 又称为后进先出(Last In First Out) 的线性表,简称LIFO结构

相关概念：

  • 表尾（即an端）称为栈顶Top
  • 表头（即a1端）称为栈底Base

例如：栈S=(a1,a2,a3...,an1,an)a1称为栈底元素,an称为栈顶元素

  • 插入元素到栈顶（即表尾）的操作，称为入栈(PUSH)
  • 从栈顶(即表尾)删除最后一个元素的操作，称为出栈(POP) 

栈只能在栈顶进行插入和删除的操作，只能在an-1尾部进行插入，插入an之后，只能先删除an然后再删除an-1 

逻辑结构

 与同线性表相同，仍为一对一关系。

存储结构

用顺序栈或链栈存储均可，但以顺序栈更常见

运算规则

只能在栈顶运算，且访问结点时依照后进先出（LIFO）的原则。

实现方式

关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同

栈与一般线性表的区别

  • 仅在于运算规则不同

队列

定义：

  • 队列（queue）是一种在表一端插入（表尾），在另一端（表头）删除的线性表。
  • 又称为先进先出（FristInFristOut）的线性表，简称FIFO结构。

相关概念

  • 表尾（即an端）称为队尾
  • 表头（即a1端）称为队首
  • 插入元素到队尾（即表尾）的操作，称为入队(PUSH)
  • 从队首(即表头)删除第一个元素的操作，称为出队(POP) 

逻辑结构

与同线性表相同，仍为一对一关系。

存储结构

顺序队或链队，以循环顺序队列更常见。

运算规则

只能在队首和队尾运算，直访问结点时依照先进先出（FIFO）的原则

实现方式

关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同

栈和队列的实际运用

栈的实际运用

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

解题步骤：

①将s依次栈入栈

②将s栈入的时候进行判段，为左括号直接栈入

③如果为右括号，判断是否与栈顶匹配，匹配则将栈顶栈出

④如果右括号与栈顶不匹配，则为非有效的括号，直接结束函数。

​

队列的实际运用

舞伴问题

假设在舞会上，男士和女士各自排成一队。舞会开始依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。

显然，先入队的男士或女士先出队配成舞伴。因此该问题具有典型的先进先出特性，可以用队列作为算法的数据结构。

①首先构造两个队列

②依次将队头元素出队配成舞伴

③某队为空，则另外一队等待着则是下一舞曲第一个
可获得舞伴的人。

​

 二、栈的表示和实现 

栈的抽象数据类型定义

ADT Stack {

数据对象：

D= (ai /ai EElemSet, i=1,2..,n, n≥0)

数据关系：

R1={ <ai-1,ai> | ai-1,ai ∈D,i=2...,n}

约定an端为栈顶，a1端为栈底。

基本操作：初始化、进栈、出栈、取栈顶元素等

} ADT Stack

栈的基本操作

InitStack(&S)
初始化操作
操作结果：构造一个空栈S

DestroyStack(&S)
销毁栈操作
初始条件：栈S已存在。
操作结果：栈S被销毁。

StackEmpty(S)判定S是否为空栈
初始条件：栈S已存在。
操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE

StackLength(S)
求栈的长度
初始条件：栈S


初始条件：栈S已存在且非空
操作结果：用e返回S的栈顶元素。

ClearStack(&S)
栈置空操作
初始条件：栈S已存在
操作结果：将S清为空栈

Push(&S,e)
入栈操作
初始条件：栈S已存在
操作结果：插入元素e为新的栈顶元素。

Pop(&S &e)
出栈操作
初始条件：栈S已存在且非空。
操作结果：删除S的栈顶元素an，并用e返回其值。

注意事项

  • 这里传参e来获取返回值只是伪代码方便，后面使用C语言写也使用e来得到返回值只是为了和伪代码相符，可以直接将结果return。

栈的顺序实现

由于栈本身就是线性表，于是栈也有顺序存储和链式存储两种实现方式。

  • 栈的顺序存储-顺序栈

  • 栈的链式存储-链栈

使用数组作为顺序栈存储方式的特点：

  • 简单方便、但易产生溢出（数组大小固定）

  • 上溢(stack overflow)：栈已经满，又要压入元素

  • 下溢(stack underflow)：栈已经空，还要弹出元素 注：上溢是一种错误，使问题的处理无法进行；而下溢一般认为是一种结束条件，即问题处理结束。

存储方式：

同一般线性表的顺序存储结构完全相同利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端

  • 图示

    设top指针，指示栈顶元素在顺序栈中的位置

  • 设base指针，指示栈底元素在顺序栈中的位置

  • 为了方便操作，通常top指示真正的栈顶元素之上的下标地址

  • 用stacksize表示栈可使用的最大容量

栈的状态表示

  • 栈空：base==top
  • 栈满：top-base==stacksize

顺序栈的代码实现

  • 创建链栈
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4.  
  5. typedef int ElemType;      // 定义栈元素的数据类型
  6.  
  7. typedef struct
  8. {
  9.     ElemType data;         // 数据域
  10.     LinkStack next;
  11. }StackNode, *LinkStack;    // 定义链栈栈的类型
  • 初始化操作 InitStack(&S)
  1. void InitStack(SqStack* S)
  2. {
  3.     S->base = (ElemType*)malloc(MAXSIZE * sizeof(ElemType));  // 分配存储空间
  4.     if (!S->base)  // 分配失败
  5.     {
  6.         exit(1);
  7.     }
  8.     S->top = S->base;   // 栈顶和栈底指针初始指向同一位置
  9.     S->stacksize = MAXSIZE;   // 栈的最大容量
  10. }
  • 销毁栈操作 DestroyStack(&S)
  1. void DestroyStack(SqStack* S)
  2. {
  3.     free(S->base);   // 释放存储空间
  4.     S->base = S->top = NULL;   // 将栈底和栈顶指针置为NULL
  5.     S->stacksize = 0;   // 当前栈的容量为0
  6. }
  • 判定S是否为空栈 StackEmpty(S)
  1. bool StackEmpty(SqStack S)
  2. {
  3.     if (S.top == S.base)  // 栈顶和栈底指针相同时，即栈为空
  4.         return true;   // 返回TRUE
  5.     else
  6.         return false;   // 返回FALSE
  7. }
  • 求栈的长度 StackLength(S)
  1. int StackLength(SqStack S)
  2. {
  3.     return (S.top - S.base);  // 栈顶指针减去栈底指针就是栈的长度
  4. }
  • 栈置空操作 ClearStack(&S)
  1. oid ClearStack(SqStack* S)
  2. {
  3.     S->top = S->base;   // 将栈顶和栈底指针指向同一位置
  4. }
  • 取栈顶元素操作 GetTop(&S,&e)
  1. bool GetTop(SqStack S, ElemType* e)
  2. {
  3.     if (S.top == S.base) // 栈为空时，返回FALSE
  4.         return false;
  5.     *e = *(S.top - 1);   // 栈顶元素的值赋给e
  6.     return true;
  7. }
  • 入栈操作 Push(&S,e)
  1. void Push(SqStack* S, ElemType e)
  2. {
  3.     if (S->top - S->base == S->stacksize) // 栈满时，扩充存储空间
  4.     {
  5.         S->base = (ElemType*)realloc(S->base, (S->stacksize + MAXSIZE) * sizeof(ElemType));
  6.         if (!S->base)
  7.         {
  8.             exit(1);
  9.         }
  10.         S->top = S->base + S->stacksize; // 栈底指针不变，栈顶指针指向新的位置
  11.         S->stacksize += MAXSIZE;         // 栈的最大容量增加 MAXSIZE
  12.     }
  13.     *(S->top++) = e;  // 元素 e 入栈，栈顶指针加1
  14. }
  • 出栈操作 Pop(&S)
  1. bool Pop(SqStack* S)
  2. {
  3.     if (S->top == S->base) // 栈为空时，返回FALSE
  4.     {
  5.         return false;
  6.     }
  7.     S--;
  8.     return true;
  9. }

栈的链式存储实现

  • 链栈是运算受限的单链表，只能在链表头部进行操作

使用链表作为顺序栈存储方式的特点：

  • 链表的头指针就是栈顶
  • 不需要头结点
  • 基本不存在栈满的情况
  • 空栈相当于头指针指向空
  • 插入和删除仅在栈顶处执行

存储方式：

  • 利用尾插法在单链表中存储
  • 头指针指向链表尾部（栈顶）

 

链栈的代码实现

  •  创建顺序栈
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4.  
  5. typedef int ElemType;   // 定义栈元素的数据类型
  6.  
  7. typedef struct StackNode
  8. {
  9.     ElemType data;         // 数据域
  10.     struct StackNode* next;   // 指向下一个结点的指针
  11. } StackNode, * LinkStack;     // 定义链栈栈的类型
  • 初始化操作 InitStack(&S)
  1. void InitStack(LinkStack* S)
  2. {
  3.     *S = NULL;   // 初始化栈顶指针为空
  4. }
  • 销毁栈操作 DestroyStack(&S)
  1. void ClearStack(LinkStack* S)
  2. {
  3.     StackNode* p;
  4.     while (*S != NULL)
  5.     {
  6.         p = *S;     // 指向栈顶结点
  7.         *S = (*S)->next;   // 栈顶指针指向下一个结点
  8.         free(p);    // 释放当前结点的内存空间
  9.     }
  10. }
  • 判定S是否为空栈 StackEmpty(S)
  1. bool StackEmpty(LinkStack S)
  2. {
  3.     if (S == NULL)   // 栈顶指针为空时，即栈为空
  4.         return true;
  5.     else
  6.         return false;
  7. }
  • 求栈的长度 StackLength(S)
  1. int StackLength(LinkStack S)
  2. {
  3.     int len = 0;      // 栈的长度
  4.     while (S != NULL)
  5.     {
  6.         S = S->next;  // 栈顶指针向下移动
  7.         len++;       // 栈的长度加1
  8.     }
  9.     return len;
  10. }
  • 取栈顶元素操作 GetTop(&S,&e)
  1. bool GetTop(LinkStack S, ElemType* e)
  2. {
  3.     if (S == NULL) // 栈为空时，返回FALSE
  4.         return false;
  5.     *e = S->data;   // 栈顶元素的值赋给e
  6.     return true;
  7. }
  • 入栈操作 Push(&S,e)
  1. void Push(LinkStack* S, ElemType e)
  2. {
  3.     StackNode* p;
  4.     p = (StackNode*)malloc(sizeof(StackNode));  // 创建新结点
  5.     if (!p)   // 分配内存失败
  6.     {
  7.         exit(1);
  8.     }
  9.     p->data = e;     // 将元素e赋值给新结点的数据域
  10.     p->next = *S;    // 新结点的next指针指向原栈顶指针指向的结点
  11.     *S = p;          // 修改栈顶指针指向新的结点
  12. }
  • 出栈操作 Pop(&S &e)
  1. bool Pop(LinkStack* S)
  2. {
  3.     StackNode* p;
  4.     if (*S == NULL) // 栈为空时，返回FALSE
  5.         return false;
  6.     p = *S;         // p指向栈顶结点
  7.     *S = p->next;   // 栈顶指针指向下一个结点
  8.     free(p);        // 释放当前结点的内存空间
  9.     return true;
  10. }

三、队列的实现和操作

队列的抽象数据类型定义

ADT Queuel {
数据对象：D={ai | ai∈ElemSet,=1,2,...,n≥0}
数据关系：R={<ai-1,ai> | ai-1,aI∈D,=2..,n) 约定a1端为队列头，an端为队列尾。
基本操作：初始化、入队、出队、将队列置空、遍历队列等操作...
} ADT Queue

基本操作：

InitQueue(&Q)
操作结果：构造空队列Q

DestroyQueue(&Q)
条件：队列Q已存在
操作结果：队列Q被销毁

ClearQueue(&Q)
条件：队列Q已存在
操作结果：将Q清空

QueueLength(Q）
条件：队列Q已存在
操作结果：返回Q的元素个数，即队长

GetHead(Q,&e)
条件：Q为非空队列
操作结果：用e返回Q的队头元素

EnQueue(&Q,e)
条件：队列Q已存在
操作结果：插入元素e为Q的队尾元素

DeQueue(&Q,&e)
条件：Q为非空队列
操作结果：删除Q的队头元素，用e返回值

 队列的顺序存储方式实现

存储方式：

同一般线性表的顺序存储结构完全相同利用一组地址连续的存储单元依次存放自队列头到队尾的数据元素。队尾一般在低地址端

图示

  • 设front指针，指示队头元素在顺序栈中的位置

  • 设rear指针，指示队尾元素在顺序栈中的位置

状态：

  • front==rear表示队空
  • rear=QLength（队列长度）表示队满

顺序队的代码实现

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4.  
  5. #define MAX_SIZE 100 // 队列的最大长度
  6.  
  7. typedef int ElemType; // 定义队列元素的数据类型
  8.  
  9. typedef struct
  10. {
  11.     ElemType* data; // 存储队列元素的数组
  12.     int front; // 队头指针，指向队头元素
  13.     int rear; // 队尾指针，指向队尾元素的下一个位置
  14. } SqQueue;
  15.  
  16. // 构造空队列Q
  17. void InitQueue(SqQueue* Q)
  18. {
  19.     Q->data = (ElemType*)malloc(MAX_SIZE * sizeof(ElemType)); // 动态分配数组空间
  20.     Q->front = Q->rear = 0; // 初始化队头和队尾指针
  21. }
  22.  
  23. // 队列Q销毁
  24. void DestroyQueue(SqQueue* Q)
  25. {
  26.     free(Q->data); // 释放队列的数组空间
  27.     Q->data = NULL; //将指针置空
  28.     Q->front = Q->rear = 0; // 初始化队头和队尾指针
  29. }
  30.  
  31. // 将队列Q清空
  32. void ClearQueue(SqQueue* Q)
  33. {
  34.     Q->front = Q->rear = 0; // 将队头和队尾指针置为0，表示队列为空
  35. }
  36.  
  37. // 返回队列Q的元素个数，即队列的长度
  38. int QueueLength(SqQueue Q)
  39. {
  40.     return Q.rear - Q.front;
  41. }
  42.  
  43. // 用e返回队列Q的队头元素
  44. bool GetHead(SqQueue Q, ElemType* e)
  45. {
  46.     if (Q.front == Q.rear) // 队列为空，无法取出队头元素
  47.     {
  48.         return false;
  49.     }
  50.     *e = Q.data[Q.front]; // 将队头元素赋值给e
  51.     return true;
  52. }
  53.  
  54. // 插入元素e为队列Q的队尾元素
  55. bool EnQueue(SqQueue* Q, ElemType e)
  56. {
  57.     if ((Q->rear + 1) % MAX_SIZE == Q->front) // 队列已满，插入失败
  58.     {
  59.         return false;
  60.     }
  61.     Q->data[Q->rear] = e; // 将元素e插入队尾
  62.     Q->rear++; // 更新队尾指针
  63.     return true;
  64. }
  65.  
  66. // 删除队列Q的队头元素，并用e返回值
  67. bool DeQueue(SqQueue* Q, ElemType* e)
  68. {
  69.     if (Q->front == Q->rear) // 队列为空，删除失败
  70.     {
  71.         return false;
  72.     }
  73.     *e = Q->data[Q->front]; // 将队头元素赋值给e
  74.     Q->front++; // 更新队头指针
  75.     return true;
  76. }

循环队列

如果仔细观察上面的代码，不难发一个问题：

当我门进行出队操作时，front+1后之前的空间便无法利用，如果此时队满了，出现上溢情况，但实际数组中却还有空间无法被我们使用，我们把这种情况称为假上溢。

假上溢会极大地浪费我们的内存空间，我们该如何解决这个问题呢？

解决假上溢的方法

  1. 将队中元素依次向队头方向移动。缺点：浪费时间每移动一次，队中元素都要移动
  2. 将队空间设想成一个循环的表，即分配给队列的n个存储单元可以循环使用，当rear为maxqsize时，若数组的开始端空着，从头开始使用空着的空间。

  • base[0]接在base[MAXQSiZE-1]之后，若rear+1==M，则令rear=0

实现方法：利用模（%）运算。

  • 插入元素：
    Q.base[Q.rear]=x;
    Q.rear=(Q.rear+1)% MAXQSIZE;
  • 删除元素：
    X=Q.base[s.front];
    Q.front=(Q.front+1)%MAXQSIZE;

不难发现，循环队列中队空为：rear==front，队满也为rear==front，该如判断队空队满？

  1. 另外设一个标志以区别队空、队满
  2. 另设一个变量，记录元素个数
  3. 少用一个先素空间 

  • 队空：rear==front
  • 队满：(rear+1)%MAXQSIXZE==front

代码实现：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4.  
  5. #define MAX_SIZE 100 // 循环队列的最大长度
  6.  
  7. typedef int ElemType; // 定义队列元素的数据类型
  8.  
  9. typedef struct
  10. {
  11.     ElemType* data; // 存储队列元素的数组
  12.     int front; // 队头指针，指向队头元素
  13.     int rear; // 队尾指针，指向队尾元素的下一个位置
  14.     int size; // 队列元素个数
  15. } SqQueue;
  16.  
  17. // 构造空队列Q
  18. void InitQueue(SqQueue* Q)
  19. {
  20.     Q->data = (ElemType*)malloc(MAX_SIZE * sizeof(ElemType)); // 动态分配数组空间
  21.     Q->front = Q->rear = 0; // 初始化队头和队尾指针
  22.     Q->size = 0; // 初始化队列元素个数
  23. }
  24.  
  25. // 队列Q销毁
  26. void DestroyQueue(SqQueue* Q)
  27. {
  28.     free(Q->data); // 释放队列的数组空间
  29.     Q->data = NULL; //将指针置空
  30.     Q->front = Q->rear = 0; // 初始化队头和队尾指针
  31.     Q->size = 0; // 将队列元素个数置为0，表示队列为空
  32. }
  33.  
  34. // 将队列Q清空
  35. void ClearQueue(SqQueue* Q)
  36. {
  37.     Q->front = Q->rear = 0; // 将队头和队尾指针置为0，表示队列为空
  38.     Q->size = 0; // 将队列元素个数置为0，表示队列为空
  39. }
  40.  
  41. // 返回队列Q的元素个数，即队列的长度
  42. int QueueLength(SqQueue Q)
  43. {
  44.     return Q.size;
  45. }
  46.  
  47. // 用e返回队列Q的队头元素
  48. bool GetHead(SqQueue Q, ElemType* e)
  49. {
  50.     if (Q.front == Q.rear) // 队列为空，无法取出队头元素
  51.         return false;
  52.     *e = Q.data[Q.front]; // 将队头元素赋值给e
  53.     return true;
  54. }
  55.  
  56. // 插入元素e为队列Q的队尾元素
  57. bool EnQueue(SqQueue* Q, ElemType e)
  58. {
  59.     if ((Q->rear + 1) % MAX_SIZE == Q->front) // 队列已满，插入失败
  60.         return false;
  61.     Q->data[Q->rear] = e; // 将元素e插入队尾
  62.     Q->rear = (Q->rear + 1) % MAX_SIZE; // 更新队尾指针
  63.     Q->size++; // 队列元素个数加1
  64.     return true;
  65. }
  66.  
  67. // 入队，插入元素e为队列Q的队尾元素
  68. bool EnQueue(SqQueue* Q, ElemType e)
  69. {
  70.     if ((Q->rear + 1) % MAX_SIZE == Q->front) // 队列已满，插入失败
  71.         return false;
  72.     Q->data[Q->rear] = e; // 将元素e插入队尾
  73.     Q->rear = (Q->rear + 1) % MAX_SIZE; // 更新队尾指针
  74.     Q->size++; // 队列元素个数加1
  75.     return true;
  76. }
  77.  
  78. // 出队，删除队列Q的队头元素，并用e返回值
  79. bool DeQueue(SqQueue* Q, ElemType* e)
  80. {
  81.     if (Q->front == Q->rear) // 队列为空，删除失败
  82.         return false;
  83.     *e = Q->data[Q->front]; // 将队头元素赋值给e
  84.     Q->front = (Q->front + 1) % MAX_SIZE; // 更新队头指针
  85.     Q->size--; // 队列元素个数减1
  86.     return true;
  87. }

队列的链式存储方式 

  • 当我们无法估计队列长度时，一般采用链式队列

存储方式

  • 链栈是运算受限的单链表，在链表头部和尾部进行操作

代码实现

 

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4.  
  5. typedef int ElemType; // 定义队列元素的数据类型
  6.  
  7. // 队列结点类型
  8. typedef struct QNode
  9. {
  10.     ElemType data; // 结点的数据域
  11.     struct QNode* next; // 结点的指针域
  12. }QNode, * QuenePtr;
  13.  
  14. // 链式队列类型
  15. typedef struct
  16. {
  17.     QuenePtr front; // 队头指针，指向队头结点
  18.     QuenePtr rear; // 队尾指针，指向队尾结点
  19. }LinkQuene;
  20.  
  21. // 初始化队列Q
  22. void InitQuene(LinkQuene* Q)
  23. {
  24.     Q->front = Q->rear = (QuenePtr)malloc(sizeof(QNode)); // 创建头结点
  25.     if (!Q->front) // 内存分配失败
  26.         exit(1);
  27.     Q->front->next = NULL; // 头结点的指针域置空
  28. }
  29.  
  30. // 销毁队列Q
  31. void DestroyQuene(LinkQuene* Q)
  32. {
  33.     QuenePtr p = Q->front;
  34.     while (p) // 逐个释放结点内存
  35.     {
  36.         Q->front = p->next;
  37.         free(p);
  38.         p = Q->front;
  39.     }
  40.     Q->front = Q->rear = NULL; // 将队列指针置空
  41. }
  42.  
  43.  
  44. // 返回队列Q的元素个数，即队列的长度
  45. int QueneLength(LinkQuene Q)
  46. {
  47.     int count = 0;
  48.     QuenePtr p = Q.front->next;
  49.     while (p) // 遍历队列计数
  50.     {
  51.         count++;
  52.         p = p->next;
  53.     }
  54.     return count;
  55. }
  56.  
  57. // 用e返回队列Q的队头元素
  58. bool GetHead(LinkQuene Q, ElemType* e)
  59. {
  60.     if (Q.front == Q.rear) // 队列为空，无法取出队头元素
  61.         return false;
  62.     *e = Q.front->next->data; // 将队头元素赋值给e
  63.     return true;
  64. }
  65.  
  66. // 入队操作
  67. bool EnQuene(LinkQuene* Q, ElemType e)
  68. {
  69.     QuenePtr p = (QuenePtr)malloc(sizeof(QNode)); // 创建新结点
  70.     if (!p) // 内存分配失败
  71.         return false;
  72.     p->data = e; // 将元素e存储到新结点中
  73.     p->next = NULL; // 将新结点的next指针置为NULL
  74.  
  75.     Q->rear->next = p; // 将新结点链接到队尾结点的后面
  76.     Q->rear = p; // 将队尾指针指向新结点
  77.  
  78.     return true;
  79. }
  80.  
  81. // 出队操作
  82. bool DeQuene(LinkQuene* Q, ElemType* e)
  83. {
  84.     if (Q->front == Q->rear) // 队列为空，无法出队
  85.         return false;
  86.     QuenePtr p = Q->front->next; // 指向队头结点
  87.     *e = p->data; // 将队头元素赋值给e
  88.     Q->front->next = p->next; // 将队头结点删除
  89.     if (Q->rear == p) // 如果队列只有一个元素，出队后队列为空，需要将队尾指针指向头结点
  90.         Q->rear = Q->front;
  91.     free(p); // 释放出队的结点的空间
  92.     return true;
  93. }

总结

栈和队列是两种常用的数据结构，都是操作方式受限的线性表，都支持快速插入和删除元素，但它们的特点和应用场景略有不同。

栈（Stack）是一种后进先出（Last In First Out, LIFO）的数据结构，通常用数组或链表实现。栈有两个基本操作：入栈（push）和出栈（pop）。在栈中，只能访问最后一个入栈的元素，不能访问其他元素。栈的典型应用包括：表达式求值、函数调用、括号匹配等。

队列（Queue）是一种先进先出（First In First Out, FIFO）的数据结构，通常用数组或链表实现。队列有两个基本操作：入队（enQueue）和出队（deQueue）。在队列中，只能访问最先入队的元素，不能访问其他元素。队列的典型应用包括：进程调度、广度优先搜索、缓存等。

在实际应用中，栈和队列的应用十分广泛。例如，在计算机底层，操作系统利用栈来保存程序调用信息和临时变量；在图形学中，使用栈来实现画图的撤销和重做操作；在网络通信中，使用队列来实现数据包的存储和转发。掌握栈和队列的基本操作及其应用，是编程中必不可少的基本功。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/169177
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号