devbox
菜鸟追梦旅行
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构中的栈和队列（附实际案例代码）

作者：菜鸟追梦旅行 | 2024-04-27 19:11:05

赞

踩

数据结构中的栈和队列（附实际案例代码）

1.栈和队列的定义和特点

        栈（Stack）和队列（Queue）是两种基本的数据结构，它们都属于线性表，即数据元素的存储和访问都是线性的。但它们之间也存在着一些区别。

1.1栈的特点

  • 栈是一种后进先出（LIFO）的数据结构，即最后压入栈的元素将首先被弹出。
  • 栈的操作只能在一端进行，这一端被称为栈顶，而另一端被称为栈底。
  • 栈的基本操作包括入栈（Push）和出栈（Pop），入栈操作将元素放入栈顶，出栈操作将栈顶元素移出。
  • 栈常用于实现函数调用的执行过程、表达式求值、括号匹配等场景。

1.2队列的特点

  • 队列是一种先进先出（FIFO）的数据结构，即最先进入队列的元素将首先被取出。
  • 队列的操作分别在两端进行，队列的一端称为队头，另一端称为队尾。
  • 队列的基本操作包括入队（enqueue）和出队（dequeue），入队操作在队尾添加元素，出队操作从队头移除元素。
  • 队列常用于模拟排队、任务调度、缓冲区管理等场景。

2.实际案例引入

        想象一下，你正在开发一个文本编辑器。用户可以在文本编辑器中输入、删除文本，并进行各种编辑操作。为了增强用户体验，你决定实现撤销（Undo）和重做（Redo）功能，以便用户可以回溯到之前的编辑状态或者重新执行已撤销的操作。

        在这种情况下，你需要管理文本的修改历史，以确保撤销和重做操作的正确性。这时候，栈（Stack）和队列（Queue）就可以派上用场了。

撤销功能的实现

        当用户进行编辑操作时，比如输入文本、删除字符等，你需要将当前的编辑状态保存起来。每当用户执行一个编辑操作时，将该操作对应的编辑状态（比如文本内容、光标位置等）压入栈中。这样，栈顶就是最新的编辑状态，而栈底则是最早的编辑状态。

        当用户点击撤销按钮时，从栈顶弹出最新的编辑状态，并将编辑器恢复到该状态。这样用户就可以一步步地回退到之前的编辑状态，实现了撤销功能。

重做功能的实现

        当用户执行撤销操作后，有时候会改变主意，希望重新执行之前的操作。这时候就需要实现重做功能。你可以使用另一个栈来存储被撤销的操作，当用户点击重做按钮时，从重做栈中弹出操作，并将其应用到编辑器中，实现重做功能。

