栈与队列 408相关

栈与队列

一、栈的全面解析

（一）栈的基本概念

栈（Stack）作为一种特殊的线性表，其核心特性是遵循后进先出（Last In First Out，LIFO）原则。想象一个垂直放置的容器，只能在顶端进行元素的插入与移除操作，这个顶端就是所谓的栈顶（top），而底部则为栈底（bottom）。例如，一摞叠放的餐盘，最后放置上去的餐盘总是最先被取用，最先放置的餐盘则在最底部，最后才会被拿到，这生动地诠释了栈的工作原理。在日常生活中，浏览器的后退功能便是栈应用的典型实例。每访问一个新网页时，该网页信息就被“压入”栈中，当点击后退按钮时，从栈顶取出最近一次压入的网页信息，从而实现页面的回退浏览。

（二）栈的物理存储结构

1. 顺序存储
   • 在顺序存储结构下，栈通常借助数组来实现。通过定义一个固定大小的数组来容纳栈元素，并使用一个变量（如 top）来指示栈顶元素的位置。例如，在 C 语言中，可以如下定义一个顺序栈结构体：

#include <stdio.h>
#include <stdlib.h>

// 定义栈的最大容量
#define MAX_SIZE 100

// 栈结构体
typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

• 初始化时，将 top 设置为 -1，表示栈为空。当有元素入栈时，top 自增 1，并将元素存储在 data[top] 位置；出栈时，先取出 data[top] 的元素，然后 top 自减 1。这种顺序存储方式的优点是访问元素速度快，因为可以直接通过数组下标定位元素。然而，其缺点也较为明显，由于数组大小固定，一旦栈元素数量超过数组容量，就可能引发栈溢出问题，且在栈元素频繁进出时，可能需要进行大量的数据移动操作。例如，在一个深度优先搜索（DFS）算法中，如果递归调用层级过深，而使用顺序栈来存储递归状态，就可能因栈空间不足导致程序出错。

2. 链式存储
   • 链式存储的栈通过链表来构建。每个节点包含数据域和指向下一个节点的指针域。在这种结构中，栈顶即为链表的头节点。以 C 语言为例，节点结构体可定义为：

typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode;

• 入栈操作就是在链表头部插入新节点，出栈操作则是删除链表头部节点。链式存储的栈不存在固定大小的限制，能够根据需要动态分配内存空间，有效地避免了顺序存储中可能出现的栈溢出问题。但是，由于需要额外的指针域来维护节点间的链接关系，其空间开销相对较大，并且在访问栈中特定位置元素时，需要从栈顶（链表头）开始遍历，时间复杂度相对较高。例如，在实现一个表达式求值算法时，如果采用链式栈来存储操作数和运算符，能够灵活处理各种复杂表达式，而不用担心栈容量不足的问题。

（三）栈的操作实现

1. C 语言实现

// 初始化栈
void InitStack(Stack *s) {
    s->top = -1;
}

