栈与队列学习笔记

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. 栈与队列的比较