以下是c语言的代码实现：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. #define MAX_LENGTH 100
  6.  
  7. // 编辑历史结构体
  8. typedef struct {
  9.     char text[MAX_LENGTH];
  10.     int cursorPosition;
  11. } EditHistory;
  12.  
  13. // 栈结构定义
  14. typedef struct {
  15.     EditHistory history[MAX_LENGTH];
  16.     int top;
  17. } UndoStack;
  18.  
  19. // 初始化栈
  20. void initStack(UndoStack *stack) {
  21.     stack->top = -1;
  22. }
  23.  
  24. // 判断栈是否为空
  25. int isEmpty(UndoStack *stack) {
  26.     return stack->top == -1;
  27. }
  28.  
  29. // 判断栈是否已满
  30. int isFull(UndoStack *stack) {
  31.     return stack->top == MAX_LENGTH - 1;
  32. }
  33.  
  34. // 入栈操作
  35. void push(UndoStack *stack, EditHistory item) {
  36.     if (isFull(stack)) {
  37.         printf("Stack overflow\n");
  38.         return;
  39.     }
  40.     stack->history[++stack->top] = item;
  41. }
  42.  
  43. // 出栈操作
  44. EditHistory pop(UndoStack *stack) {
  45.     if (isEmpty(stack)) {
  46.         printf("Stack underflow\n");
  47.         exit(1);
  48.     }
  49.     return stack->history[stack->top--];
  50. }
  51.  
  52. // 模拟用户编辑操作，修改文本内容和光标位置
  53. void editContent(char *text, int *cursorPosition) {
  54.     printf("Enter new text: ");
  55.     scanf("%s", text);
  56.     printf("Enter cursor position: ");
  57.     scanf("%d", cursorPosition);
  58. }
  59.  
  60. // 撤销操作
  61. void undo(UndoStack *undoStack, char *text, int *cursorPosition) {
  62.     if (isEmpty(undoStack)) {
  63.         printf("No more undo steps\n");
  64.         return;
  65.     }
  66.     EditHistory history = pop(undoStack);
  67.     strcpy(text, history.text);
  68.     *cursorPosition = history.cursorPosition;
  69. }
  70.  
  71. // 重做操作
  72. void redo(UndoStack *redoStack, char *text, int *cursorPosition) {
  73.     // 在实际情况下，redoStack 应该存储被撤销的操作历史
  74.     // 这里只是简单演示，直接重新执行了撤销操作的逆向操作
  75.     EditHistory history;
  76.     strcpy(history.text, text);
  77.     history.cursorPosition = *cursorPosition;
  78.     push(redoStack, history);
  79. }
  80.  
  81. int main() {
  82.     char text[MAX_LENGTH];
  83.     int cursorPosition;
  84.     UndoStack undoStack, redoStack;
  85.     EditHistory history;
  86.  
  87.     // 初始化栈
  88.     initStack(&undoStack);
  89.     initStack(&redoStack);
  90.  
  91.     // 模拟用户编辑操作
  92.     editContent(text, &cursorPosition);
  93.  
  94.     // 将当前编辑状态压入栈中
  95.     strcpy(history.text, text);
  96.     history.cursorPosition = cursorPosition;
  97.     push(&undoStack, history);
  98.  
  99.     // 用户执行撤销操作
  100.     undo(&undoStack, text, &cursorPosition);
  101.  
  102.     // 用户执行重做操作
  103.     redo(&redoStack, text, &cursorPosition);
  104.  
  105.     return 0;
  106. }

3. 栈的表示和操作的实现

        栈是一种常见的数据结构，具有后进先出（LIFO）的特性，它的操作包括入栈（Push）和出栈（Pop）。栈可以通过顺序存储和链式存储两种方式来实现。

3.1栈的类型定义

        首先，我们定义栈的基本结构，包括栈的元素类型和栈的大小（对于顺序栈而言）

以下是c语言的代码实现：

  1. #define MAX_SIZE 100
  2.  
  3. // 栈的元素类型
  4. typedef int ElementType;
  5.  
  6. // 栈结构定义
  7. typedef struct {
  8.     ElementType data[MAX_SIZE];
  9.     int top; // 栈顶指针
  10. } SeqStack;
  11. 对于链栈，我们需要定义栈节点 的结构
  12. // 链栈节点结构
  13. typedef struct StackNode {
  14.     ElementType data; // 数据域
  15.     struct StackNode *next; // 指针域
  16. } StackNode;
  17.  
  18. // 链栈结构定义
  19. typedef struct {
  20.     StackNode *top; // 栈顶指针
  21. } LinkStack;

3.2顺序栈的表示和实现

        顺序栈使用数组来存储栈元素，同时维护一个栈顶指针指向栈顶元素。下面是顺序栈的入栈和出栈操作的实现。

以下是c语言的代码实现：

  1. // 初始化栈
  2. void initSeqStack(SeqStack *stack) {
  3.     stack->top = -1; // 空栈时栈顶指针为-1
  4. }
  5.  
  6. // 判断栈是否为空
  7. int isEmptySeqStack(SeqStack *stack) {
  8.     return stack->top == -1;
  9. }
  10.  
  11. // 判断栈是否已满
  12. int isFullSeqStack(SeqStack *stack) {
  13.     return stack->top == MAX_SIZE - 1;
  14. }
  15.  
  16. // 入栈操作
  17. void pushSeqStack(SeqStack *stack, ElementType value) {
  18.     if (isFullSeqStack(stack)) {
  19.         printf("Stack overflow\n");
  20.         return;
  21.     }
  22.     stack->data[++stack->top] = value;
  23. }
  24.  
  25. // 出栈操作
  26. ElementType popSeqStack(SeqStack *stack) {
  27.     if (isEmptySeqStack(stack)) {
  28.         printf("Stack underflow\n");
  29.         exit(1);
  30.     }
  31.     return stack->data[stack->top--];
  32. }
  33.

