双端队列

双端队列（Double-Ended Queue, Deque）是一种两端都可以进行入队和出队操作的线性表。

分类

1. 输入受限的双端队列：只允许在一端入队，但两端都可以出队
2. 输出受限的双端队列：只允许在一端出队，但两端都可以入队

输入受限的双端队列：          输出受限的双端队列：
        只能从队尾入 →              → 从队头入
   ┌──────────────────┐        ┌──────────────────┐
←  │      数据区      │ ←      │      数据区      │  →
   从队头出           从队尾出    从队尾入          只能从队尾出

存储实现

#define MaxSize 100
typedef struct {
    ElemType data[MaxSize];
    int front, rear;  // 队头和队尾指针
} Deque;

四种基本操作：队头入队 push_front(x)；队尾入队 push_back(x)；队头出队 pop_front()；队尾出队 pop_back()。