ToB企服应用市场:ToB评测及商务社交产业平台

标题: 数据结构3-栈和队列 [打印本页]

---

作者: 麻花痒    时间: 5 天前
标题: 数据结构3-栈和队列
 栈和队列的操纵特点

栈和队列是限定插入和删除只能在表的“端点”举行的线性表
栈（操纵尾部）和队列（操纵头部）是线性表的子集（是插入和删除位置受限的线性表）
栈（Stack）

栈是一个遵循 后进先出 (LIFO, Last In First Out) 规则的线性表。栈的插入和删除操纵都只能在表的一端举行，即栈顶。常见的栈操纵包括：

• Push：向栈顶插入一个元素。
  
• Pop：从栈顶删除一个元素。
  
• Top 或 Peek：检察栈顶元素。
  

队列（Queue）

队列是一个遵循 先辈先出 (FIFO, First In First Out) 规则的线性表。队列的插入操纵发生在表的一端（队尾），删除操纵发生在表的另一端（队头）。常见的队列操纵包括：

• Enqueue：向队尾插入一个元素。
  
• Dequeue：从队头删除一个元素。
  
• Front：检察队头元素。
  

栈与队列的比较：

• 栈：插入和删除只能发生在表的顶部。栈是一种顺序存取的数据结构，操纵是单向的。
  
• 队列：插入操纵发生在队尾，删除操纵发生在队头，符合先辈先出的原则。
  

在顺序存储结构和链式存储结构上实现栈(顺序栈、链栈)和队列(循环队列、链队列)的各种基本操纵

1. 栈（Stack）基本操纵

顺序栈（Array-based Stack）

顺序栈使用数组作为底层存储结构。基本操纵包括 Push（入栈）、Pop（出栈）、Peek（获取栈顶元素）。

1. #define MAX_SIZE 100
3. typedef int ElemType;  // 假设栈的元素类型为整型
4. typedef struct {
5.     ElemType elem[MAX_SIZE];
6.     int top;  // 栈顶指针
7. } SqStack;
9. // InitStack: 初始化栈，构建一个空的顺序栈
10. void InitStack(SqStack &S) {
11.     S.top = -1;  // 初始化栈为空栈
12. }
14. // StackEmpty: 判断栈是否为空，栈空返回1，否则返回0
15. int StackEmpty(SqStack S) {
16.     return S.top == -1;  // 栈空返回1，否则返回0
17. }
19. // StackLength: 返回栈的元素个数（栈的长度）
20. int StackLength(SqStack S) {
21.     return S.top + 1;  // 栈长度为栈顶指针+1
22. }
24. // Push: 向栈顶插入元素e，如果栈满则报错
25. void Push(SqStack &S, ElemType e) {
26.     if (S.top == MAX_SIZE - 1) {
27.         printf("栈满\n");
28.         return;
29.     }
30.     S.elem[++S.top] = e;  // 入栈
31. }
33. // Pop: 从栈顶删除元素，并将删除的元素存储在e中
34. void Pop(SqStack &S, ElemType &e) {
35.     if (S.top == -1) {
36.         printf("栈空\n");
37.         return;
38.     }
39.     e = S.elem[S.top--];  // 出栈
40. }
42. // GetTop: 获取栈顶元素，但不删除该元素
43. void GetTop(SqStack S, ElemType &e) {
44.     if (S.top == -1) {
45.         printf("栈空\n");
46.         return;
47.     }
48.     e = S.elem[S.top];  // 获取栈顶元素
49. }

复制代码

链栈（Linked List-based Stack）

链栈使用链表作为底层存储结构。基本操纵与顺序栈雷同。

1. typedef int ElemType;
2. typedef struct Node {
3.     ElemType data;
4.     struct Node* next;
5. } Node;
7. typedef struct {
8.     Node* top;  // 栈顶指针
9. } LinkStack;
11. // InitStack: 初始化栈，构建一个空的链栈
12. void InitStack(LinkStack &S) {
13.     S.top = NULL;  // 初始化栈为空栈
14. }
16. // StackEmpty: 判断链栈是否为空，空栈返回1，否则返回0
17. int StackEmpty(LinkStack S) {
18.     return S.top == NULL;  // 栈空返回1，否则返回0
19. }
21. // Push: 向链栈的栈顶插入元素e
22. void Push(LinkStack &S, ElemType e) {
23.     Node* newNode = (Node*)malloc(sizeof(Node));
24.     newNode->data = e;
25.     newNode->next = S.top;
26.     S.top = newNode;  // 入栈
27. }
29. // Pop: 从链栈的栈顶删除元素，并将删除的元素存储在e中
30. void Pop(LinkStack &S, ElemType &e) {
31.     if (S.top == NULL) {
32.         printf("栈空\n");
33.         return;
34.     }
35.     Node* temp = S.top;
36.     e = S.top->data;  // 出栈
37.     S.top = S.top->next;
38.     free(temp);
39. }
41. // GetTop: 获取链栈的栈顶元素，但不删除该元素
42. void GetTop(LinkStack S, ElemType &e) {
43.     if (S.top == NULL) {
44.         printf("栈空\n");
45.         return;
46.     }
47.     e = S.top->data;  // 获取栈顶元素
48. }

复制代码

链队列（Linked List-based Queue）

链队列使用链表作为底层存储结构，队列的头指针指向队头，尾指针指向队尾。

