栈和队列总结

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头。 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。出栈：栈的删除操作叫做出栈。出数据在栈顶。 Deque（双端队列）中常见方法：

public interface Deque extends Queue{ // 这组方法，通过特殊返回值报告错误 boolean offerFirst(Integer e); Integer peekFirst(); Integer pollFirst(); boolean offerLast(Integer e); Integer peekLast(); Integer pollLast(); // 这组方法，通过异常报错 default void addFirst(Integer e) { if (offerFirst(e) == false) { throw new IllegalStateException(); } } default Integer getFirst() { Integer e = peekFirst(); if (e == null) { throw new NoSuchElementException(); } return e; } default Integer removeFirst() { Integer e = pollFirst(); if (e == null) { throw new NoSuchElementException(); } return e; } default void addLast(Integer e) { if (offerLast(e) == false) { throw new IllegalStateException(); } } default Integer getLast() { Integer e = peekLast(); if (e == null) { throw new NoSuchElementException(); } return e; } default Integer removeLast() { Integer e = pollLast(); if (e == null) { throw new NoSuchElementException(); } return e; } // 这组方法，继承自 Queue // 特殊值 default boolean offer(Integer e) { return offerLast(e); } default Integer peek() { return peekFirst(); } default Integer poll() { return pollFirst(); } // 下面这组方法为栈的形态准备，还包括上面的 peek 方法 default void push(Integer e) { addFirst(e); } default Integer pop() { return removeFirst(); } }

这些方法通过LinkedList类来实现Deque接口

public class LinkedList implements Deque { private static class Node { public Integer v; Node prev; Node next; Node(Integer x) { v = x; } } private Node head; private Node tail; private int size; @Override public boolean offerFirst(Integer e) { if (size == 0) { head = tail = new Node(e); } else { Node newNode = new Node(e); newNode.next = head; head.prev = newNode; head = newNode; } size++; return true; } @Override public Integer peekFirst() { if (size == 0) { return null; } return head.v; } @Override public Integer pollFirst() { if (size == 0) { return null; } Integer e = head.v; head = head.next; if (head != null) { head.prev = null; } else { tail = null; } size--; return e; } @Override public boolean offerLast(Integer e) { if (size == 0) { head = tail = new Node(e); } else { Node newNode = new Node(e); tail.next = newNode; newNode.prev = tail; tail = newNode; } size++; return true; } @Override public Integer peekLast() { if (size == 0) { return null; } return tail.v; } @Override public Integer pollLast() { if (size == 0) { return null; } Integer e = tail.v; tail = tail.prev; if (tail != null) { tail.next = null; } else { head = null; } size--; return e; } }

LinkedList与Deque，Queque，三者之间的关系：LinkedList是实现类，继承了Deque接口，而Deque接口继承了Queque接口，因此LinkedList是实现类要重写接口中的方法。

Queque（队列）接口中的方法：

public interface Queue { //这组方法通过返回特殊值来通知错误 boolean offer(Integer e); Integer peek(); Integer poll(); //这组方法通过抛异常通知错误 default boolean add(Integer e){ if(offer(e)==false){ throw new IllegalStateException(); } return true; } default Integer element(){ Integer e=peek(); if(e==null){ throw new NoSuchElementException(); } return e; } default Integer remove(){ Integer e=poll(); if(e==null){ throw new NoSuchElementException(); } return e; } }