2.2 栈与队列

在我们日常生活中，一些排列和存储物品的方式可以很好地帮助我们理解栈和队列这两种数据结构。

栈（Stack）

栈是一种后进先出（Last In First Out，简称LIFO）的数据结构，就像我们堆盘子一样，最后放的盘子在最上面，需要取时也是先取最上面的盘子。我们可以通过Java中的Stack类来实现栈的功能：

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());  // 输出：3
        stack.pop();
        System.out.println(stack.peek());  // 输出：2
    }
}

在这个示例中，我们使用了Stack类的push方法来添加元素，peek方法来获取栈顶元素，以及pop方法来删除栈顶元素。可以看到，最后入栈的元素总是最先出栈。

自己实现一个简单的栈：

public class SimpleStack<T> {
    private ArrayList<T> stack = new ArrayList<>();

    public int getSize() {
        return stack.size();
    }

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

    public void push(T item) {
        stack.add(item);
    }

    public T pop() {
        if (!isEmpty()) {
            return stack.remove(stack.size() - 1);
        } else {
            return null; // Or throw exception
        }
    }

    public T peek() {
        if (!isEmpty()) {
            return stack.get(stack.size() - 1);
        } else {
            return null; // Or throw exception
        }
    }
}

上面的实现中，我们使用ArrayList作为底层的数据结构。在push操作中，我们直接在ArrayList的末尾添加元素，pop操作则是删除并返回ArrayList的最后一个元素。

队列（Queue）

与栈相反，队列是一种先进先出（First In First Out，简称FIFO）的数据结构，就像我们在银行排队一样，最早来的人会最先得到服务。我们可以通过Java的Queue接口和LinkedList类来实现队列的功能：

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

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        System.out.println(queue.peek());  // 输出：1
        queue.poll();
        System.out.println(queue.peek());  // 输出：2
    }
}

在这个示例中，我们使用了Queue接口的offer方法来添加元素，peek方法来获取队列头部的元素，以及poll方法来删除队列头部的元素。可以看到，最早入队的元素总是最先出队。

自己实现一个简单的队列：

import java.util.LinkedList;

public class SimpleQueue<T> {
    private LinkedList<T> queue = new LinkedList<>();

    public int getSize() {
        return queue.size();
    }

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

    public void offer(T item) {
        queue.addLast(item);
    }

    public T poll() {
        if (!isEmpty()) {
            return queue.removeFirst();
        } else {
            return null; // Or throw exception
        }
    }

    public T peek() {
        if (!isEmpty()) {
            return queue.getFirst();
        } else {
            return null; // Or throw exception
        }
    }
}