1. typedef int ElemType;
2. typedef struct Node {
3.     ElemType data;
4.     struct Node* next;
5. } Node;
7. typedef struct {
8.     Node* front;  // 队头指针
9.     Node* rear;   // 队尾指针
10. } LinkQueue;
12. // InitStack: 初始化栈，构建一个空的链栈
13. void InitQueue(LinkQueue &Q) {
14.     Q.front = Q.rear = NULL;  // 初始化队列为空队列
15. }
17. // StackEmpty: 判断链栈是否为空，空栈返回1，否则返回0
18. int QueueEmpty(LinkQueue Q) {
19.     return Q.front == NULL;  // 判断队列是否为空
20. }
22. // Enqueue: 向队列的队尾插入元素e
23. void Enqueue(LinkQueue &Q, ElemType e) {
24.     Node* newNode = (Node*)malloc(sizeof(Node));
25.     newNode->data = e;
26.     newNode->next = NULL;
27.     if (Q.rear == NULL) {
28.         Q.front = Q.rear = newNode;  // 队列为空时，队头和队尾都指向新节点
29.     } else {
30.         Q.rear->next = newNode;  // 队尾插入新节点
31.         Q.rear = newNode;
32.     }
33. }
35. // Dequeue: 从队列的队头删除元素，并将删除的元素存储在e中
36. void Dequeue(LinkQueue &Q, ElemType &e) {
37.     if (Q.front == NULL) {
38.         printf("队列空\n");
39.         return;
40.     }
41.     Node* temp = Q.front;
42.     e = Q.front->data;  // 出队
43.     Q.front = Q.front->next;
44.     if (Q.front == NULL) {
45.         Q.rear = NULL;  // 如果队列为空，更新队尾指针
46.     }
47.     free(temp);
48. }
50. // GetFront: 获取队列的队头元素，但不删除该元素
51. void GetFront(LinkQueue Q, ElemType &e) {
52.     if (Q.front == NULL) {
53.         printf("队列空\n");
54.         return;
55.     }
56.     e = Q.front->data;  // 获取队头元素
57. }

复制代码

栈和队列的简单应用

假设有一个洗碗机，它需要根据不同的顺序来处置处罚碗碟。这个问题涉及到两个部门：清洗和列队。当碗碟进洗碗机时，它们是按先辈先出（FIFO）的顺序进入的。然而，清洗时，洗碗机只能后进先出（LIFO）的顺序举行处置处罚。也就是说，洗碗机必须清洗最后进入的碗碟，然后才清洗前面的碗碟。
使用一个队列来模拟碗碟的进入顺序，而使用一个栈来模拟洗碗机清洗的顺序。

• 碗碟进入洗碗机：用户将碗碟依次放入洗碗机，这部门用一个队列来模拟。每个碗碟被按顺序到场队列。
  
• 清洗顺序：由于洗碗机必须按照“后进先出”的顺序清洗碗碟，可以将队列中的碗碟转移到栈中，然后按栈的顺序举行清洗。
  
• 清洗过程：从栈中弹出碗碟并清洗，直到栈为空。
  

1. from collections import deque
3. class Dishwasher:
4.     def __init__(self):
5.         self.queue = deque()  # 用队列存储碗碟进入顺序
6.         self.stack = []  # 用栈模拟清洗顺序
8.     def add_dish(self, dish):
9.         # 把碗碟按顺序放入队列
10.         self.queue.append(dish)
11.         print(f"添加碗碟：{dish}")
13.     def start_washing(self):
14.         # 把队列中的碗碟转移到栈中（洗碗机需要后进先出的顺序）
15.         while self.queue:
16.             dish = self.queue.popleft()
17.             self.stack.append(dish)
18.         
19.         print("开始清洗碗碟：")
20.         # 按栈的顺序清洗碗碟（后进先出）
21.         while self.stack:
22.             dish = self.stack.pop()
23.             print(f"正在清洗：{dish}")
25. # 使用示例：
26. dishwasher = Dishwasher()
27. dishwasher.add_dish("碗1")
28. dishwasher.add_dish("碟1")
29. dishwasher.add_dish("杯子1")
31. # 开始清洗
32. dishwasher.start_washing()

复制代码

碗碟进入顺序：碗1, 碟1, 杯子1，它们依次进入队列。
清洗顺序：由于洗碗机必须后进先出（LIFO），我们把队列中的碗碟依次转移到栈中，然后按栈的顺序清洗：先清洗最后放入的“杯子1”，然后是“碟1”，最后是“碗1”。
递归程序筹划的基本方法(分治法、减治法)

递归程序筹划的基本方法，包括分治法和减治法。其中，分治法递归的结构为“基本项+归纳项”。详细而言：
基本项：递归的停止条件，当问题足够简单时，直接返回结果。
归纳项：通过将问题分解为更小的子问题来解决，并递归地调用同样的方法来处置处罚这些子问题，直到满足基本项条件。
分治法递归：基本项+归纳项。
阶乘计算：

1. long Fact(long n) {
2.     if (n == 0) return 1;  // 基本项
3.     else return n * Fact(n - 1);  // 归纳项
4. }

复制代码

基本项：当 n == 0 时，返回 1。
归纳项：当 n > 0 时，返回 n * Fact(n - 1)，通过递归调用计算阶乘。
这种结构很适合解决分治法问题，即通过递归将大问题分解成小问题，再逐步解决。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4