【641】设计循环双端队列(deque)

队列是一种特殊的线性表，它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限的线性表。进行插入操作的端成为队尾，进行删除操作的端称为队头。

双端队列：两端都可以进队和出队的队列

• 从后端进前端出 或者 从前端进后端出 体现了 先进先出 的特点；
• 从后端进后端出 或者 从前端进前端出 体现了 先进后出 的特点。

图示：
分别从前端和后端插入节点：

分别从前端和后端删除节点：

实现代码如下：
【注】我用了一个计数器count来统计双端队列中的元素个数，方便判断栈空与栈满。实际上，用链式结构实现循环双端队列，不存在栈满情况，除非内存满了。但题目要求，故加之。

public class MyCircularDeque {
    class node{
        int val;
        node next = null;
        node pre = null;

        node(int v){
            this.val = v;
        }
    }

    node firsthead = null;
    node lasthead = null;
    int capacity;  //链表的总节点容量
    int count;   //链表的当前节点容量

    /** Initialize your data structure here. Set the size of the deque to be k. */
    public MyCircularDeque(int k) {
        this.capacity = k;
        this.count = 0;
    }

    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    //头插法 保持队列的先进先出特性
    public boolean insertFront(int value) {
        if(isFull()){
            return false;
        }
        node nd = new node(value);
        //只要firsthead为空，那么lasthead必定为空
        if(firsthead==null){
            firsthead = nd;
            lasthead = nd;
        }else {
            //只要firsthead不空 lasthead肯定也不空
            nd.next = firsthead;
            firsthead.pre = nd;
            firsthead = nd;
        }
        count++;
        return true;
    }

    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    public boolean insertLast(int value) {
        if(isFull())
            return false;
        node nd = new node(value);
        if(lasthead==null){
            lasthead = nd;
            firsthead = nd;
        }else {
            nd.pre = lasthead;
            lasthead.next = nd;
            lasthead = nd;
        }
        count++;
        return  true;

    }

    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    public boolean deleteFront() {
        if(isEmpty())
            return false;
        if(count==1){
            firsthead = null;
            lasthead = null;
        }else {
            firsthead = firsthead.next;
            firsthead.pre = null;
        }
        count--;
        return true;
    }

    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    public boolean deleteLast() {
        if (isEmpty())
            return false;
        if (count==1){
            firsthead = null;
            lasthead = null;
        }else {
            lasthead = lasthead.pre;
            lasthead.next = null;
        }
        count --;
        return true;

    }

    /** Get the front item from the deque. */
    public int getFront() {
        if(this.firsthead == null)
            return -1;
        else
            return firsthead.val;
    }

    /** Get the last item from the deque. */
    public int getRear() {
        if(this.lasthead == null)
            return -1;
        else
            return this.lasthead.val;
    }

    /** Checks whether the circular deque is empty or not. */
    public boolean isEmpty() {
        if(this.count == 0)
            return true;
        else
            return false;
    }

    /** Checks whether the circular deque is full or not. */
    public boolean isFull() {
        if(this.count==this.capacity)
            return true;
        else
            return false;
    }
}

另外，还可以了解一下共享栈的结构

用数组实现，数组两端分别为栈底，通过两个栈顶指针进行出入栈操作。栈空与栈满的条件也很好判断。