设计循环双端队列(deque)-ag真人游戏

队列是一种特殊的线性表，它只允许在表的前端(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;
    }
}

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

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