原文： https://www.programiz.com/dsa/deque

在本教程中，您将学习什么是双端队列（双端队列）。 另外，您还将找到在 C，C++ ，Java 和 Python 的双端队列上进行不同操作的工作示例。

双端队列是队列的一种，其中元素的插入和删除可以从前面或后面进行。 因此，它不遵循 FIFO 规则（先进先出）。

双端队列 - 图1

双端队列

双端队列的类型

  1. 输入限制双端队列
    在此双端队列中，输入在一端限制，但允许在两端删除。
  2. 输出限制双端队列
    在此双端队列中，输出限制在一个端部，但允许在两端插入。

双端队列操作

下面是循环双端数组实现的双端队列。 在圆形数组中，如果数组已满，我们将从头开始。

但是在线性数组实现中，如果数组已满，则无法插入更多元素。 在下面的每个操作中，如果数组已满，则会引发“溢出消息”。

在执行以下操作之前，请执行以下步骤。

  1. 取大小为n的数组。
  2. 在第一个位置设置两个指针，然后设置front = -1和rear = 0。

双端队列 - 图2

初始化数组和指针

在前面插入

此操作在前面添加了一个元素。

  1. 检查前面的位置。
    双端队列 - 图3
    检查正面

  2. 如果为front < 1，请重新初始化front = n-1（最后一个索引）。
    双端队列 - 图4
    前端发送

  3. 否则，将front减小 1。

  4. 将新键5添加到array[front]中。
    双端队列 - 图5
    插入键

在后面插入

此操作在后部增加了一个元素。

  1. 检查数组是否已满。
    双端队列 - 图6
    检查完整的

  2. 如果数组已满，请重新初始化rear = 0。

  3. 否则，将rear增加 1。
    双端队列 - 图7
    增加后

  4. 将新键5添加到array[rear]中。
    双端队列 - 图8
    插入键

从前面删除

该操作从前面删除一个元素。

  1. 检查数组是否为空。
    双端队列 - 图9
    检查为空

  2. 如果数组为空（即front = -1），则无法执行删除操作（下溢条件）。

  3. 如果双端队列只有一个元素（即front = rear），请设置front = -1和rear = -1。

  4. 否则，如果front位于末尾（即front = n - 1），则设置转到前front = 0。

  5. 否则，front = front + 1。
    双端队列 - 图10
    增加前线

从后面删除

此操作从背面删除一个元素。

  1. 检查数组是否为空。
    双端队列 - 图11
    检查为空

  2. 如果数组为空（即front = -1），则无法执行删除操作（下溢条件）。

  3. 如果双端队列只有一个元素（即front = rear），请设置front = -1和rear = -1，否则请按照以下步骤操作。

  4. 如果rear在前面（即rear = 0），则设置转到前rear = n - 1。

  5. 否则，rear = rear - 1。
    双端队列 - 图12
    降低后排

检查空

此操作检查数组是否为空。 如果为front = -1，则双端队列为空。

检查满

此操作检查双端队列是否已满。 如果front = 0和rear = n - 1，则双端队列已满。

