第03章_栈和队列.md

第03章 栈和队列

本章的栈和队列的实现实际上完全可以用JDK自带的类ArrayDeque来实现

作为队列使用

• public abstract boolean add(E paramE); // 加入元素到队尾
• public abstract boolean offer(E paramE); // 加入元素到队尾
• public abstract E remove(); // 弹出队头元素
• public abstract E poll(); // 弹出队头元素

ArrayDeque接口提供了以上几个方法，使用时要注意：

• 尽量避免使用add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。
• offer()和poll()优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。
• 如果要使用队头元素而不移出该元素，使用element()或者peek()方法

代码示例：

package Chapter03StackAndQueues.JavaBuiltIn;

import java.util.ArrayDeque;

/**
 * ArrayDeque作为队列使用
 */
public class ArrayDequeQueue {
    public static void main(String[] args) {
        // 左边的ArrayDeque可以换成java.util.Queue，相当于向上转型，会只留下add()和remove()方法。见图论中BFS的实现
        ArrayDeque<String> queue = new ArrayDeque<>();
        // 入队
        queue.offer("Java");
        queue.offer("Python");
        queue.offer("C++");
        System.out.println(queue);

        // 出队
        System.out.println(queue.poll());
        System.out.println(queue);
        // 打印队首元素，但是并不出队
        System.out.println(queue.peek());
        System.out.println(queue);
    }
}

作为栈使用

• 添加元素：push()
• 弹出元素：pop()
• 获取栈顶元素但不弹出：peek()

package Chapter03StackAndQueues.JavaBuiltIn;

import java.util.ArrayDeque;

/**
 * ArrayDeque当成栈来使用
 */
public class ArrayDequeStack {

    public static void main(String[] args) {
        ArrayDeque<String> stack = new ArrayDeque<>();
        // 入栈
        stack.push("Java");
        stack.push("Python");
        stack.push("C++");
        System.out.println(stack);
        // 出栈
        System.out.println(stack.pop());
        System.out.println(stack);
        // 显示第一个元素但是不出栈
        System.out.println(stack.peek());
        System.out.println(stack);
    }
}

栈的JDK标准类还有java.util.Stack，使用方法完全一样