【Java-数据结构篇】Java 中栈和队列：构建程序逻辑的关键数据结构基石

一、引言

1. 栈与队列在编程中的角色定位

栈和队列作为两种基本的数据结构，在众多编程场景中都有着独特的地位。它们为数据的有序处理提供了简单而有效的模型。栈的后进先出特性使其在处理函数调用、表达式求值以及资源管理等方面表现出色。例如，当一个函数调用另一个函数时，当前函数的执行状态信息（如局部变量、返回地址等）会被压入栈中，当被调用函数执行完毕后，再从栈中弹出这些信息，从而保证函数调用的正确顺序和状态恢复。队列的先进先出原则则适用于模拟现实世界中的排队现象，如任务调度、消息传递等。在任务调度系统中，新提交的任务按照到达的顺序依次进入队列，然后按照队列的顺序依次被处理，这样可以保证任务处理的公平性和顺序性。总之，栈和队列帮助程序员以简洁、有序的方式组织和处理数据，是解决许多编程问题不可或缺的工具。

二、栈

1. 栈的概念与特性 1.1后进先出（LIFO）原理阐释

栈是一种特殊的数据结构，它就像一个只能在一端进行操作的容器。数据元素只能从栈顶进入（入栈操作，push），也只能从栈顶取出（出栈操作，pop）。这就意味着最后进入栈的元素会最先被取出，最先进入栈的元素则最后被取出，遵循后进先出的原则。例如，假设有一个栈，依次将元素 1、2、3 入栈，那么出栈的顺序就是 3、2、1。这种特性使得栈在很多需要逆序处理数据或者记录操作顺序的场景中非常有用。

栈在现实⽣活中的例⼦

1.2栈顶与栈底的定义及意义

栈顶是栈中进行数据操作的一端，是数据元素进入和离开栈的位置。而栈底则是栈的另一端，是最先进入栈的元素所在的位置。栈顶的位置会随着入栈和出栈操作而不断变化，而栈底相对固定。明确栈顶和栈底的概念对于理解栈的操作和实现至关重要，在代码实现中，通常会使用一个指针或者索引来表示栈顶的位置，以便进行入栈、出栈等操作的控制。

2. Java 中栈的实现方式

2.1 使用内置的 Stack 类 2.1.1 Stack 类的基本方法与操作示例

Java 中的 java.util.Stack 类提供了方便的栈操作方法。例如，push(E item)方法用于将元素压入栈顶，pop() 方法用于移除并返回栈顶元素，peek() 方法则只是返回栈顶元素但不将其移除。以下是一个简单的示例代码：

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println("栈顶元素: " + stack.peek()); 
        System.out.println("弹出的元素: " + stack.pop()); 
        System.out.println("栈是否为空: " + stack.empty()); 
    }
}

2.1.2 深入剖析 Stack 类的继承结构与局限性

2.2 基于数组自行实现栈 2.2.1 数组实现栈的设计思路与代码框架搭建

class ArrayStack {
    private int[] stackArray;
    private int top;

    public ArrayStack(int capacity) {
        stackArray = new int[capacity];
        top = -1;
    }

    // 入栈操作
    public void push(int item) {
        // 待实现
    }

    // 出栈操作
    public int pop() {
        // 待实现
        return -1; 
    }

    // 查看栈顶元素
    public int peek() {
        // 待实现
        return -1; 
    }

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

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

2.2.2 入栈（push）、出栈（pop）、查看栈顶元素（peek）等核心方法的详细实现与讲解

• 入栈（push）方法实现：

public void push(int item) {
    if (isFull()) {
        throw new StackOverflowError("栈已满");
    }
    top++;
    stackArray[top] = item;
}

首先检查栈是否已满，如果已满则抛出栈溢出异常。然后将栈顶索引加 1，并将元素放入栈顶索引对应的数组位置。

• 出栈（pop）方法实现：

public int pop() {
    if (isEmpty()) {
        throw new EmptyStackException();
    }
    int item = stackArray[top];
    top--;
    return item;
}

先判断栈是否为空，为空则抛出空栈异常。取出栈顶元素，将栈顶索引减 1，并返回取出的元素。

• 查看栈顶元素（peek）方法实现：

public int peek() {
    if (isEmpty()) {
        throw new EmptyStackException();
    }
    return stackArray[top];
}

判断栈是否为空，若为空则抛出异常，否则直接返回栈顶元素但不改变栈顶索引。 2.2.3处理栈空与栈满的边界情况策略探讨

对于栈空的情况，在出栈和查看栈顶元素操作时需要进行判断并抛出相应的异常，以避免程序出现错误。而对于栈满的情况，在入栈操作时进行判断，当栈已满时，可以选择抛出异常或者采取动态扩容策略。如果选择动态扩容，可以创建一个更大容量的新数组，将原数组中的元素复制到新数组中，然后将新数组赋值给栈数组，并更新相关的索引和容量信息。

2.3基于链表实现栈 2.3.1链表节点的定义与构造

class StackNode {
    int data;
    StackNode next;

