Java数据结构专题解析之栈和队列的实现

什么是栈和队列？

在计算机科学中，栈（Stack）和队列（Queue）都是常见的数据结构，用于解决许多问题。它们都是线性数据结构，但它们的元素访问顺序不同。

• 栈是先进后出（Last In First Out，LIFO）的结构，即最后放入栈中的元素最先被访问。
• 队列是先进先出（First In First Out，FIFO）的结构，即最早放入队列中的元素最先被访问。

举个例子，我们生活中很常见的一个栈就是桶，不断往桶里踩东西，但是只有当最上面的东西被取走之后，第二层才能被取走，以此类推；而队列则类似排队，先来的先被服务，后来的等待在队列中。

栈的实现

栈的常见实现方式是使用数组或链表，这里我们采用链表来实现。一个栈包含两个主要操作：压入（push）和弹出（pop）。在链表实现中，我们需要每次将新元素插入链表的头部，同时我们也需要记录当前栈顶元素的位置，以便在弹出元素时能够快速访问。

以下是一段Java实现的示例代码：

public class MyStack<T> {
    // 内部类，代表链表的节点
    private class Node {
        // 数据
        private T data;
        // 下一节点
        private Node next;
        // 构造函数
        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
    // 栈顶节点
    private Node top = null;
    // 栈的大小
    private int size = 0;

    // 压入元素
    public void push(T data) {
        // 新建节点
        Node newNode = new Node(data, top);
        // 更新栈顶
        top = newNode;
        // 更新大小
        size++;
    }

    // 弹出栈顶元素
    public T pop() throws Exception {
        if (top == null) {
            throw new Exception("Stack is empty!");
        }
        // 取出栈顶元素
        T data = top.data;
        // 更新栈顶
        top = top.next;
        // 更新大小
        size--;
        return data;
    }

    // 获取栈顶元素
    public T peek() throws Exception {
        if (top == null) {
            throw new Exception("Stack is empty!");
        }
        return top.data;
    }

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

    // 获取栈的大小
    public int getSize() {
        return size;
    }
}

队列的实现

队列也是可以使用数组或链表来实现，这里我们采用链表实现。一个队列包含两个主要操作：入队（enqueue）和出队（dequeue）。在链表实现中，我们需要每次将新元素插入链表的尾部，同时我们也需要记录队列的头部和尾部位置，以便在出队时能够快速访问。

以下是一段Java实现的示例代码：

public class MyQueue<T> {
    // 内部类，代表链表的节点
    private class Node {
        // 数据
        private T data;
        // 下一节点
        private Node next;
        // 构造函数
        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
    // 队列头
    private Node head = null;
    // 队列尾
    private Node tail = null;
    // 队列大小
    private int size = 0;

    // 入队
    public void enqueue(T data) {
        // 新建节点
        Node newNode = new Node(data, null);
        if (tail == null) {
            // 如果队列为空，则头、尾节点都为新节点
            head = tail = newNode;
        } else {
            // 如果队列不为空，则将新节点插入到尾部
            tail.next = newNode;
            tail = newNode;
        }
        // 更新队列大小
        size++;
    }

    // 出队
    public T dequeue() throws Exception {
        if (head == null) {
            throw new Exception("Queue is empty!");
        }
        // 取出队列头元素
        T data = head.data;
        head = head.next;
        if (head == null) {
            // 如果出队后队列为空，则尾节点设为null
            tail = null;
        }
        // 更新队列大小
        size--;
        return data;
    }

    // 获取队列头元素
    public T getHead() throws Exception {
        if (head == null) {
            throw new Exception("Queue is empty!");
        }
        return head.data;
    }

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

    // 获取队列大小
    public int getSize() {
        return size;
    }
}

示例说明

示例一

假设我们需要对一个字符串进行逆序输出，可以使用栈来实现。将字符串逐个字符压入栈中，然后依次弹出栈顶元素并输出即可。

以下是Java实现的示例代码：

public static void reverseString(String str) throws Exception {
    MyStack<Character> stack = new MyStack<>();
    // 将字符串逐个字符压入栈中
    for (int i = 0; i < str.length(); i++) {
        stack.push(str.charAt(i));
    }
    // 依次弹出栈顶元素并输出
    while (!stack.isEmpty()) {
        System.out.print(stack.pop());
    }
}

示例二

假设我们需要对一组数进行先进先出的排序，可以使用队列来实现。将数列中的数依次入队，然后依次将队列中的元素出队并输出即可。

以下是Java实现的示例代码：

public static void sortNumberList(int[] nums) throws Exception {
    MyQueue<Integer> queue = new MyQueue<>();
    // 将数列中的数依次入队
    for (int i = 0; i < nums.length; i++) {
        queue.enqueue(nums[i]);
    }
    // 依次出队并输出队列中的元素
    while (!queue.isEmpty()) {
        System.out.print(queue.dequeue() + " ");
    }
}