数据结构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（获取栈顶元素）。
#define MAX_SIZE 100
typedef int ElemType;// 假设栈的元素类型为整型
typedef struct {
ElemType elem;
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;// 出栈
}
// GetTop: 获取栈顶元素，但不删除该元素
void GetTop(SqStack S, ElemType &e) {
if (S.top == -1) {
printf("栈空\n");
return;
}
e = S.elem;// 获取栈顶元素
}
链栈（Linked List-based Stack）
链栈使用链表作为底层存储结构。基本操纵与顺序栈雷同。
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;// 获取栈顶元素
}
链队列（Linked List-based Queue）
链队列使用链表作为底层存储结构，队列的头指针指向队头，尾指针指向队尾。
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() 碗碟进入顺序：碗1, 碟1, 杯子1，它们依次进入队列。
清洗顺序：由于洗碗机必须后进先出（LIFO），我们把队列中的碗碟依次转移到栈中，然后按栈的顺序清洗：先清洗最后放入的“杯子1”，然后是“碟1”，最后是“碗1”。
递归程序筹划的基本方法(分治法、减治法)
递归程序筹划的基本方法，包括分治法和减治法。其中，分治法递归的结构为“基本项+归纳项”。详细而言：
基本项：递归的停止条件，当问题足够简单时，直接返回结果。
归纳项：通过将问题分解为更小的子问题来解决，并递归地调用同样的方法来处置处罚这些子问题，直到满足基本项条件。
分治法递归：基本项+归纳项。
阶乘计算：
long Fact(long n) {
if (n == 0) return 1;// 基本项
else return n * Fact(n - 1);// 归纳项
}
基本项：当 n == 0 时，返回 1。
归纳项：当 n > 0 时，返回 n * Fact(n - 1)，通过递归调用计算阶乘。
这种结构很适合解决分治法问题，即通过递归将大问题分解成小问题，再逐步解决。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]