【数据结构与算法】【08】数据结构之栈和队列

什么是栈和队列

栈和队列是两种特殊的线性表结构，它们不像数组和链表一样，可以在任意位置插入数据

• 栈规定，数据只能从顶部插入，只能从顶部移除 就像堆砖块一样，只能从顶部添加新砖块，也只能从顶部拿走旧砖块，不能从中间抽走砖块
• 队列规定，数据只能从尾部插入，只能从头部移除 就像食堂的取饭队伍一样，只能从后面排，前面出去，不能插队
• 栈的特点，可以用后进先出来概括，队列的特点，可以用先进先出来概括

可见，栈和队列，跟数组和链表并没有太大区别，只是限制了插入删除位置而已

因此，数组和链表，都可以用来实现栈和队列

但是一般我们不用插入删除来表述栈和队列的操作

而是用入栈（push）、出栈（pop）、入列（enqueue）、出列（dequeue）这些专有词语来代替

双向队列

双向队列，英文名Deque，顾名思义，就是正向可以当队列用，反向也可以当队列用

实际上，它就是两端都可以插入和删除的线性表，它既可以当栈用，也可以当队列用，还可以正反向随便用

双向队列通过双向链表就可以很容易地实现，自己控制哪端删除，哪端插入就行了

栈实现代码

	//栈
	@SuppressWarnings("all")
	public class Stack {
	
	    //这是一个标记栈顶的特殊节点，本身不存储数据
	    final Node top = new Node();
	
	    //判断栈是否为空
	    public boolean IsEmpty() {
	        return top.next == null;
	    }
	
	    //统计栈的大小
	    public int Size() {
	        int size = 0;
	        Node preNode = top;
	        while (preNode.next != null) {
	            size++;
	            preNode = preNode.next;
	        }
	        return size;
	    }
	
	    //从栈顶向栈底遍历数据
	    public void Print() {
	        Node preNode = top;
	        while (preNode.next != null) {
	            System.out.println(preNode.next);
	            preNode = preNode.next;
	        }
	        int size = Size();
	        System.out.println("Total Size: " + size);
	    }
	
	    //入栈
	    public void Push(T data) {
	        Node insertNode = new Node();
	        insertNode.data = data;
	        insertNode.next = top.next;
	        top.next = insertNode;
	    }
	
	    //出栈
	    public T Pop() {
	        if (IsEmpty())
	            return null;
	        Node deleteNode = top.next;
	        top.next = deleteNode.next;
	        return (T) deleteNode.data;
	    }
	
	
	    //数据节点
	    protected static class Node {
	
	        T data;
	        Node next;
	
	        @Override
	        public String toString() {
	            if (next == null)
	                return data + " => null";
	            return data + " => " + String.valueOf(next.data);
	        }
	    }
	
	    public static void main(String[] args) {
	        Stack stack = new Stack();
	        stack.Push("A");
	        stack.Push("B");
	        stack.Push("C");
	        stack.Push("D");
	        stack.Push("E");
	        stack.Pop();
	        stack.Pop();
	        stack.Print();
	    }
	}

队列实现代码

	//队列
	@SuppressWarnings("all")
	public class Queue {
	
	    //这是一个标记队首的特殊节点，本身不存储数据
	    final Node head = new Node();
	
	    //这是一个标记队尾的特殊节点，本身不存储数据
	    final Node tail = new Node();
	
	    //初始化
	    public void Init() {
	        head.next = tail;
	        tail.previous = head;
	    }
	
	    //判断队列是否为空
	    public boolean IsEmpty() {
	        return head.next == tail;
	    }
	
	    //统计队列的大小
	    public int Size() {
	        int size = 0;
	        Node preNode = head;
	        while (preNode.next != tail) {
	            size++;
	            preNode = preNode.next;
	        }
	        return size;
	    }
	
	    //从列首向列尾遍历数据
	    public void Print() {
	        Node preNode = head;
	        while (preNode.next != tail) {
	            System.out.println(preNode.next);
	            preNode = preNode.next;
	        }
	        int size = Size();
	        System.out.println("Total Size: " + size);
	    }
	
	    //入列
	    public void Enqueue(T data) {
	        Node insertNode = new Node();
	        insertNode.data = data;
	        insertNode.next = tail;
	        tail.previous.next = insertNode;
	        tail.previous = insertNode;
	    }
	
	    //出列
	    public T Dequeue() {
	        if (IsEmpty())
	            return null;
	        Node deleteNode = head.next;
	        head.next = deleteNode.next;
	        return (T) deleteNode.data;
	    }
	
	    //数据节点
	    protected static class Node {
	
	        T data;
	        Node next;
	        Node previous;
	
	        @Override
	        public String toString() {
	            if (next == null)
	                return data + " => null";
	            return data + " => " + String.valueOf(next.data);
	        }
	    }
	
	    public static void main(String[] args) {
	        Queue queue = new Queue();
	        queue.Init();
	        queue.Enqueue("A");
	        queue.Enqueue("B");
	        queue.Enqueue("C");
	        queue.Enqueue("D");
	        queue.Enqueue("E");
	        queue.Dequeue();
	        queue.Dequeue();
	        queue.Print();
	    }
	}