3.3链栈的表示和实现

        链栈使用链表来存储栈元素，每个节点包含数据域和指针域，指向下一个节点。下面是链栈的入栈和出栈操作的实现。

以下是c语言的代码实现：

  1. // 初始化链栈
  2. void initLinkStack(LinkStack *stack) {
  3.     stack->top = NULL; // 空栈时栈顶指针为NULL
  4. }
  5.  
  6. // 判断链栈是否为空
  7. int isEmptyLinkStack(LinkStack *stack) {
  8.     return stack->top == NULL;
  9. }
  10.  
  11. // 入栈操作
  12. void pushLinkStack(LinkStack *stack, ElementType value) {
  13.     StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
  14.     if (newNode == NULL) {
  15.         printf("Memory allocation failed\n");
  16.         exit(1);
  17.     }
  18.     newNode->data = value;
  19.     newNode->next = stack->top;
  20.     stack->top = newNode;
  21. }
  22.  
  23. // 出栈操作
  24. ElementType popLinkStack(LinkStack *stack) {
  25.     if (isEmptyLinkStack(stack)) {
  26.         printf("Stack underflow\n");
  27.         exit(1);
  28.     }
  29.     StackNode *temp = stack->top;
  30.     ElementType value = temp->data;
  31.     stack->top = stack->top->next;
  32.     free(temp);
  33.     return value;
  34. }

4 栈与递归

        栈在计算机科学中具有重要的应用，尤其是在函数调用和递归方面。在程序执行过程中，每次函数调用都会创建一个栈帧（Stack Frame）来存储函数的局部变量、参数以及返回地址等信息，这些栈帧按照后进先出的顺序存放在栈中，因此栈的特性与函数调用和递归密切相关。

4.1函数调用

        当一个函数被调用时，系统需要保存函数的调用信息，以便在函数执行完毕后能够正确返回到调用处继续执行。这些调用信息包括函数的参数、返回地址等，它们会被压入一个称为“调用栈”的栈中。当函数执行完毕后，这些信息会被从调用栈中弹出，从而返回到正确的位置继续执行。

例如，考虑以下递归函数计算阶乘的例子：

  1. int factorial(int n) {
  2.     if (n == 0 || n == 1)
  3.         return 1;
  4.     else
  5.         return n * factorial(n - 1);
  6. }

4.2递归

        递归也是基于栈的思想实现的。当一个函数调用自身时，它会将当前函数的状态（包括参数、返回地址等）压入栈中，然后开始执行。当递归调用结束时，函数的状态会被弹出栈，并返回到上一个调用处继续执行。例如，计算阶乘的递归函数：

  1. int factorial(int n) {
  2.     if (n == 0) {
  3.         return 1;
  4.     } else {
  5.         return n * factorial(n - 1);
  6.     }
  7. }

        在函数 factorial 被调用时，n 的值和返回地址会被压入栈中。当函数递归调用自身时，新的 n 值和返回地址也会被压入栈中。当递归结束时，函数的状态会被依次弹出栈，直到返回到初始的调用处。

5队列的表示和操作的实现

        队列是一种常见的数据结构，具有先进先出（FIFO）的特性，通常使用数组或链表来实现。下面我们将分别介绍数组队列和链表队列的表示和操作实现。

5.1数组队列的表现和实现

        使用数组实现队列时，需要记录队头（front）和队尾（rear）的位置。初始时，front 和 rear 都指向数组的首元素。当一个元素被入队时，rear 向前移动一位；当一个元素被出队时，front 向前移动一位。当 rear 等于数组大小时，队列满；当 front 等于 rear 时，队列为空。

  1. #define MAX_SIZE 100
  2.  
  3. // 队列元素类型
  4. typedef int ElementType;
  5.  
  6. // 队列结构定义
  7. typedef struct {
  8.     ElementType data[MAX_SIZE];
  9.     int front; // 队头指针
  10.     int rear; // 队尾指针
  11. } ArrayQueue;