// 判断栈是否为空
int IsEmpty(Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
int IsFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

// 入栈操作
void Push(Stack *s, int value) {
    if (IsFull(s)) {
        printf("栈已满，无法入栈\n");
        return;
    }
    s->top++;
    s->data[s->top] = value;
}

// 出栈操作
int Pop(Stack *s) {
    if (IsEmpty(s)) {
        printf("栈为空，无法出栈\n");
        return -1;
    }
    int value = s->data[s->top];
    s->top--;
    return value;
}

// 获取栈顶元素
int Peek(Stack *s) {
    if (IsEmpty(s)) {
        printf("栈为空，无栈顶元素\n");
        return -1;
    }
    return s->data[s->top];
}

2. Java 语言实现

class Stack {
    private int[] data;
    private int top;
    private static final int MAX_SIZE = 100;

    // 构造函数，初始化栈
    public Stack() {
        data = new int[MAX_SIZE];
        top = -1;
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return top == -1;
    }

    // 判断栈是否已满
    public boolean isFull() {
        return top == MAX_SIZE - 1;
    }

    // 入栈操作
    public void push(int value) {
        if (isFull()) {
            System.out.println("栈已满，无法入栈");
            return;
        }
        top++;
        data[top] = value;
    }

    // 出栈操作
    public int pop() {
        if (isEmpty()) {
            System.out.println("栈为空，无法出栈");
            return -1;
        }
        int value = data[top];
        top--;
        return value;
    }

    // 获取栈顶元素
    public int peek() {
        if (isEmpty()) {
            System.out.println("栈为空，无栈顶元素");
            return -1;
        }
        return data[top];
    }
}

（四）栈的应用

1. 函数调用栈
   • 在程序运行期间，当一个函数调用另一个函数时，系统会创建一个函数调用栈。将当前函数的执行状态信息（如局部变量、返回地址等）压入栈中。例如，在递归函数执行过程中，每一次递归调用都会将当前层的参数和局部变量等信息压入栈。以计算斐波那契数列的递归函数为例：

int Fibonacci(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

• 在计算 Fibonacci(5) 时，首先将 Fibonacci(5) 的状态信息压入栈，然后在计算 Fibonacci(4) 和 Fibonacci(3) 等过程中，不断将相应的状态压入栈。当递归到 Fibonacci(0) 和 Fibonacci(1) 时开始返回，从栈顶依次弹出之前压入的状态信息并进行计算，最终得到 Fibonacci(5) 的结果。如果递归深度过大，可能会导致栈溢出，这也是使用递归时需要注意的问题。

2. 表达式求值
   • 中缀表达式求值是栈应用的经典场景。例如对于表达式“3 + 4 * 2 / ( 1 - 5 )”，可以利用两个栈，一个操作数栈和一个运算符栈来实现求值。扫描表达式时，数字直接压入操作数栈，运算符则根据其优先级以及栈顶运算符的情况进行入栈或出栈操作，并对操作数栈的栈顶元素进行相应运算。比如，先扫描到“3”，压入操作数栈；再扫描到“+”，压入运算符栈；接着扫描到“4”，压入操作数栈；扫描到“”，因为“”优先级高于“+”，所以“”压入运算符栈；扫描到“2”，压入操作数栈；此时扫描到“/”，“/”优先级高于“”，“/”压入运算符栈；扫描到“(”，“(”压入运算符栈；扫描到“1”，压入操作数栈；扫描到“-”，“-”压入运算符栈；扫描到“5”，压入操作数栈；扫描到“)”，则将运算符栈中“-”对应的操作数栈顶两个元素（1 和 5）取出进行“-”运算，结果 -4 压入操作数栈，运算符栈中“-”出栈；然后继续处理运算符栈中剩余运算符与操作数栈顶元素的运算，最终得到表达式的值。

二、队列的深度解读

（一）队列的基本概念

队列（Queue）是一种遵循先进先出（First In First Out，FIFO）原则的线性表。可以类比为人们在银行排队办理业务的场景，先到达的客户先接受服务并离开队列，后到达的客户依次在队列末尾排队等待。队列有队头（front）和队尾（rear）两个关键端点，元素从队尾进入队列，从队头离开队列。在计算机操作系统的任务调度中，多个任务按照到达的先后顺序排队等待 CPU 资源，先到达的任务先被 CPU 处理，这充分体现了队列的先进先出特性。

（二）队列的物理存储结构

1. 顺序存储
   • 顺序存储的队列利用数组来实现。定义一个数组来存储队列元素，并使用两个变量 front 和 rear 分别表示队头和队尾元素的索引。例如，在 C 语言中：

#include <stdio.h>
#include <stdlib.h>

// 队列的最大容量
#define MAX_SIZE 100

// 队列结构体
typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Queue;

• 初始化时，front 和 rear 通常都设置为 0。入队操作时，将元素存储在 data[rear] 位置，然后 rear 自增 1（在循环队列中，需要考虑 rear 到达数组末尾后的处理，通常采用取模运算）；出队操作时，取出 data[front] 的元素，然后 front 自增 1（同样在循环队列中需取模）。顺序存储的队列访问元素较为高效，但存在队列假溢出问题。例如，当 rear 到达数组末尾，即使队列前端还有空位，也可能被误判为已满。为解决此问题，常采用循环队列的形式。

2. 链式存储
   • 链式存储的队列通过链表构建。包含一个头指针指向队头节点，一个尾指针指向队尾节点。节点结构体类似栈的链式结构：

typedef struct QueueNode {
    int data;
    struct QueueNode *next;
} QueueNode;

• 入队操作就是在链表尾部添加新节点，若队列为空，则头指针和尾指针都指向新节点；出队操作则是删除队头节点，并更新头指针。链式队列的优点是可以灵活地动态分配内存，不存在固定大小的限制，适用于元素数量不确定且可能较大的情况。但由于需要维护指针，其操作的时间和空间复杂度相对顺序队列略高。例如，在一个网络数据传输缓存队列中，如果数据流量不稳定，采用链式队列可以更好地适应数据量的动态变化，避免因队列容量限制导致数据丢失。

（三）特殊队列 - 循环队列

1. 概念与原理
   • 循环队列是为了解决顺序队列的假溢出问题而设计的。它将数组视为一个环形结构，当队尾指针 rear 到达数组末尾时，若数组前端还有空位，则可将新元素绕回数组开头存放。在循环队列中，判断队列空的条件是 front == rear，而判断队列满的条件通常有两种方式，一种是牺牲一个存储单元，即 (rear + 1) % MAX_SIZE == front；另一种是设置一个计数器来记录队列中元素的数量。例如，在一个循环队列中，假设 MAX_SIZE = 5，初始时 front = rear = 0，依次入队元素 1、2、3，此时 rear = 3，front = 0。当再入队一个元素 4 时，rear = (3 + 1) % 5 = 4。如果此时出队一个元素，front = (0 + 1) % 5 = 1，队列依然可以正常工作，不会因为 rear 到达末尾而出现假溢出情况。
2. 操作实现与计算
   • 以下是 C 语言中循环队列的基本操作实现：

// 初始化循环队列
void InitQueue(Queue *q) {
    q->front = 0;
    q->rear = 0;
}

// 判断循环队列是否为空
int IsEmptyQueue(Queue *q) {
    return q->front == q->rear;
}

// 判断循环队列是否已满（牺牲一个存储单元法）
int IsFullQueue(Queue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

// 入队操作（循环队列）
void Enqueue(Queue *q, int value) {
    if (IsFullQueue(q)) {
        printf("队列已满，无法入队\n");
        return;
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
}

// 出队操作（循环队列）
int Dequeue(Queue *q) {
    if (IsEmptyQueue(q)) {
        printf("队列为空，无法出队\n");
        return -1;
    }
    int value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return value;
}

• 在循环队列中，一些相关的计算也很重要。例如，计算队列中当前元素的数量，可以使用公式 (rear - front + MAX_SIZE) % MAX_SIZE（当采用牺牲一个存储单元判断队列满的方式时）。另外，在设计循环队列的应用场景时，需要根据实际需求合理确定队列的最大容量，以平衡内存使用和队列操作的效率。例如，在一个实时数据处理系统中，如果数据产生速度较快且处理速度相对较慢，需要设置较大的循环队列容量来缓存数据，但过大的容量可能会导致内存占用过高，影响系统整体性能。

（四）队列的应用

1. 广度优先搜索（BFS）
   • 在图的遍历算法中，广度优先搜索使用队列来存储待访问的节点。从起始节点开始，将其入队，然后不断取出队头节点，访问其相邻节点并将未访问过的相邻节点入队，直到队列为空，这样可以按照距离起始节点由近及远的顺序遍历图中的节点。例如，在一个迷宫求解问题中，将迷宫的入口作为起始节点，每个节点表示迷宫中的一个位置，相邻节点就是通过上下左右移动可以到达的位置。使用队列进行广度优先搜索，可以找到从入口到出口的最短路径。具体操作时，先将入口节点入队，然后循环执行出队操作，对出队节点的相邻节点进行判断，如果是未访问过的通道节点，则将其入队，并记录其前驱节点，直到队列为空或者找到出口节点。通过回溯前驱节点，就可以得到从入口到出口的最短路径。
2. 打印机任务管理
   • 在多任务操作系统中，打印机任务可以看作是一个队列。多个打印任务按照提交的先后顺序排队，打印机依次处理队列中的任务，先提交的任务先被打印输出。例如，在一个办公室网络打印环境中，不同用户提交的打印文档形成一个打印任务队列。打印机从队列头部取出任务进行打印，当一个任务完成后，继续处理队列中的下一个任务。这确保了打印任务的公平性和顺序性，避免了任务混乱和插队现象。同时，可以根据打印机的性能和任务的紧急程度等因素，对队列进行一些优化操作，如设置优先级队列，让紧急任务优先处理等。

无论是栈还是队列，它们都是计算机科学中非常基础且重要的数据结构。在实际的编程和算法设计中，根据不同的需求合理选择和运用它们，能够有效地解决各种复杂的问题，提高程序的效率和性能。对于深入学习数据结构与算法的人来说，熟练掌握栈和队列的相关知识，包括它们的各种存储结构、特殊类型以及应用场景等，是迈向更高层次的重要一步，尤其对于考研复习中的数据结构部分，这些知识更是重点考查内容，需要深入理解并能够灵活运用到各类算法题的解答中。