双向队列是一种特殊的队列，允许在头部和尾部执行元素添加和删除操作

双向队列常用操作

deque<int> deque;

deque.push_back(2);
deque.push_front(3);

int front = deque.front();
int back = deque.back();

deque.pop_front();
deque.pop_back();

int size = deque.size();
bool empty = deque.empty();

双向队列实现

基于双向链表的实现

struct DoublyListNode {
  int val;
  DoublyListNode* next;
  DoublyListNode* prev;
  DoublyListNode(int val) : val(val), prev(nullptr), next(nullptr) {}
}

class LinkedListDeque {
private:
  DoublyListNode* front;
  DoublyListNode* rear;
  int queSize = 0;
  
public:
  LinkedListDeque() : front(nullptr), rear(nullptr) {}
  
  ~LinkedListDeque() {
    DoublyListNode* pre;
    DoublyListNode* cur = front;
    while (cur != nullptr) {
      pre = cur;
      cur = cur->next;
      delete pre;
    }
  }
  
  int size() {
    return queSize;
  }
  
  bool isEmpty() {
    return size() == 0;
  }
  
  void push(int num, bool isFront) {
    DoublyListNode* node = new DoublyListNode(num);
    if (isEmpty()) front = rear = node;
    else if (isFront) {
      front->prev = node;
      node->next = front;
      front = node;
    } else {
      rear->next  = node;
      node->prev = rear;
      rear = node;
    }
    
    ++queSize;
  }
  
  void pushFirst(int num) {
    push(num, true);
  }
  
  void pushLast(int num) {
    push(num, false);
  }
  
  void pop(bool isFront) {
    if (isEmpty()) throw out_of_range("队列为空");
    
    int val;
    
    if (isFront) {
      val = front->val;
      DoublyListNode* fNext = front->next;
      if (fNext != nullptr) {
        fNext->prev = nullptr;
        front->next = nullptr;
      }
      
      delete front;
      front = fNext;
    } else {
      val = rear->val;
      DoublyListNode* rPrev = rear->prev;
      if (rPrev != nullptr) {
        rPrev->next = nullptr;
        rear->prev = nullptr;
      }
      
      delete rear;
      rear = rPrev;
    }
    
    --queSize;
    return val;
  }
  
  int popFirst() {
    return pop(true);
  }
  
  int popLast() {
    return pop(false);
  }
  
  int peekFirst() {
    if (isEmpty()) {
      throw out_of_range("队列为空");
    }
    return front->val;
  }
  
  vector<int> toVector() {
    DoublyListNode* node = front;
    vector<int> res(size());
    
    for (int i = 0; i < res.size(); ++i) {
      res[i] = node->val;
      node = node->next;
    }
    
    return res;
  }
}

基于数组的实现

class ArrayDeque {
private:
  vector<int> nums;
  int front;
  int queSize;
  
public:
  ArrayDeque(int capacity) {
    nums.resize(capacity);
    front = queSize = 0;
  }
  
  int capacity() {
    return nums.size();
  }
  
  int size() {
    return queSize;
  }
  
  bool isEmpty() {
    return queSize == 0;
  }
  
  int index(int i) {
    return (i + capacity()) % capacity();
  }
  
  void pushFirst(int num) {
    if (queSize == capacity()) {
      cout << "队列已满" << endl;
      return;
    }
    
    front = index(front - 1);
    nums[front] = num;
    ++queSize;
  }
  
  void pushLast(int num) {
    if (queSize == capacity()) {
      cout << "队列已满" << endl;
      return;
    }
    
    int rear = index(front + queSize);
    nums[rear] = num;
    ++queSize;
  }
  
  int popFirst() {
    int num = peekFirst();
    front = index(front + 1);
    --queSize;
    return num;
  }
  
  int popLast() {
    int num = peekLast();
    --queSize;
    return num;
  }
  
  int peekLast() {
    if (isEmpty()) {
      throw out_of_range("队列为空");
    }
    
    int last = index(front + queSize - 1);
    return nums[last];
  }
  
  int peekFirst() {
    if (isEmpty()) throw out_of_range("队列为空");
    return nums[front];
  }
  
  vector<int> toVector() {
    vector<int> res(queSize);
    for (int i = 0, j = front; i < queSize; ++i, ++j) {
      res[i] = nums[index(j)];
    }
    
    return res;
  }
}