接下来是数组队列的入队和出队操作的实现。

  1. // 初始化队列
  2. void initArrayQueue(ArrayQueue *queue) {
  3.     queue->front = queue->rear = -1; // 空队列时队头和队尾指针都为-1
  4. }
  5.  
  6. // 判断队列是否为空
  7. int isEmptyArrayQueue(ArrayQueue *queue) {
  8.     return queue->front == -1;
  9. }
  10.  
  11. // 判断队列是否已满
  12. int isFullArrayQueue(ArrayQueue *queue) {
  13.     return (queue->rear + 1) % MAX_SIZE == queue->front;
  14. }
  15.  
  16. // 入队操作
  17. void enqueueArrayQueue(ArrayQueue *queue, ElementType value) {
  18.     if (isFullArrayQueue(queue)) {
  19.         printf("Queue overflow\n");
  20.         return;
  21.     }
  22.     if (isEmptyArrayQueue(queue))
  23.         queue->front = queue->rear = 0;
  24.     else
  25.         queue->rear = (queue->rear + 1) % MAX_SIZE;
  26.     queue->data[queue->rear] = value;
  27. }
  28.  
  29. // 出队操作
  30. ElementType dequeueArrayQueue(ArrayQueue *queue) {
  31.     if (isEmptyArrayQueue(queue)) {
  32.         printf("Queue underflow\n");
  33.         exit(1);
  34.     }
  35.     ElementType value = queue->data[queue->front];
  36.     if (queue->front == queue->rear)
  37.         queue->front = queue->rear = -1;
  38.     else
  39.         queue->front = (queue->front + 1) % MAX_SIZE;
  40.     return value;
  41. }

5.2链表队列的表现和实现

        链表队列使用链表来存储队列元素，每个节点包含数据域和指针域，指向下一个节点。

  1. // 队列节点结构
  2. typedef struct QueueNode {
  3.     ElementType data; // 数据域
  4.     struct QueueNode *next; // 指针域
  5. } QueueNode;
  6.  
  7. // 队列结构定义
  8. typedef struct {
  9.     QueueNode *front; // 队头指针
  10.     QueueNode *rear; // 队尾指针
  11. } LinkedQueue;

接下来是链表队列的入队和出队操作的实现。

  1. // 初始化链表队列
  2. void initLinkedQueue(LinkedQueue *queue) {
  3.     queue->front = queue->rear = NULL; // 空队列时队头和队尾指针都为NULL
  4. }
  5.  
  6. // 判断链表队列是否为空
  7. int isEmptyLinkedQueue(LinkedQueue *queue) {
  8.     return queue->front == NULL;
  9. }
  10.  
  11. // 入队操作
  12. void enqueueLinkedQueue(LinkedQueue *queue, ElementType value) {
  13.     QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
  14.     if (newNode == NULL) {
  15.         printf("Memory allocation failed\n");
  16.         exit(1);
  17.     }
  18.     newNode->data = value;
  19.     newNode->next = NULL;
  20.     if (isEmptyLinkedQueue(queue))
  21.         queue->front = queue->rear = newNode;
  22.     else {
  23.         queue->rear->next = newNode;
  24.         queue->rear = newNode;
  25.     }
  26. }
  27.  
  28. // 出队操作
  29. ElementType dequeueLinkedQueue(LinkedQueue *queue) {
  30.     if (isEmptyLinkedQueue(queue)) {
  31.         printf("Queue underflow\n");
  32.         exit(1);
  33.     }
  34.     QueueNode *temp = queue->front;
  35.     ElementType value = temp->data;
  36.     queue->front = queue->front->next;
  37.     free(temp);
  38.     if (queue->front == NULL) // 出队后队列为空，重置队尾指针
  39.         queue->rear = NULL;
  40.     return value;
  41. }

6 综合案例

