重写Stack与Queue

一、Stack

1、栈明细

       栈是一种特殊的线性表，只能在栈顶插入和删除元素(入栈和出栈)，相当于只有栈顶一端才对用户可见。遵循后进先出LIFO原则(Last In First Out)与FILO原则(First In Last Out)。

       考虑到栈只在一端操作数据的时间复杂度，底层可以用动态数组或者双向链表实现，jdk源码用的是动态数组实现的栈，只不过继承的是Vector<E>这个泛型，和动态数组唯一不同就是线程安全。

       浏览器前进和后退底层就是用两个栈来实现的。

	public class Stack<E> {
	    private ArrayList<E> list;  //组合优于继承
	
	    public Stack() {
	        list = new ArrayList<>();
	    }
	
	    public boolean isEmpty() {
	        return list.size() == 0;
	    }
	
	    public void push(E element) {
	        list.add(element);
	    }
	
	    public E pop() {
	        E element = list.get(list.size() - 1);
	        list.remove(list.size() - 1);
	        return element;
	    }
	
	    /**
	     * 返回栈顶元素
	     *
	     * @return
	     */
	    public E peek() {
	        return list.get(list.size() - 1);
	    }
	    
	 	public static void main(String[] args) {
	        Stack<Integer> stack = new Stack<>();
	        stack.push(11);
	        stack.push(22);
	        stack.push(33);
	        stack.pop();
	        stack.push(44);
	        System.out.println(stack.peek());
	        while (!stack.isEmpty()) {
	            System.out.println(stack.pop());
	        }
	    }
	}

2、测试结果

二、Queue

1、普通队列明细

       普通队列也是特殊的线性表，只能在队尾插入元素(入队)，在队头删除元素(出队)，但是只有队头为用户可见。遵循后进先出LILO原则(Last In Last Out)与FIFO原则(First In First Out)。

       考虑到队列需要在两端操作数据的时间复杂度，底层最适用双向链表实现，jdk源码用的也是LinkedList实现的队列，LinkedList底层还是双向链表啦。

       其实普通队列完全可以用两个栈来模拟。

	public class Queue<E> {
	    private DoubleLinkedList<E> list;
	
	    public Queue() {
	        list = new DoubleLinkedList<>();
	    }
	
	    public boolean isEmpty() {
	        return list.size() == 0;
	    }
	
	    public void offer(E element) {
	        list.add(element);
	    }
	
	    public E remove() {
	        E element = list.get(0);
	        list.remove(0);
	        return element;
	    }
	
	    /**
	     * 返回队列头元素
	     *
	     * @return
	     */
	    public E peek() {
	        return list.get(0);
	    }
	
	    public static void main(String[] args) {
	        Queue<Integer> queue = new Queue<>();
	        queue.offer(11);
	        queue.offer(22);
	        queue.offer(33);
	        queue.remove();
	        queue.offer(44);
	        System.out.println(queue.peek());
	        while (!queue.isEmpty()) {
	            System.out.println(queue.remove());
	        }
	    }
	}

2、测试结果

3、双端队列明细

       双端队列不仅可以在队列头删除元素还可以在队列尾删除元素(头尾都可出队)，同时添加元素既可以在队列尾也可以在队列头(头尾都可入队)。队头和队尾都为用户可见。

       jdk源码用的也是LinkedList实现的队列，LinkedList底层还是双向链表啦。

	public class Deque<E> {
	    private DoubleLinkedList<E> list;   //组合优于继承
	
	    public Deque() {
	        list = new DoubleLinkedList<>();
	    }
	
	    public boolean isEmpty() {
	        return list.size() == 0;
	    }
	
	    public void offerFirst(E element) {
	        list.add(0, element);
	    }
	
	    public void offerLast(E element) {
	        list.add(element);
	    }
	
	    public E removeFirst() {
	        E element = list.get(0);
	        list.remove(0);
	        return element;
	    }
	
	    public E removeLast() {
	        E element = list.get(list.size() - 1);
	        list.remove(list.size() - 1);
	        return element;
	    }
	
	    public E peekFirst() {
	        return list.get(0);
	    }
	
	    public E peekLast() {
	        return list.get(list.size() - 1);
	    }
	
	    public static void main(String[] args) {
	        Deque<Integer> deque = new Deque<>();
	        deque.offerFirst(22);
	        deque.offerFirst(11);
	        deque.offerLast(33);
	        deque.offerLast(44);
	        deque.offerFirst(0);
	        deque.removeFirst();
	        while (!deque.isEmpty()) {
	            System.out.println(deque.removeLast());
	        }
	    }
	}

4、测试结果