Python，Java 和 C/C++ 示例

  1. # Deque operations in python
  3. class Deque:
  4.     def __init__(self):
  5.         self.items = []
  7.     def isEmpty(self):
  8.         return self.items == []
  10.     def addFront(self, item):
  11.         self.items.append(item)
  13.     def addRear(self, item):
  14.         self.items.insert(0, item)
  16.     def removeFront(self):
  17.         return self.items.pop()
  19.     def removeRear(self):
  20.         return self.items.pop(0)
  22.     def size(self):
  23.         return len(self.items)
  25. d = Deque()
  26. print(d.isEmpty())
  27. d.addRear(8)
  28. d.addRear(5)
  29. d.addFront(7)
  30. d.addFront(10)
  31. print(d.size())
  32. print(d.isEmpty())
  33. d.addRear(11)
  34. print(d.removeRear())
  35. print(d.removeFront())
  36. d.addFront(55)
  37. d.addRear(45)
  38. print(d.items)
  1. // Deque operations in Java
  3. class Deque {
  4.   static final int MAX = 100;
  5.   int arr[];
  6.   int front;
  7.   int rear;
  8.   int size;
  10.   public Deque(int size) {
  11.     arr = new int[MAX];
  12.     front = -1;
  13.     rear = 0;
  14.     this.size = size;
  15.   }
  17.   boolean isFull() {
  18.     return ((front == 0 && rear == size - 1) || front == rear + 1);
  19.   }
  21.   boolean isEmpty() {
  22.     return (front == -1);
  23.   }
  25.   void insertfront(int key) {
  26.     if (isFull()) {
  27.       System.out.println("Overflow");
  28.       return;
  29.     }
  31.     if (front == -1) {
  32.       front = 0;
  33.       rear = 0;
  34.     }
  36.     else if (front == 0)
  37.       front = size - 1;
  39.     else
  40.       front = front - 1;
  42.     arr[front] = key;
  43.   }
  45.   void insertrear(int key) {
  46.     if (isFull()) {
  47.       System.out.println(" Overflow ");
  48.       return;
  49.     }
  51.     if (front == -1) {
  52.       front = 0;
  53.       rear = 0;
  54.     }
  56.     else if (rear == size - 1)
  57.       rear = 0;
  59.     else
  60.       rear = rear + 1;
  62.     arr[rear] = key;
  63.   }
  65.   void deletefront() {
  66.     if (isEmpty()) {
  67.       System.out.println("Queue Underflow\n");
  68.       return;
  69.     }
  71.     // Deque has only one element
  72.     if (front == rear) {
  73.       front = -1;
  74.       rear = -1;
  75.     } else if (front == size - 1)
  76.       front = 0;
  78.     else
  79.       front = front + 1;
  80.   }
  82.   void deleterear() {
  83.     if (isEmpty()) {
  84.       System.out.println(" Underflow");
  85.       return;
  86.     }
  88.     if (front == rear) {
  89.       front = -1;
  90.       rear = -1;
  91.     } else if (rear == 0)
  92.       rear = size - 1;
  93.     else
  94.       rear = rear - 1;
  95.   }
  97.   int getFront() {
  98.     if (isEmpty()) {
  99.       System.out.println(" Underflow");
  100.       return -1;
  101.     }
  102.     return arr[front];
  103.   }
  105.   int getRear() {
  106.     if (isEmpty() || rear < 0) {
  107.       System.out.println(" Underflow\n");
  108.       return -1;
  109.     }
  110.     return arr[rear];
  111.   }
  113.   public static void main(String[] args) {
  115.     Deque dq = new Deque(4);
  117.     System.out.println("Insert element at rear end : 12 ");
  118.     dq.insertrear(12);
  120.     System.out.println("insert element at rear end : 14 ");
  121.     dq.insertrear(14);
  123.     System.out.println("get rear element : " + dq.getRear());
  125.     dq.deleterear();
  126.     System.out.println("After delete rear element new rear become : " + dq.getRear());
  128.     System.out.println("inserting element at front end");
  129.     dq.insertfront(13);
  131.     System.out.println("get front element: " + dq.getFront());
  133.     dq.deletefront();
  135.     System.out.println("After delete front element new front become : " + +dq.getFront());
  137.   }
  138. }
  1. // Deque operations in C
  3. #include <stdio.h>
  5. #define MAX 10
  7. void addFront(int *, int, int *, int *);
  8. void addRear(int *, int, int *, int *);
  9. int delFront(int *, int *, int *);
  10. int delRear(int *, int *, int *);
  11. void display(int *);
  12. int count(int *);
  14. int main()
  15. {
  16.   int arr[MAX];
  17.   int front, rear, i, n;
  19.   front = rear = -1;
  20.   for (i = 0; i < MAX; i++)
  21.     arr[i] = 0;
  23.   addRear(arr, 5, &front, &rear);
  24.   addFront(arr, 12, &front, &rear);
  25.   addRear(arr, 11, &front, &rear);
  26.   addFront(arr, 5, &front, &rear);
  27.   addRear(arr, 6, &front, &rear);
  28.   addFront(arr, 8, &front, &rear);
  30.   printf("\nElements in a deque: ");
  31.   display(arr);
  33.   i = delFront(arr, &front, &rear);
  34.   printf("\nremoved item: %d", i);
  36.   printf("\nElements in a deque after deletion: ");
  37.   display(arr);
  39.   addRear(arr, 16, &front, &rear);
  40.   addRear(arr, 7, &front, &rear);
  42.   printf("\nElements in a deque after addition: ");
  43.   display(arr);
  45.   i = delRear(arr, &front, &rear);
  46.   printf("\nremoved item: %d", i);
  48.   printf("\nElements in a deque after deletion: ");
  49.   display(arr);
  51.   n = count(arr);
  52.   printf("\nTotal number of elements in deque: %d", n);
  53. }
  55. void addFront(int *arr, int item, int *pfront, int *prear)
  56. {
  57.   int i, k, c;
  59.   if (*pfront == 0 && *prear == MAX - 1)
  60.   {
  61.     printf("\nDeque is full.\n");
  62.     return;
  63.   }
  65.   if (*pfront == -1)
  66.   {
  67.     *pfront = *prear = 0;
  68.     arr[*pfront] = item;
  69.     return;
  70.   }
  72.   if (*prear != MAX - 1)
  73.   {
  74.     c = count(arr);
  75.     k = *prear + 1;
  76.     for (i = 1; i <= c; i++)
  77.     {
  78.       arr[k] = arr[k - 1];
  79.       k--;
  80.     }
  81.     arr[k] = item;
  82.     *pfront = k;
  83.     (*prear)++;
  84.   }
  85.   else
  86.   {
  87.     (*pfront)--;
  88.     arr[*pfront] = item;
  89.   }
  90. }
  92. void addRear(int *arr, int item, int *pfront, int *prear)
  93. {
  94.   int i, k;
  96.   if (*pfront == 0 && *prear == MAX - 1)
  97.   {
  98.     printf("\nDeque is full.\n");
  99.     return;
  100.   }
  102.   if (*pfront == -1)
  103.   {
  104.     *prear = *pfront = 0;
  105.     arr[*prear] = item;
  106.     return;
  107.   }
  109.   if (*prear == MAX - 1)
  110.   {
  111.     k = *pfront - 1;
  112.     for (i = *pfront - 1; i < *prear; i++)
  113.     {
  114.       k = i;
  115.       if (k == MAX - 1)
  116.         arr[k] = 0;
  117.       else
  118.         arr[k] = arr[i + 1];
  119.     }
  120.     (*prear)--;
  121.     (*pfront)--;
  122.   }
  123.   (*prear)++;
  124.   arr[*prear] = item;
  125. }
  127. int delFront(int *arr, int *pfront, int *prear)
  128. {
  129.   int item;
  131.   if (*pfront == -1)
  132.   {
  133.     printf("\nDeque is empty.\n");
  134.     return 0;
  135.   }
  137.   item = arr[*pfront];
  138.   arr[*pfront] = 0;
  140.   if (*pfront == *prear)
  141.     *pfront = *prear = -1;
  142.   else
  143.     (*pfront)++;
  145.   return item;
  146. }
  148. int delRear(int *arr, int *pfront, int *prear)
  149. {
  150.   int item;
  152.   if (*pfront == -1)
  153.   {
  154.     printf("\nDeque is empty.\n");
  155.     return 0;
  156.   }
  158.   item = arr[*prear];
  159.   arr[*prear] = 0;
  160.   (*prear)--;
  161.   if (*prear == -1)
  162.     *pfront = -1;
  163.   return item;
  164. }
  166. void display(int *arr)
  167. {
  168.   int i;
  170.   printf("\n front:  ");
  171.   for (i = 0; i < MAX; i++)
  172.     printf("  %d", arr[i]);
  173.   printf("  :rear");
  174. }
  176. int count(int *arr)
  177. {
  178.   int c = 0, i;
  180.   for (i = 0; i < MAX; i++)
  181.   {
  182.     if (arr[i] != 0)
  183.       c++;
  184.   }
  185.   return c;
  186. }
  1. // Deque operations in C++
  3. #include <iostream>
  4. using namespace std;
  6. #define MAX 10
  8. class Deque
  9. {
  10.   int arr[MAX];
  11.   int front;
  12.   int rear;
  13.   int size;
  15. public:
  16.   Deque(int size)
  17.   {
  18.     front = -1;
  19.     rear = 0;
  20.     this->size = size;
  21.   }
  23.   void insertfront(int key);
  24.   void insertrear(int key);
  25.   void deletefront();
  26.   void deleterear();
  27.   bool isFull();
  28.   bool isEmpty();
  29.   int getFront();
  30.   int getRear();
  31. };
  33. bool Deque::isFull()
  34. {
  35.   return ((front == 0 && rear == size - 1) ||
  36.       front == rear + 1);
  37. }
  39. bool Deque::isEmpty()
  40. {
  41.   return (front == -1);
  42. }
  44. void Deque::insertfront(int key)
  45. {
  46.   if (isFull())
  47.   {
  48.     cout << "Overflow\n"
  49.        << endl;
  50.     return;
  51.   }
  53.   if (front == -1)
  54.   {
  55.     front = 0;
  56.     rear = 0;
  57.   }
  59.   else if (front == 0)
  60.     front = size - 1;
  62.   else
  63.     front = front - 1;
  65.   arr[front] = key;
  66. }
  68. void Deque ::insertrear(int key)
  69. {
  70.   if (isFull())
  71.   {
  72.     cout << " Overflow\n " << endl;
  73.     return;
  74.   }
  76.   if (front == -1)
  77.   {
  78.     front = 0;
  79.     rear = 0;
  80.   }
  82.   else if (rear == size - 1)
  83.     rear = 0;
  85.   else
  86.     rear = rear + 1;
  88.   arr[rear] = key;
  89. }
  91. void Deque ::deletefront()
  92. {
  93.   if (isEmpty())
  94.   {
  95.     cout << "Queue Underflow\n"
  96.        << endl;
  97.     return;
  98.   }
  100.   if (front == rear)
  101.   {
  102.     front = -1;
  103.     rear = -1;
  104.   }
  105.   else if (front == size - 1)
  106.     front = 0;
  108.   else
  109.     front = front + 1;
  110. }
  112. void Deque::deleterear()
  113. {
  114.   if (isEmpty())
  115.   {
  116.     cout << " Underflow\n"
  117.        << endl;
  118.     return;
  119.   }
  121.   if (front == rear)
  122.   {
  123.     front = -1;
  124.     rear = -1;
  125.   }
  126.   else if (rear == 0)
  127.     rear = size - 1;
  128.   else
  129.     rear = rear - 1;
  130. }
  132. int Deque::getFront()
  133. {
  134.   if (isEmpty())
  135.   {
  136.     cout << " Underflow\n"
  137.        << endl;
  138.     return -1;
  139.   }
  140.   return arr[front];
  141. }
  143. int Deque::getRear()
  144. {
  145.   if (isEmpty() || rear < 0)
  146.   {
  147.     cout << " Underflow\n"
  148.        << endl;
  149.     return -1;
  150.   }
  151.   return arr[rear];
  152. }
  154. int main()
  155. {
  156.   Deque dq(4);
  158.   cout << "insert element at rear end \n";
  159.   dq.insertrear(5);
  160.   dq.insertrear(11);
  162.   cout << "rear element: "
  163.      << dq.getRear() << endl;
  165.   dq.deleterear();
  166.   cout << "after deletion of the rear element, the new rear element: " << dq.getRear() << endl;
  168.   cout << "insert element at front end \n";
  170.   dq.insertfront(8);
  172.   cout << "front element: " << dq.getFront() << endl;
  174.   dq.deletefront();
  176.   cout << "after deletion of front element new front element: " << dq.getFront() << endl;
  177. }

双端队列复杂度

所有上述操作的时间复杂度是恒定的，即O(1)。

双端队列应用

  1. 软件中的撤消操作。
  2. 在浏览器中存储历史记录。
  3. 为了实现栈和队列。