案例一：浏览器历史记录

        浏览器通常使用栈来管理历史记录。当你访问一个网页时，该网页会被压入历史记录栈中。当你点击后退按钮时，浏览器会从历史记录栈中弹出当前网页，并将上一个网页展示出来。    

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef struct Stack {
  5.     int size;
  6.     int top;
  7.     char **history;
  8. } Stack;
  9.  
  10. void initStack(Stack *stack, int size) {
  11.     stack->size = size;
  12.     stack->top = -1;
  13.     stack->history = malloc(sizeof(char*) * size);
  14.     if (stack->history == NULL) {
  15.         printf("内存分配失败。\n");
  16.         exit(1);
  17.     }
  18. }
  19.  
  20. int isEmpty(Stack *stack) {
  21.     return stack->top == -1;
  22. }
  23.  
  24. int isFull(Stack *stack) {
  25.     return stack->top == stack->size - 1;
  26. }
  27.  
  28. void push(Stack *stack, char *url) {
  29.     if (isFull(stack)) {
  30.         printf("栈已满，无法压入新元素。\n");
  31.         return;
  32.     }
  33.     stack->top++;
  34.     stack->history[stack->top] = strdup(url);
  35. }
  36.  
  37. char *pop(Stack *stack) {
  38.     if (isEmpty(stack)) {
  39.         printf("栈为空，无法弹出元素。\n");
  40.         return NULL;
  41.     }
  42.     char *url = stack->history[stack->top];
  43.     stack->top--;
  44.     return url;
  45. }
  46.  
  47. int main() {
  48.     Stack historyStack;
  49.     initStack(&historyStack, 5);
  50.  
  51.     push(&historyStack, "www.example.com");
  52.     push(&historyStack, "www.example1.com");
  53.     push(&historyStack, "www.example2.com");
  54.  
  55.     char *prevUrl = pop(&historyStack);
  56.     printf("后退到上一页：%s\n", prevUrl);
  57.  
  58.     return 0;
  59. }

    案例二：打印任务队列

        打印任务队列也是队列的一个实际应用。当你向打印机发送多个打印任务时，它们会被添加到打印任务队列中。打印机会从队列中取出任务进行打印，遵循先进先出的原则。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef struct Node {
  5.     char *filename;
  6.     struct Node *next;
  7. } Node;
  8.  
  9. typedef struct {
  10.     Node *head;
  11.     Node *tail;
  12. } Queue;
  13.  
  14. void initQueue(Queue *queue) {
  15.     queue->head = NULL;
  16.     queue->tail = NULL;
  17. }
  18.  
  19. void enqueue(Queue *queue, char *filename) {
  20.     Node *newNode = malloc(sizeof(Node));
  21.     if (newNode == NULL) {
  22.         printf("内存分配失败。\n");
  23.         return;
  24.     }
  25.     newNode->filename = strdup(filename);
  26.     newNode->next = NULL;
  27.  
  28.     if (queue->tail == NULL) {
  29.         queue->head = newNode;
  30.         queue->tail = newNode;
  31.     } else {
  32.         queue->tail->next = newNode;
  33.         queue->tail = newNode;
  34.     }
  35. }
  36.  
  37. char *dequeue(Queue *queue) {
  38.     if (queue->head == NULL) {
  39.         printf("队列为空，无法出队。\n");
  40.         return NULL;
  41.     }
  42.     Node *temp = queue->head;
  43.     char *filename = temp->filename;
  44.     queue->head = temp->next;
  45.     if (queue->head == NULL) {
  46.         queue->tail = NULL;
  47.     }
  48.     free(temp);
  49.     return filename;
  50. }
  51.  
  52. int main() {
  53.     Queue printQueue;
  54.     initQueue(&printQueue);
  55.  
  56.     enqueue(&printQueue, "document1.pdf");
  57.     enqueue(&printQueue, "document2.pdf");
  58.     enqueue(&printQueue, "document3.pdf");
  59.  
  60.     char *filename = dequeue(&printQueue);
  61.     printf("正在打印：%s\n", filename);
  62.  
  63.     return 0;
  64. }

7 小结

        栈和队列是两种基本的数据结构，在计算机科学中有着广泛的应用。它们都属于线性表，但具有不同的特性。栈遵循后进先出的原则，在函数调用和递归中扮演着重要角色。队列遵循先进先出的原则，在任务管理和数据处理中十分有用。通过理解和掌握栈和队列，我们可以更好地解决各种实际问题，提高程序的效率和性能。

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

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

  

闽ICP备14008679号