栈与队列：数据结构的有序世界

在计算机科学中，栈和队列是两种非常重要的线性数据结构，它们以特定的顺序存储和管理数据。本文将详细介绍栈和队列的基本概念、实现方式以及它们之间的相互转换，并通过代码示例和表格对比来加深理解。

栈（Stack）：后进先出（LIFO）的存储结构

基本概念

栈是一种限制在一端进行插入和删除操作的线性表。这一端被称为栈顶，另一端称为栈底。栈的特点是后进先出（Last In First Out, LIFO），即最后进入的元素最先被取出。

栈的实现

使用数组实现栈是最常见的方法。以下是一个简单的栈实现的Java代码示例：

public class MyStack<T> {
    private T[] elements;
    private int size;

    public MyStack(int capacity) {
        elements = (T[]) new Object[capacity];
        size = 0;
    }

    public void push(T element) {
        if (size < elements.length) {
            elements[size++] = element;
        }
    }

    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return elements[--size];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return elements[size - 1];
    }
}

栈的应用

• 括号匹配：使用栈可以检查括号是否正确匹配。
• 逆波兰表达式求值：栈可以用来计算后缀表达式的值。

队列（Queue）：先进先出（FIFO）的存储结构

基本概念

队列是一种允许在一端（队尾）进行插入操作，在另一端（队头）进行删除操作的线性表。队列的特点是先进先出（First In First Out, FIFO）。

队列的实现

与栈类似，队列也可以通过数组或链表来实现。以下是一个基于链表的队列实现的Java代码示例：

import java.util.LinkedList;

public class MyQueue<T> {
    private LinkedList<T> list = new LinkedList<>();

    public void offer(T element) {
        list.addLast(element);
    }

    public T poll() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return list.removeFirst();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return list.getFirst();
    }
}

队列的应用

• 任务调度：在操作系统中，队列常用于任务调度。
• 消息队列：在分布式系统中，消息队列用于传递消息。

栈与队列的相互实现

队列实现栈

要使用队列实现栈，需要两个队列。以下是一个使用两个队列实现栈的Java代码示例：

public class StackUsingQueues {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    public StackUsingQueues() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        queue1.offer(x);
    }

    public int pop() {
        if (queue2.isEmpty()) {
            while (!queue1.isEmpty()) {
                queue2.offer(queue1.poll());
            }
        }
        return queue2.poll();
    }
}

栈实现队列

要使用栈实现队列，同样需要两个栈。以下是一个使用两个栈实现队列的Java代码示例：

public class QueueUsingStacks {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public QueueUsingStacks() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

对比表格

结论

栈和队列是两种具有不同特性和应用场景的数据结构。通过本文的介绍和代码示例，我们可以更好地理解它们的定义、实现方式以及如何相互转换。在实际编程中，根据不同的需求选择合适的数据结构是解决问题的关键。