栈与队列学习笔记

1. 栈（Stack） 1.1 栈的定义

栈是一种后进先出（Last In First Out, LIFO）的数据结构。栈中元素的插入和删除只在一端进行，该端称为栈顶（Top）。

1.2 栈的基本操作 入栈（Push）：将元素添加到栈顶。出栈（Pop）：从栈顶移除元素。栈顶元素（Peek/Top）：返回栈顶的元素，但不移除。检查栈是否为空（IsEmpty）：检查栈中是否有元素。 1.3 栈的实现

栈可以使用数组或链表来实现。

使用数组实现栈 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX_SIZE 100 typedef struct { int items[MAX_SIZE]; int top; } Stack; void init_stack(Stack* stack) { stack->top = -1; } bool is_empty(Stack* stack) { return stack->top == -1; } bool is_full(Stack* stack) { return stack->top == MAX_SIZE - 1; } void push(Stack* stack, int item) { if (is_full(stack)) { printf("Stack Overflow\n"); return; } stack->items[++stack->top] = item; } int pop(Stack* stack) { if (is_empty(stack)) { printf("Stack Underflow\n"); return -1; } return stack->items[stack->top--]; } int peek(Stack* stack) { if (is_empty(stack)) { printf("Stack is empty\n"); return -1; } return stack->items[stack->top]; } 使用链表实现栈 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef struct Node { int value; struct Node* next; } Node; typedef struct { Node* top; } Stack; void init_stack(Stack* stack) { stack->top = NULL; } bool is_empty(Stack* stack) { return stack->top == NULL; } void push(Stack* stack, int value) { Node* new_node = (Node*)malloc(sizeof(Node)); new_node->value = value; new_node->next = stack->top; stack->top = new_node; } int pop(Stack* stack) { if (is_empty(stack)) { printf("Stack Underflow\n"); return -1; } Node* temp = stack->top; int value = temp->value; stack->top = stack->top->next; free(temp); return value; } int peek(Stack* stack) { if (is_empty(stack)) { printf("Stack is empty\n"); return -1; } return stack->top->value; } 1.4 栈的应用 函数调用栈：用于跟踪函数调用和返回。表达式求值：用于中缀表达式转后缀表达式、表达式求值。括号匹配：用于检查括号是否匹配。 2. 队列（Queue） 2.1 队列的定义

队列是一种先进先出（First In First Out, FIFO）的数据结构。队列中元素的插入在一端进行，该端称为队尾（Rear），删除在另一端进行，该端称为队头（Front）。

2.2 队列的基本操作 入队（Enqueue）：将元素添加到队尾。出队（Dequeue）：从队头移除元素。队头元素（Peek/Front）：返回队头的元素，但不移除。检查队列是否为空（IsEmpty）：检查队列中是否有元素。 2.3 队列的实现

队列可以使用数组或链表来实现。

使用数组实现队列 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX_SIZE 100 typedef struct { int items[MAX_SIZE]; int front; int rear; } Queue; void init_queue(Queue* queue) { queue->front = -1; queue->rear = -1; } bool is_empty(Queue* queue) { return queue->front == -1; } bool is_full(Queue* queue) { return queue->rear == MAX_SIZE - 1; } void enqueue(Queue* queue, int item) { if (is_full(queue)) { printf("Queue Overflow\n"); return; } if (queue->front == -1) queue->front = 0; queue->items[++queue->rear] = item; } int dequeue(Queue* queue) { if (is_empty(queue)) { printf("Queue Underflow\n"); return -1; } int item = queue->items[queue->front]; if (queue->front >= queue->rear) { queue->front = -1; queue->rear = -1; } else { queue->front++; } return item; } int peek(Queue* queue) { if (is_empty(queue)) { printf("Queue is empty\n"); return -1; } return queue->items[queue->front]; } 使用链表实现队列 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef struct Node { int value; struct Node* next; } Node; typedef struct { Node* front; Node* rear; } Queue; void init_queue(Queue* queue) { queue->front = NULL; queue->rear = NULL; } bool is_empty(Queue* queue) { return queue->front == NULL; } void enqueue(Queue* queue, int value) { Node* new_node = (Node*)malloc(sizeof(Node)); new_node->value = value; new_node->next = NULL; if (queue->rear) { queue->rear->next = new_node; } queue->rear = new_node; if (queue->front == NULL) { queue->front = new_node; } } int dequeue(Queue* queue) { if (is_empty(queue)) { printf("Queue Underflow\n"); return -1; } Node* temp = queue->front; int value = temp->value; queue->front = queue->front->next; if (queue->front == NULL) { queue->rear = NULL; } free(temp); return value; } int peek(Queue* queue) { if (is_empty(queue)) { printf("Queue is empty\n"); return -1; } return queue->front->value; } 2.4 队列的应用 操作系统中的任务调度：用于管理进程和任务调度。广度优先搜索（BFS）：用于图的遍历。缓冲区：用于数据缓冲和流处理。 3. 栈与队列的比较 特性栈（Stack）队列（Queue）数据结构后进先出（LIFO）先进先出（FIFO）基本操作Push, Pop, Peek, IsEmptyEnqueue, Dequeue, Peek, IsEmpty插入位置栈顶队尾删除位置栈顶队头应用场景函数调用栈、表达式求值、括号匹配任务调度、广度优先搜索、缓冲区实现方式数组或链表数组或链表