# 栈&队列

## 0x00、 栈 & 队列

**栈 & 队列** 都是动态集合，且在其上进行 DELETE 操作所删除的元素都是预先设定的。

在 栈(stack) 中，被删除的是最近插入的元素。 栈 实现的是一种 **后进先出(last-in,first-out LIFO)** 的策略。

在 队列(queue) 中，被删除的总是在集合中存在时间最长的元素。 队列 实现的是一种 **先进先出(first-in,first-out FIFO)** 的策略。

### 0.1、 用 Java 实现一个队列

1. 我们称数组为 Q 长度为 Q.length 。存在针对数组的两个指针 Q.head , Q.tail 并且在这两个指针处都可以完成插入和删除的操作。
2. 两个指针的起始位置均为 `Q[0](Q.head = 0 , Q.tail = 0)`。
3. 在逻辑上这个数组是首尾向接的。

## 0x01、 实现双端队列

**问题描述 :** 栈插入和删除元素只能在同一端进行，与他们不同的，有一种 **双端队列(deque)** 其插入和删除操作都可以两端进行。 写出四个时间均为 O(1) 的过程，分别实现在双端队列的两端插入删除元素的操作，该队列是用一个数组实现的。

**问题分析 :** 1. 我们称数组为 Q 长度为 Q.length 。存在针对数组的两个指针 Q.head , Q.tail 并且在这两个指针处都可以完成插入和删除的操作。 2. 两个指针的起始位置均为 `Q[0](Q.head = 0 , Q.tail = 0)`。 3. 在逻辑上这个数组是首尾向接的。 4. (上溢)对于 Q.head ,在插入操作的时候如果发现 Q.head+1 == Q.tail 表示队列已经满了。 5. (上溢)对于 Q.tail ,在插入操作的时候如果发现 Q.tail-1 == Q.head 表示队列已经满了。 6. (下溢)对于 Q.head ,在删除操作的时候如果发现 Q.head-1 < Q.tail 表示当前删除的是队列中的最后一个元素了。 7. (下溢)对于 Q.tail ,在删除操作的时候如果发现 Q.tail+1 > Q.head 表示当前删除的是队列中的最后一个元素了。

```java
public class Queue<E>{
    private E[] Q;
    int head = 0;
    int tail = 0;

    /*队列初始化的时候确定队列长度*/
    public Queue(int n){
        Q = new E[n];
    }

    public void enqueueHead(E e){
        //要确保插入不会导致上溢就要首先进行预判从而确定是否要执行插入操作
        head +=1;
        if(head == Q.length){
            head = 0;
        }

        if(head == tail){
            notify("插入失败，队列已经满了");
            head -= 1;
        }else{
            Q[head] = e;
        }
    }

    public E dqueueHead(){
        head -= 1;
        if(head == -1){
            head = Q.length-1;
            if(tail == 0){
                notify("删除成功，这是队列中的最后一个元素了")
            }
        }else{

        }

        if(head < tail){}
    }

    public void enqueueTail(E e){
        //要确保插入不会导致上溢就要首先进行预判从而确定是否要执行插入操作
        tail -= 1;
        if(tail == -1){
            tail = Q.length - 1;
        }

        if(tail == head){
            notify("插入失败，队列已经满了");
            tail -= 1;
        }else{
            Q[tail] = e;
        }
    }

    public E dqueueTail(){

    }

    public void notify(String str){/*通知操作者操作失败的原因*/}
}
```