栈和队列的操纵特点
栈和队列是限定插入和删除只能在表的“端点”举行的线性表
栈（操纵尾部）和队列（操纵头部）是线性表的子集（是插入和删除位置受限的线性表）
栈（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（获取栈顶元素）。
- #define MAX_SIZE 100
- typedef int ElemType; // 假设栈的元素类型为整型
- typedef struct {
- ElemType elem[MAX_SIZE];
- int top; // 栈顶指针
- } SqStack;
- // InitStack: 初始化栈，构建一个空的顺序栈
- void InitStack(SqStack &S) {
- S.top = -1; // 初始化栈为空栈
- }
- // StackEmpty: 判断栈是否为空，栈空返回1，否则返回0
- int StackEmpty(SqStack S) {
- return S.top == -1; // 栈空返回1，否则返回0
- }
- // StackLength: 返回栈的元素个数（栈的长度）
- int StackLength(SqStack S) {
- return S.top + 1; // 栈长度为栈顶指针+1
- }
- // Push: 向栈顶插入元素e，如果栈满则报错
- void Push(SqStack &S, ElemType e) {
- if (S.top == MAX_SIZE - 1) {
- printf("栈满\n");
- return;
- }
- S.elem[++S.top] = e; // 入栈
- }
- // Pop: 从栈顶删除元素，并将删除的元素存储在e中
- void Pop(SqStack &S, ElemType &e) {
- if (S.top == -1) {
- printf("栈空\n");
- return;
- }
- e = S.elem[S.top--]; // 出栈
- }
- // GetTop: 获取栈顶元素，但不删除该元素
- void GetTop(SqStack S, ElemType &e) {
- if (S.top == -1) {
- printf("栈空\n");
- return;
- }
- e = S.elem[S.top]; // 获取栈顶元素
- }
链栈使用链表作为底层存储结构。基本操纵与顺序栈雷同。
- typedef int ElemType;
- typedef struct Node {
- ElemType data;
- struct Node* next;
- } Node;
- typedef struct {
- Node* top; // 栈顶指针
- } LinkStack;
- // InitStack: 初始化栈，构建一个空的链栈
- void InitStack(LinkStack &S) {
- S.top = NULL; // 初始化栈为空栈
- }
- // StackEmpty: 判断链栈是否为空，空栈返回1，否则返回0
- int StackEmpty(LinkStack S) {
- return S.top == NULL; // 栈空返回1，否则返回0
- }
- // Push: 向链栈的栈顶插入元素e
- void Push(LinkStack &S, ElemType e) {
- Node* newNode = (Node*)malloc(sizeof(Node));
- newNode->data = e;
- newNode->next = S.top;
- S.top = newNode; // 入栈
- }
- // Pop: 从链栈的栈顶删除元素，并将删除的元素存储在e中
- void Pop(LinkStack &S, ElemType &e) {
- if (S.top == NULL) {
- printf("栈空\n");
- return;
- }
- Node* temp = S.top;
- e = S.top->data; // 出栈
- S.top = S.top->next;
- free(temp);
- }
- // GetTop: 获取链栈的栈顶元素，但不删除该元素
- void GetTop(LinkStack S, ElemType &e) {
- if (S.top == NULL) {
- printf("栈空\n");
- return;
- }
- e = S.top->data; // 获取栈顶元素
- }
链队列使用链表作为底层存储结构，队列的头指针指向队头，尾指针指向队尾。
- typedef int ElemType;
- typedef struct Node {
- ElemType data;
- struct Node* next;
- } Node;
- typedef struct {
- Node* front; // 队头指针
- Node* rear; // 队尾指针
- } LinkQueue;
- // InitStack: 初始化栈，构建一个空的链栈
- void InitQueue(LinkQueue &Q) {
- Q.front = Q.rear = NULL; // 初始化队列为空队列
- }
- // StackEmpty: 判断链栈是否为空，空栈返回1，否则返回0
- int QueueEmpty(LinkQueue Q) {
- return Q.front == NULL; // 判断队列是否为空
- }
- // Enqueue: 向队列的队尾插入元素e
- void Enqueue(LinkQueue &Q, ElemType e) {
- Node* newNode = (Node*)malloc(sizeof(Node));
- newNode->data = e;
- newNode->next = NULL;
- if (Q.rear == NULL) {
- Q.front = Q.rear = newNode; // 队列为空时，队头和队尾都指向新节点
- } else {
- Q.rear->next = newNode; // 队尾插入新节点
- Q.rear = newNode;
- }
- }
- // Dequeue: 从队列的队头删除元素，并将删除的元素存储在e中
- void Dequeue(LinkQueue &Q, ElemType &e) {
- if (Q.front == NULL) {
- printf("队列空\n");
- return;
- }
- Node* temp = Q.front;
- e = Q.front->data; // 出队
- Q.front = Q.front->next;
- if (Q.front == NULL) {
- Q.rear = NULL; // 如果队列为空，更新队尾指针
- }
- free(temp);
- }
- // GetFront: 获取队列的队头元素，但不删除该元素
- void GetFront(LinkQueue Q, ElemType &e) {
- if (Q.front == NULL) {
- printf("队列空\n");
- return;
- }
- e = Q.front->data; // 获取队头元素
- }
假设有一个洗碗机，它需要根据不同的顺序来处置处罚碗碟。这个问题涉及到两个部门：清洗和列队。当碗碟进洗碗机时，它们是按先辈先出（FIFO）的顺序进入的。然而，清洗时，洗碗机只能后进先出（LIFO）的顺序举行处置处罚。也就是说，洗碗机必须清洗最后进入的碗碟，然后才清洗前面的碗碟。
使用一个队列来模拟碗碟的进入顺序，而使用一个栈来模拟洗碗机清洗的顺序。
- 碗碟进入洗碗机：用户将碗碟依次放入洗碗机，这部门用一个队列来模拟。每个碗碟被按顺序到场队列。
- 清洗顺序：由于洗碗机必须按照“后进先出”的顺序清洗碗碟，可以将队列中的碗碟转移到栈中，然后按栈的顺序举行清洗。
- 清洗过程：从栈中弹出碗碟并清洗，直到栈为空。
- from collections import deque
- class Dishwasher:
- def __init__(self):
- self.queue = deque() # 用队列存储碗碟进入顺序
- self.stack = [] # 用栈模拟清洗顺序
- def add_dish(self, dish):
- # 把碗碟按顺序放入队列
- self.queue.append(dish)
- print(f"添加碗碟：{dish}")
- def start_washing(self):
- # 把队列中的碗碟转移到栈中（洗碗机需要后进先出的顺序）
- while self.queue:
- dish = self.queue.popleft()
- self.stack.append(dish)
-
- print("开始清洗碗碟：")
- # 按栈的顺序清洗碗碟（后进先出）
- while self.stack:
- dish = self.stack.pop()
- print(f"正在清洗：{dish}")
- # 使用示例：
- dishwasher = Dishwasher()
- dishwasher.add_dish("碗1")
- dishwasher.add_dish("碟1")
- dishwasher.add_dish("杯子1")
- # 开始清洗
- dishwasher.start_washing()
清洗顺序：由于洗碗机必须后进先出（LIFO），我们把队列中的碗碟依次转移到栈中，然后按栈的顺序清洗：先清洗最后放入的“杯子1”，然后是“碟1”，最后是“碗1”。
递归程序筹划的基本方法(分治法、减治法)
递归程序筹划的基本方法，包括分治法和减治法。其中，分治法递归的结构为“基本项+归纳项”。详细而言：
基本项：递归的停止条件，当问题足够简单时，直接返回结果。
归纳项：通过将问题分解为更小的子问题来解决，并递归地调用同样的方法来处置处罚这些子问题，直到满足基本项条件。
分治法递归：基本项+归纳项。
阶乘计算：
- long Fact(long n) {
- if (n == 0) return 1; // 基本项
- else return n * Fact(n - 1); // 归纳项
- }
归纳项：当 n > 0 时，返回 n * Fact(n - 1)，通过递归调用计算阶乘。
这种结构很适合解决分治法问题，即通过递归将大问题分解成小问题，再逐步解决。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
