Java栈与队列的实现

栈和队列的实现

实现类使用实现了Deque接口的类，如ArrayQueue或LinkedList，性能上ArrayQueue占优

栈的实现

使用Deque接口，ArrayDeque实现类

Deque<String> stack = new ArrayDeque<>();
stack.push("a");
stack.push("b");
stack.push("c");
while (stack.peek() != null) {
    System.out.println(stack.pop());
}

输出结果

c
b
a

队列的实现

使用Queue接口，ArrayDeque实现类

add和remove方法，失败抛异常

Queue<String> queue = new ArrayDeque<>();
queue.add("d");
queue.add("e");
queue.add("f");
while (queue.peek() != null) {
    System.out.println(queue.remove());
}

offer和poll方法，失败返回特殊值，如false和null

Queue<String> queue = new ArrayDeque<>();
queue.offer("d");
queue.offer("e");
queue.offer("f");
while (queue.peek() != null) {
    System.out.println(queue.poll());
}

输出结果

d
e
f

element方法可替代peek方法，区别为element方法失败抛异常，peek方法失败返回null

Queue接口方法总结

入队

• add，插入队尾，失败抛异常
• offer，插入队尾，失败返回特殊值false

出队

• remove，从队头移出，失败抛异常
• poll，从队头移出，失败返回特殊值null

查看

• element，查看队头，失败抛异常
• peek，查看队头，失败返回特殊值null

Deque接口方法总结

入队

• addFirst插入队头，失败抛异常
• addLast插入队尾，失败抛异常，相当于Queue接口的add
• offerFirst插入队头，失败返回特殊值false
• offerLast插入队尾，失败返回特殊值false，相当于Queue接口的offer

出队

• removeFirst从队头移出，失败抛异常，相当于Queue接口的remove
• removeLast从队尾移出，失败抛异常
• pollFirst从队头移出，失败返回特殊值null，相当于Queue接口的poll
• pollLast从队尾移出，失败返回特殊值null

查看

• getFirst查看队头，失败抛异常，相当于Queue接口的element
• getLast查看队尾，失败抛异常
• peekFirst查看队头，失败返回特殊值null，相当于Queue接口的peek
• peekLast查看队尾，失败返回特殊值null

栈操作

• push压入栈，相当于addFirst，失败抛异常
• pop从栈弹出，相当于removeFirst，失败抛异常
• peek查看栈顶，失败返回特殊值null