    public StackNode(int data) {
        this.data = data;
        this.next = null;
    }
}

定义一个链表节点类，包含数据域和指向下一个节点的指针域。每个节点存储栈中的一个元素，通过指针连接形成栈的链表结构。 2.3.2利用链表构建栈的逻辑流程与代码实现要点

使用链表实现栈时，需要维护一个指向栈顶节点的指针。入栈操作时，创建一个新节点，将新节点的 next指针指向当前栈顶节点，然后更新栈顶指针为新节点；出栈操作时，先保存栈顶节点的数据，然后将栈顶指针指向栈顶节点的下一个节点，并释放原来的栈顶节点。以下是基于链表实现栈的主要代码：

class LinkedStack {
    private StackNode top;

    // 入栈操作
    public void push(int item) {
        StackNode newNode = new StackNode(item);
        newNode.next = top;
        top = newNode;
    }

    // 出栈操作
    public int pop() {
        if (top == null) {
            throw new EmptyStackException();
        }
        int item = top.data;
        top = top.next;
        return item;
    }

    // 查看栈顶元素
    public int peek() {
        if (top == null) {
            throw new EmptyStackException();
        }
        return top.data;
    }

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

2.3.3对比数组实现与链表实现栈的性能差异与适用场景分析

• 性能差异：
  • 空间复杂度：数组实现的栈在创建时需要指定固定的容量，如果栈中的元素数量超过容量则可能需要进行扩容操作，而扩容可能涉及到大量元素的复制，比较耗时。链表实现的栈则不需要预先指定容量，根据需要动态分配节点内存，空间利用更加灵活，但每个节点需要额外的指针空间来存储下一个节点的引用。
  • 时间复杂度：对于入栈、出栈和查看栈顶元素操作，数组实现和链表实现的平均时间复杂度都是

  O(1)

  。但在数组实现中，如果需要扩容，扩容操作可能会使一次入栈操作的时间复杂度变为

  O(n)

  （

  n

  为当前栈中的元素数量）。而链表实现则不存在这种情况，但链表在内存中的存储可能不是连续的，这可能会导致缓存不友好，在一些对性能要求极高且数据量较大的场景下可能会有一定影响。

• 适用场景：
  • 数组实现栈：适用于已知栈的最大容量且数据量相对稳定的场景，例如编译器中的语法分析栈，因为在编译过程中通常可以预估表达式的最大嵌套深度，从而确定栈的大小。
  • 链表实现栈：适用于数据量不确定且可能频繁变动的场景，例如实现一个浏览器的后退栈，用户的浏览历史长度是不确定的，链表可以方便地动态添加和删除节点。 –

三、队列

1. 队列的概念与特性 1.1先进先出（FIFO）原则解读

队列是一种线性数据结构，它遵循先进先出的原则。就如同日常生活中的排队，先进入队列的元素会先被处理。数据元素从队尾进入队列（入队操作，enqueue），在队头被取出（出队操作，dequeue）。例如，在一个售票系统中，顾客按照到达的先后顺序排队购票，先到的顾客先购票离开，这就很好地体现了队列的先进先出特性。这种特性使得队列在处理顺序性任务、资源分配以及模拟现实中的排队过程等方面有着广泛的应用。

• 1.2队头与队尾的概念及在队列操作中的作用

队头是队列中最先进入的元素所在的位置，是出队操作发生的地方。队尾则是新元素进入队列的位置。在队列的操作过程中，入队操作会使队尾指针发生变化，新元素被添加到队尾；出队操作则会使队头指针移动，队头元素被移除。明确队头和队尾的概念对于正确实现和理解队列的各种操作至关重要，无论是基于数组还是链表来构建队列，都需要准确地维护队头和队尾的状态信息。

2. Java 中队列的实现途径 2.1使用内置的 Queue 接口及相关实现类（如 LinkedList 实现队列）

2.1.1Queue 接口的主要方法（add、offer、remove、poll、peek 等）介绍与使用示例

Java 中的 java.util.Queue 接口提供了一组用于操作队列的方法。其中：

• add(E e)：将指定元素插入队列，如果队列已满则抛出异常。例如：Queue<Integer> queue = new LinkedList<>(); queue.add(1);
• offer(E e)：将指定元素插入队列，如果队列已满则返回 false。Queue<Integer> queue = new LinkedList<>(); boolean success = queue.offer(2);
• remove()：获取并移除队头元素，如果队列为空则抛出异常。Integer element = queue.remove();
• poll()：获取并移除队头元素，如果队列为空则返回 null。Integer element = queue.poll();
• peek()：获取但不移除队头元素，如果队列为空则返回 null。Integer frontElement = queue.peek();

以下是一个综合使用这些方法的示例：

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("Apple");
        queue.offer("Banana");
        queue.offer("Cherry");

        System.out.println("队头元素: " + queue.peek()); 
        System.out.println("移除的元素: " + queue.poll()); 
        System.out.println("队列是否为空: " + queue.isEmpty()); 
    }
}

• 2.1.2LinkedList 作为队列实现的底层原理剖析

LinkedList 类实现了 Queue 接口，它内部通过链表结构来存储元素。当使用 LinkedList 作为队列时，队头对应链表的头节点，队尾对应链表的尾节点。入队操作就是在链表的尾部添加一个新节点，出队操作则是移除链表的头节点。由于链表的特性，插入和删除操作在平均情况下时间复杂度为

，这使得 LinkedList作为队列实现时在入队和出队操作上具有较好的性能表现。然而，由于链表需要额外的指针来维护节点之间的关系，相比于基于数组的实现，它在空间上会有一定的额外开销。

• 2.1.3队列操作中的异常处理机制探讨（如队列空时的操作异常）

• 在使用队列方法时，需要注意对队列空和队列满的情况进行处理。例如，当使用 remove 方法从空队列中获取元素时，会抛出 NoSuchElementException 异常；而使用 poll 方法从空队列获取元素时则返回 null。在实际编程中，可以根据具体需求选择合适的方法并进行相应的异常处理。如果希望在队列空时得到明确的提示而不是异常，可以优先选择poll和peek方法，并结合isEmpty` 方法来判断队列状态，例如：

Queue<Integer> queue = new LinkedList<>();
// 一系列入队和出队操作后
if (!queue.isEmpty()) {
    Integer element = queue.poll();
    // 处理元素
} else {
    System.out.println("队列已空");
}

2.2基于数组实现循环队列

2.2.1 数组表示循环队列的关键数据结构设计与变量定义

通常需要定义一个数组来存储队列元素，以及两个指针变量，一个表示队头指针 front，一个表示队尾指针 rear。还需要记录队列的最大容量 capacity。例如：

class CircularQueue {
    private int[] queueArray;
    private int front;
    private int rear;
    private int capacity;

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        queueArray = new int[capacity];
        front = 0;
        rear = 0;
    }

2.2.2入队（enqueue）、出队（dequeue）操作的代码实现及循环处理逻辑解析

• 入队（enqueue）操作：

public boolean enqueue(int item) {
    if ((rear + 1) % capacity == front) {
        return false; // 队列已满
    }
    queueArray[rear] = item;
    rear = (rear + 1) % capacity;
    return true;
}

首先检查队列是否已满，通过判断队尾指针的下一个位置（循环意义上）是否等于队头指针来确定。如果不满，则将元素放入队尾指针指向的位置，并更新队尾指针，使其指向下一个可用位置（循环处理）。

• 出队（dequeue）操作：

public int dequeue() {
    if (front == rear) {
        throw new IllegalStateException("队列已空");
    }
    int item = queueArray[front];
    front = (front + 1) % capacity;
    return item;
}

先判断队列是否为空，若为空则抛出异常。然后取出队头元素，更新队头指针指向下一个元素（循环处理）。

2.2.3计算循环队列的有效元素个数、判断队列空与满的方法讲解

• 计算有效元素个数：

public int size() {
    return (rear - front + capacity) % capacity;
}

通过队尾指针和队头指针的相对位置计算队列中元素的数量，考虑了循环的情况。

• 判断队列空：

public boolean isEmpty() {
        return front == rear;
}

当队头指针和队尾指针相等时，队列中没有元素，即为空。

• 判断队列满：

public boolean isFull() {
        return (rear + 1) % capacity == front;
}

如入队操作中所述，通过队尾指针的下一个位置（循环意义上）与队头指针的关系判断队列是否已满。

2.3基于链表实现队列 2.3.1链表实现队列的入队与出队操作的具体代码实现细节

class LinkedQueue {
    private QueueNode front;
    private QueueNode rear;

    // 入队操作
    public void enqueue(int item) {
        QueueNode newNode = new QueueNode(item);
        if (rear == null) {
            front = newNode;
            rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }

    // 出队操作
    public int dequeue() {
        if (front == null) {
            throw new IllegalStateException("队列已空");
        }
        int item = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        return item;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return front == null;
    }
}

入队操作时，如果队列为空，新节点既是队头也是队尾；否则将新节点添加到队尾，并更新队尾指针。出队操作时，先判断队列是否为空，若不为空则取出队头元素，更新队头指针，如果出队后队列为空，则将队尾指针也置为 null。

2.3.2对比循环队列与链表队列在不同应用场景下的性能表现与资源消耗情况

• 性能表现：
  • 入队和出队操作：在平均情况下，循环队列和链表队列的入队和出队操作时间复杂度都为

  O(1)

  。但在最坏情况下，循环队列如果需要扩容（虽然相对较少发生），可能会涉及到数组元素的复制，时间复杂度会变为

  O(n)

  ；而链表队列不需要扩容操作，始终保持

  O(1)

  的时间复杂度。

  • 遍历操作：循环队列由于基于数组实现，可以通过索引快速访问任意位置的元素，遍历操作相对简单高效；链表队列遍历则需要从队头开始逐个节点访问，时间复杂度为

  O(n)

  。

• 资源消耗：
  • 空间复杂度：循环队列需要预先分配固定大小的数组空间，可能会存在空间浪费（如果队列实际元素数量远小于数组容量）或空间不足（需要扩容）的情况；链表队列则根据实际元素数量动态分配节点空间，不会有空间浪费，但每个节点需要额外的指针空间来存储下一个节点的引用。
• 应用场景：
  • 循环队列：适用于已知队列最大容量且对遍历操作有一定需求的场景，例如在一些嵌入式系统中的数据缓冲区管理，或者生产者 - 消费者模型中，当缓冲区大小固定且需要快速访问队列中的数据时。
  • 链表队列：适用于数据量不确定且频繁进行入队和出队操作的场景，例如在任务调度系统中，任务的数量和到达时间是不确定的，链表队列可以方便地动态添加和删除任务节点，而无需担心容量问题。

四、栈与队列的应用场景

1. 栈的应用实例

在程序执行过程中，当一个函数调用另一个函数时，系统会为每个函数调用创建一个栈帧，并将其压入函数调用栈。栈帧中包含了函数的局部变量、参数值、返回地址等信息。例如，考虑一个计算阶乘的递归函数：

public class Factorial {
    public static int factorial(int n) {
        if (n == 0 || n == 1) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }

    public static void main(String[] args) {
        int result = factorial(5);
        System.out.println(result);
    }
}

当调用 factorial(5) 时，首先会创建一个栈帧，将 n = 5 以及其他相关信息压入栈中。然后在函数内部又调用 factorial(4)，此时会创建一个新的栈帧并压入栈顶，依此类推。当 n 递减到 0 或 1 时，开始从栈顶依次弹出栈帧，并返回计算结果。每弹出一个栈帧，就会恢复上一层函数调用的执行环境，直到回到最初的 factorial(5) 调用处，最终得到阶乘的结果。这种机制保证了函数调用的顺序性和正确性，使得递归函数能够正确地执行多层嵌套调用，并在每层调用结束后正确地返回结果。

中缀表达式是我们常见的数学表达式形式，如 `3 + 4 * 2 / ( 1 - 5 )`。但计算机在求值时，后缀表达式（逆波兰表达式）更易于处理。例如，上述中缀表达式的后缀表达式为 `3 4 2 * 1 5 - / +`。利用栈可以实现中缀表达式到后缀表达式的转换以及后缀表达式的求值。

扫描中缀表达式，操作数直接输出，运算符则根据其优先级和栈的状态处理。当扫描到运算符时，如果栈为空或栈顶运算符为左括号，则将该运算符入栈；如果当前运算符优先级高于栈顶运算符优先级，则入栈；否则，将栈顶运算符弹出并输出，直到当前运算符优先级高于栈顶运算符优先级或栈为空，然后将当前运算符入栈。遇到左括号时入栈，遇到右括号时，将栈顶元素依次弹出并输出，直到遇到左括号并将左括号弹出。扫描结束后，将栈中剩余运算符依次弹出输出。

例如，对于表达式 3 + 4 * 2 / ( 1 - 5 )： - 扫描到 3，输出 3。 - 扫描到 +，入栈。 - 扫描到 4，输出 4。 - 扫描到 *，因为 * 优先级高于 +，入栈。 - 扫描到 2，输出 2。 - 扫描到 /，因为 / 优先级高于 *，入栈。 - 扫描到 (，入栈。 - 扫描到 1，输出 1。 - 扫描到 -，入栈。 - 扫描到 5，输出 5。 - 扫描到 )，将栈顶元素 - 弹出输出，然后将 ( 弹出。 - 扫描结束，将栈中剩余运算符 /、*、+ 依次弹出输出，得到后缀表达式 3 4 2 * 1 5 - / +。

• 后缀表达式求值： 扫描后缀表达式，操作数入栈，当扫描到运算符时，从栈中弹出两个操作数，进行相应运算，并将结果入栈。例如，对于后缀表达式 3 4 2 * 1 5 - / +：
  • 扫描到 3，入栈。
  • 扫描到 4，入栈。
  • 扫描到 2，入栈。
  • 扫描到 *，弹出 2 和 4，计算 4 * 2 = 8，将 8 入栈。
  • 扫描到 1，入栈。
  • 扫描到 5，入栈。
  • 扫描到 -，弹出 5 和 1，计算 1 - 5 = -4，将 -4 入栈。
  • 扫描到 /，弹出 -4 和 8，计算 8 / (-4) = -2，将 -2 入栈。
  • 扫描到 +，弹出 -2 和 3，计算 3 + (-2) = 1，得到最终结果。

浏览器的浏览历史可以看作是一个栈。当用户访问一个新页面时，该页面的 URL 被压入栈中。当用户点击后退按钮时，栈顶的 URL 被弹出，浏览器加载该 URL 对应的页面，实现后退功能。而前进功能则可以通过维护一个额外的栈来实现。当用户点击后退按钮时，将当前 URL 压入前进栈；当用户点击前进按钮时，从前进栈中弹出 URL 并加载对应的页面。例如，用户依次访问页面 A、B、C，此时浏览历史栈中从栈底到栈顶为 A、B、C。当用户点击后退按钮两次，栈变为 A，并且 C、B依次被压入前进栈。如果此时用户点击前进按钮，浏览器将从前进栈中弹出 B 并加载页面 B。

2. 队列的应用实例

在任务调度系统中，有多个任务需要按照一定的顺序执行。这些任务可以被看作是队列中的元素，按照提交的先后顺序进入队列。例如，在一个操作系统的任务调度器中，进程可能会请求CPU 时间片。当有多个进程同时请求时，它们会被放入一个就绪队列中，调度器按照队列的先进先出顺序，依次为每个进程分配 CPU时间片，使得每个进程都能得到公平的执行机会。这种基于队列的任务调度机制保证了任务处理的顺序性和公平性，避免了某些任务长时间等待而得不到执行的情况。

在分布式系统中，不同的组件可能分布在不同的服务器或进程中，它们之间需要进行通信和协作。消息队列作为一种中间件，利用队列的特性实现了解耦和异步通信。例如，一个电商系统中，订单处理模块、库存管理模块和物流配送模块是相互独立的。当有新订单生成时，订单处理模块将订单信息放入消息队列，而不是直接调用库存管理模块和物流配送模块。库存管理模块和物流配送模块从消息队列中获取订单信息并进行相应处理。这样，即使某个模块出现故障或性能瓶颈，也不会影响其他模块的正常运行，实现了解耦。同时，由于消息队列的异步特性，订单处理模块不需要等待库存管理模块和物流配送模块处理完成，提高了系统的整体性能和响应速度。

在多用户共享的打印环境中，多个打印任务会被提交到打印服务器。这些打印任务可以用队列来管理。当用户提交打印任务时，任务被添加到打印队列的队尾。打印服务器按照队列的先进先出顺序，依次从队头取出打印任务并进行打印。例如，在一个办公室网络中，有多个员工同时提交打印文档的任务。这些任务被排队，先提交的任务先被打印。可以通过队列的相关操作，如查看队列长度（即等待打印的任务数量）、暂停或取消特定的打印任务等，来实现对打印任务队列的有效管理，提高打印资源的利用率和打印服务的质量。

五、栈与队列的性能分析与优化

1. 时间复杂度分析

栈操作时间复杂度： 对于基于数组实现的栈，在理想情况下（不考虑扩容），入栈（push）和出栈（pop）操作的时间复杂度均为

。这是因为它们仅仅涉及到对数组特定位置的元素操作以及栈顶指针的更新，这些操作的执行时间不随栈中元素数量的增加而显著增加。例如，将一个元素压入一个已有

个元素的栈中，只需将该元素放置在数组的第

个位置（假设栈顶索引从 0开始），并更新栈顶指针，这个过程的时间消耗基本固定。 基于链表实现的栈，入栈和出栈操作同样平均时间复杂度为

。入栈时创建新节点并调整指针指向新节点作为栈顶，出栈时改变栈顶指针指向原栈顶节点的下一个节点并释放原栈顶节点，这些操作都能在常数时间内完成，与栈中元素的数量无关。

• 队列操作时间复杂度：
  • 在使用 LinkedList 实现 Queue 接口的队列中，入队（enqueue）和出队（dequeue）操作的平均时间复杂度也是

  O(1)

  。入队操作是在链表尾部添加节点，出队操作是移除链表头部节点，这两个操作在链表结构中都能高效地完成，不受队列长度的影响。

  • 对于基于数组实现的循环队列，入队和出队操作在正常情况下时间复杂度为

  O(1)

  。入队时只需将元素放置在队尾指针指向的位置，并更新队尾指针；出队时取出队头元素并更新队头指针，这些操作的执行时间相对固定。然而，当循环队列需要进行扩容操作时，时间复杂度会变为

  O(n)

  ，因为需要创建新的更大容量的数组，并将原数组中的元素复制到新数组中，其中

  n

  是当前队列中的元素数量。

数组实现的栈和队列在空间利用上相对高效，因为它们不需要额外的指针来存储元素之间的关系。但数组的大小在创建时通常需要预先确定，如果预估不准确，可能导致空间浪费或频繁扩容。例如，若创建一个容量为100 的数组来实现栈，但实际使用中栈中元素数量很少超过 10，那么就有大量的空间未被利用。而扩容操作会带来较大的时间开销，可能使原本

的入栈或入队操作在某次操作时变为

。 链表实现的栈和队列则具有更好的灵活性，能够根据实际需求动态地分配内存空间，不需要预先指定最大容量。但由于每个节点都需要额外的指针空间，所以在空间利用率上相对较低。而且，链表在内存中的存储不是连续的，这可能导致缓存不友好，在一些对性能要求极高且数据量较大的场景下，可能会影响整体性能。例如，在频繁进行入栈、出栈或入队、出队操作的情况下，如果 CPU 缓存不能有效地命中链表节点，可能会增加数据读取的时间。

2. 空间复杂度分析

• 数组实现：
  • 基于数组实现的栈和队列，其空间复杂度主要取决于数组的大小。如果预先分配的数组大小能够较好地适应实际存储需求，那么空间利用率较高。例如，对于一个已知最大元素数量为

  n

  的栈或队列，创建一个大小为

  n

  的数组来实现，其空间复杂度为

  O(n)

  。但如果实际使用中元素数量远小于数组容量，就会造成空间浪费。而且，在某些情况下，如循环队列的实现，为了区分队空和队满的状态，可能会浪费一个数组元素的空间。例如，一个容量为

  n

  的循环队列，最多只能存储

  n - 1

  个元素，此时其空间复杂度虽然仍为

  O(n)

  ，但实际有效利用空间略小于理论值。

• 链表实现：
  • 链表实现的栈和队列，空间复杂度取决于实际存储的元素数量。每个节点除了存储数据元素本身，还需要额外的指针空间来维护链表结构。对于一个包含

  n

  个元素的链表栈或队列，其空间复杂度为

  O(n)

  ，其中

  n

  是元素数量。由于链表节点的动态分配特性，不会出现像数组那样预先分配过多空间导致浪费的情况，但每个节点的指针空间开销在元素数量较大时也不可忽视。

• 动态数组扩容策略：
  • 一种常见的优化数组实现的栈和队列空间复杂度的策略是采用动态扩容机制。例如，在数组容量不足时，不是简单地创建一个固定倍数（如两倍）大小的新数组，而是采用更灵活的扩容方式。可以根据当前元素数量和历史增长趋势来确定新数组的大小。比如，当元素数量接近数组容量时，先计算出一个合适的增量，然后创建一个新的数组，其容量为原数组容量加上这个增量。这样可以在一定程度上避免过度扩容导致的空间浪费。另外，还可以考虑在扩容时对原数组中的元素进行重新整理，以提高空间利用率。例如，当栈或队列中的元素在扩容后只占用了新数组的一小部分空间时，可以将这些元素移动到数组的开头部分，减少后续操作中的空指针判断等额外开销。
• 链表节点的合理设计：
  • 对于链表实现的栈和队列，可以优化链表节点的结构设计来降低空间复杂度。例如，如果数据元素的类型是固定大小的基本数据类型（如整数），可以考虑将多个数据元素存储在一个节点中，减少节点数量从而减少指针的使用。但这种方式需要在操作的复杂性和空间利用率之间进行权衡，因为在入栈、出栈、入队、出队等操作时，可能需要更多的逻辑来处理多个数据元素在一个节点中的情况。另外，还可以对链表节点中的指针进行压缩存储，例如，如果指针只需要指向特定范围内的地址，可以使用更短的位表示来存储指针，从而节省空间。但这种方法需要对内存地址的分配和管理有更深入的理解和控制，并且可能会增加一些指针操作的复杂性。 3. 优化技巧与实践

• 避免栈溢出：
  • 在使用栈时，尤其是基于数组实现的栈，要合理预估栈的最大深度。如果是在递归函数中使用栈，要确保递归的终止条件能够在合理的深度内满足，避免无限递归导致栈溢出。例如，在计算斐波那契数列的递归实现中，如果不进行优化，递归深度会随着计算的数列项数增加而快速增长，容易导致栈溢出。可以通过使用迭代或者尾递归优化等方式来减少栈的使用深度。另外，对于基于数组实现的栈，如果采用动态扩容策略，要确保扩容机制的正确性和高效性，避免因扩容失败或不合理的扩容导致栈空间不足而溢出。
• 避免队列内存泄漏：
  • 在使用队列时，要确保对队列中的元素进行正确的管理，避免内存泄漏。例如，在使用基于链表实现的队列时，如果在出队操作中只是简单地移除了队头节点的引用，但没有释放节点所占用的内存，就会导致内存泄漏。应该在出队操作时，正确地释放队头节点及其相关资源。对于基于数组实现的循环队列，如果数组中的元素是对象类型，并且在队列操作过程中对象的生命周期管理不当，也可能导致内存泄漏。例如，当队列中的元素被取出后，如果没有正确地处理对象的引用，使得对象无法被垃圾回收机制回收，就会造成内存泄漏。因此，在设计队列的操作方法时，要考虑到元素的生命周期管理，确保在元素不再被队列使用时，能够及时释放相关资源。

• 分块处理与多栈/多队列协同：
  • 在大规模数据处理场景下，单一的栈或队列可能无法满足性能和内存的要求。可以采用分块处理的策略，将大规模数据分成多个较小的块，分别使用栈或队列进行处理。例如，在处理一个大型文件中的数据时，可以将文件分成多个较小的片段，每个片段使用一个独立的栈或队列进行处理，然后再将各个片段的处理结果进行合并。另外，还可以使用多栈或多队列协同工作的方式。例如，在一个复杂的数据处理流程中，可能需要根据数据的不同特性或处理阶段将数据分别放入不同的栈或队列中，然后在合适的时机进行数据的转移和合并。比如，在一个图像处理算法中，可以使用一个队列来存储待处理的图像块，然后根据图像块的特征将它们分别放入不同的栈中进行进一步的处理，如边缘检测栈、颜色调整栈等，最后再将处理后的结果合并成最终的图像。
• 利用并发与并行处理：
  • 在多核处理器环境下，可以利用并发或并行处理来优化栈和队列的操作。例如，可以创建多个线程，每个线程负责处理一个独立的栈或队列，从而提高数据处理的速度。但在并发或并行处理时，需要注意数据的一致性和同步问题。例如，在多个线程同时对一个共享的队列进行入队和出队操作时，需要使用合适的同步机制（如锁、信号量等）来确保操作的正确性，避免出现数据竞争和错误的结果。同时，还可以考虑使用无锁数据结构来实现栈和队列，这种数据结构通过使用原子操作和特殊的算法设计，能够在一定程度上避免传统锁机制带来的性能开销，提高并发性能。例如，在一些高性能的网络服务器中，使用无锁队列来处理大量的网络请求，可以有效地提高服务器的响应速度和吞吐量。

六、栈与队列的面试考点与常见问题解答

1. 面试中关于栈和队列的高频问题梳理

• 辅助栈法：
  • 思路：使用两个栈，一个主栈用于正常的元素存储和操作，另一个辅助栈用于存储当前主栈中的最小值。每当有元素压入主栈时，将其与辅助栈顶元素比较，如果该元素小于等于辅助栈顶元素，则将其压入辅助栈；否则，不操作辅助栈。当主栈出栈时，如果出栈元素等于辅助栈顶元素，则辅助栈也出栈。这样，辅助栈顶元素始终为当前主栈中的最小值，获取最小值操作时间复杂度为

  O(1)

  。例如：

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        if (stack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

• 差值法：
  • 思路：只使用一个栈，在栈中存储元素与当前最小值的差值。同时，使用一个变量记录当前最小值。当压入元素时，计算该元素与当前最小值的差值并压入栈中，如果该元素小于当前最小值，则更新当前最小值。出栈时，通过栈顶元素和当前最小值恢复出原元素值，并检查是否需要更新当前最小值。获取最小值操作时间复杂度为

  O(1)

  。例如：

class MinStack {
    private Stack<Integer> stack;
    private int minValue;

    public MinStack() {
        stack = new Stack<>();
        minValue = Integer.MAX_VALUE;
    }

    public void push(int val) {
        if (stack.isEmpty()) {
            minValue = val;
            stack.push(0);
        } else {
            int diff = val - minValue;
            stack.push(diff);
            if (diff < 0) {
                minValue = val;
            }
        }
    }

    public void pop() {
        int diff = stack.pop();
        if (diff < 0) {
            minValue = minValue - diff;
        }
    }

    public int top() {
        int diff = stack.peek();
        if (diff < 0) {
            return minValue;
        } else {
            return minValue + diff;
        }
    }

    public int getMin() {
        return minValue;
    }
}

• 数组实现循环队列高效方案：
  • 设计思路：使用一个数组来存储队列元素，并使用两个指针 front 和 rear 分别表示队头和队尾。为了区分队空和队满的情况，可以浪费一个数组元素的空间，即当 (rear + 1) % capacity == front 时表示队满，当 front == rear 时表示队空。入队操作时，将元素放入 rear 指针指向的位置，并更新 rear = (rear + 1) % capacity；出队操作时，取出 front 指针指向的元素，并更新 front = (front + 1) % capacity。例如：

class MyCircularQueue {
    private int[] queue;
    private int front;
    private int rear;
    private int capacity;

    public MyCircularQueue(int k) {
        capacity = k + 1;
        queue = new int[capacity];
        front = 0;
        rear = 0;
    }

    public boolean enqueue(int value) {
        if (isFull()) {
            return false;
        }
        queue[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }

    public boolean dequeue() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        return true;
    }

    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return queue[front];
    }

    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return queue[(rear - 1 + capacity) % capacity];
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }
}

• 优势分析：这种实现方式的优势在于入队和出队操作的平均时间复杂度为

，空间复杂度为

（其中

为队列的最大容量）。通过巧妙地利用数组下标取模运算来实现循环队列，避免了频繁的元素移动和数组扩容操作，提高了队列操作的效率。同时，通过浪费一个数组元素的空间来区分队空和队满的状态，简化了代码逻辑，使得队列的操作更加清晰和易于理解。

1. 问题解答与代码示例

• 最小栈代码讲解：
  • 在辅助栈法的 MinStack 类中，构造函数初始化两个栈。push 方法中，先将元素压入主栈，然后判断是否压入辅助栈，这保证了辅助栈顶始终是当前最小值。pop 方法中，先弹出主栈元素，再判断是否弹出辅助栈元素以维护最小值的正确性。top 方法直接返回主栈顶元素，getMin 方法返回辅助栈顶元素即最小值。
  • 在差值法的 MinStack 类中，构造函数初始化栈并设置初始最小值为最大整数值。push 方法计算差值并压入栈，同时更新最小值。pop 方法弹出差值并根据情况更新最小值。top 方法通过差值和当前最小值恢复出原元素值。getMin 方法直接返回当前最小值。
• 循环队列代码讲解：
  • MyCircularQueue 类的构造函数根据传入容量初始化数组，并设置队头和队尾指针。enqueue 方法先检查队列是否已满，未满则将元素放入队尾并更新队尾指针。dequeue 方法先检查队列是否为空，非空则更新队头指针。Front 方法返回队头元素，Rear 方法通过计算返回队尾元素。isEmpty 和 isFull 方法分别根据队头和队尾指针的关系判断队列状态。

• 数据结构理解与应用能力：
  • 通过考察最小栈和循环队列的设计，面试官期望应聘者深入理解栈和队列的基本概念、特性以及它们的变种应用。能够根据特定的需求（如常数时间获取最小值、高效的循环队列操作），选择合适的数据结构并设计出合理的算法来实现。这需要应聘者不仅熟悉栈和队列的常规操作，还能灵活运用数据结构知识解决实际问题，展示对数据结构的深入理解和创新应用能力。
• 代码实现与优化能力：
  • 要求应聘者提供详细的代码实现，考察其代码编写规范、逻辑清晰性以及对边界情况的处理能力。例如，在最小栈的实现中，正确处理辅助栈与主栈的同步操作，以及在循环队列中准确地实现队空和队满的判断逻辑。同时，通过对不同解法的比较和分析（如最小栈的辅助栈法和差值法），期望应聘者能够考虑到代码的效率、空间复杂度等因素，进行代码优化，展示其对算法性能的关注和优化能力。
• 问题解决与思维能力：
  • 这些问题往往不是简单地套用现成的代码模板就能解决的，需要应聘者具备较强的问题解决能力和思维能力。例如，在设计循环队列时，如何在有限的数组空间内实现高效的循环利用，需要应聘者深入思考并设计出巧妙的解决方案。通过回答这些问题，应聘者能够展示其分析问题、分解问题、提出解决方案并进行验证的能力，这是在实际编程工作中非常重要的技能，能够帮助应聘者快速适应复杂的项目开发需求并解决各种技术难题。

七、总结

总结栈与队列的核心概念、特性、实现方式以及应用场景等关键知识点

• 核心概念与特性：
  • 栈遵循后进先出（LIFO）原则，数据的操作主要集中在栈顶，就像一个只能从一端进出的容器，最后进入栈的元素最先被取出。队列则遵循先进先出（FIFO）原则，数据从队尾进入，从队头离开，如同排队等候的队伍，先到的先被服务。
• 实现方式：
  • 在 Java 中，栈可以使用内置的 Stack 类，但因其继承结构存在一些局限性；也可以基于数组或链表自行实现。基于数组实现时，需关注栈顶指针的变化、数组容量及扩容策略，处理好边界情况；基于链表实现则要构建合适的节点结构并维护好栈顶节点的引用。队列可以使用 java.util.Queue 接口及其相关实现类，如 LinkedList 实现队列较为便捷，其底层基于链表结构，入队和出队操作分别对应链表的尾部添加和头部移除。此外，还可基于数组实现循环队列，通过巧妙利用数组下标实现循环效果，减少空间浪费，但要精确处理队空和队满的判断条件；基于链表实现队列同样需要构建合适的节点并维护好队头和队尾的引用。
• 应用场景：
  • 栈在函数调用栈中用于保存函数调用的上下文信息，保证函数调用的顺序和状态恢复；在表达式求值中，可将中缀表达式转换为后缀表达式并求值，借助栈的特性实现运算符的优先级处理；在浏览器的后退与前进功能中，浏览历史的管理利用了栈的后进先出特性。队列在任务调度系统里，确保任务按照提交顺序依次执行，实现公平的资源分配；在消息队列中，用于分布式系统的解耦和异步通信，提高系统的灵活性和响应速度；在打印任务队列中，实现多用户打印任务的有序管理，提升打印资源的利用率和服务质量。

2道⾯试题

1. ⽤队列实现栈。题目链接
2. ⽤栈实现队列。题目链接