雙端隊列 · Programiz 中文系列教程

# 雙端隊列 > 原文： [https://www.programiz.com/dsa/deque](https://www.programiz.com/dsa/deque) #### 在本教程中，您將學習什么是雙端隊列（雙端隊列）。另外，您還將找到在 C，C++ ，Java 和 Python 的雙端隊列上進行不同操作的工作示例。雙端隊列是[隊列](https://www.programiz.com/dsa/queue)的一種，其中元素的插入和刪除可以從前面或后面進行。因此，它不遵循 FIFO 規則（先進先出）。 ![Deque](https://img.kancloud.cn/6f/8e/6f8e170364e62f45e6c0feb9a0f780e9_1274x204.png "Double ended queue") 雙端隊列 * * * ## 雙端隊列的類型 1. 輸入限制雙端隊列在此雙端隊列中，輸入在一端限制，但允許在兩端刪除。 2. 輸出限制雙端隊列在此雙端隊列中，輸出限制在一個端部，但允許在兩端插入。 * * * ## 雙端隊列操作下面是[循環雙端數組](https://www.programiz.com/dsa/circular-queue)實現的雙端隊列。在圓形數組中，如果數組已滿，我們將從頭開始。但是在線性數組實現中，如果數組已滿，則無法插入更多元素。在下面的每個操作中，如果數組已滿，則會引發“溢出消息”。在執行以下操作之前，請執行以下步驟。 1. 取大小為`n`的數組。 2. 在第一個位置設置兩個指針，然后設置`front = -1`和`rear = 0`。 ![Initialize array](https://img.kancloud.cn/7d/9c/7d9c3d8e2127ce8e8147a8f847613ab5_766x382.png "Initialize array") 初始化數組和指針 ### 在前面插入此操作在前面添加了一個元素。 1. 檢查前面的位置。 ![Check empty](https://img.kancloud.cn/45/e8/45e87e57642387328902e7b1e27e3335_754x334.png "Deque - insert at the front") 檢查正面 2. 如果為`front < 1`，請重新初始化`front = n-1`（最后一個索引）。 ![Deque - insert at the front](https://img.kancloud.cn/69/cb/69cb33fe578b97033624555201c72c96_754x334.png "Deque - insert at the front") 前端發送 3. 否則，將`front`減小 1。 4. 將新鍵`5`添加到`array[front]`中。 ![Deque - insert](https://img.kancloud.cn/09/69/09696942f424ce1cc694d44924a68015_754x334.png "Deque - insert at the front") 插入鍵 ### 在后面插入此操作在后部增加了一個元素。 1. 檢查數組是否已滿。 ![Deque - insert at rear](https://img.kancloud.cn/45/e8/45e87e57642387328902e7b1e27e3335_754x334.png "Deque - insert at the rear") 檢查完整的 2. 如果數組已滿，請重新初始化`rear = 0`。 3. 否則，將`rear`增加 1。 ![Deque - insert at rear](https://img.kancloud.cn/02/f4/02f43fcaf730a99ce7e7f83a15ab2c70_754x334.png "Deque - insert at the rear") 增加后 4. 將新鍵`5`添加到`array[rear]`中。 ![Deque - insert at rear](https://img.kancloud.cn/b3/87/b3878ff265743bc925c8bf938898e456_754x334.png "Deque - insert at the rear") 插入鍵 ### 從前面刪除該操作從前面刪除一個元素。 1. 檢查數組是否為空。 ![Deque - delete from the front](https://img.kancloud.cn/45/e8/45e87e57642387328902e7b1e27e3335_754x334.png "Deque - delete from the front") 檢查為空 2. 如果數組為空（即`front = -1`），則無法執行刪除操作（**下溢條件**）。 3. 如果雙端隊列只有一個元素（即`front = rear`），請設置`front = -1`和`rear = -1`。 4. 否則，如果`front`位于末尾（即`front = n - 1`），則設置轉到前`front = 0`。 5. 否則，`front = front + 1`。 ![Deque - Increase front](https://img.kancloud.cn/73/e3/73e38e718a320fc3d89fec4f5bbf8857_754x334.png "Deque - delete from the front") 增加前線 ### 從后面刪除此操作從背面刪除一個元素。 1. 檢查數組是否為空。 ![Deque - check empty](https://img.kancloud.cn/45/e8/45e87e57642387328902e7b1e27e3335_754x334.png "Deque - delete from the rear") 檢查為空 2. 如果數組為空（即`front = -1`），則無法執行刪除操作（**下溢條件**）。 3. 如果雙端隊列只有一個元素（即`front = rear`），請設置`front = -1`和`rear = -1`，否則請按照以下步驟操作。 4. 如果`rear`在前面（即`rear = 0`），則設置轉到前`rear = n - 1`。 5. 否則，`rear = rear - 1`。 ![Deque - Decrease rear](https://img.kancloud.cn/9a/fe/9afef5cf1060078d55146b7e6f8438bf_754x334.png "Deque - delete from the rear") 降低后排 ### 檢查空此操作檢查數組是否為空。如果為`front = -1`，則雙端隊列為空。 ### 檢查滿此操作檢查雙端隊列是否已滿。如果`front = 0`和`rear = n - 1`，則雙端隊列已滿。 * * * ## Python，Java 和 C/C++ 示例 ```py # Deque operations in python class Deque: def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def addFront(self, item): self.items.append(item) def addRear(self, item): self.items.insert(0, item) def removeFront(self): return self.items.pop() def removeRear(self): return self.items.pop(0) def size(self): return len(self.items) d = Deque() print(d.isEmpty()) d.addRear(8) d.addRear(5) d.addFront(7) d.addFront(10) print(d.size()) print(d.isEmpty()) d.addRear(11) print(d.removeRear()) print(d.removeFront()) d.addFront(55) d.addRear(45) print(d.items) ``` ```java // Deque operations in Java class Deque { static final int MAX = 100; int arr[]; int front; int rear; int size; public Deque(int size) { arr = new int[MAX]; front = -1; rear = 0; this.size = size; } boolean isFull() { return ((front == 0 && rear == size - 1) || front == rear + 1); } boolean isEmpty() { return (front == -1); } void insertfront(int key) { if (isFull()) { System.out.println("Overflow"); return; } if (front == -1) { front = 0; rear = 0; } else if (front == 0) front = size - 1; else front = front - 1; arr[front] = key; } void insertrear(int key) { if (isFull()) { System.out.println(" Overflow "); return; } if (front == -1) { front = 0; rear = 0; } else if (rear == size - 1) rear = 0; else rear = rear + 1; arr[rear] = key; } void deletefront() { if (isEmpty()) { System.out.println("Queue Underflow\n"); return; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else if (front == size - 1) front = 0; else front = front + 1; } void deleterear() { if (isEmpty()) { System.out.println(" Underflow"); return; } if (front == rear) { front = -1; rear = -1; } else if (rear == 0) rear = size - 1; else rear = rear - 1; } int getFront() { if (isEmpty()) { System.out.println(" Underflow"); return -1; } return arr[front]; } int getRear() { if (isEmpty() || rear < 0) { System.out.println(" Underflow\n"); return -1; } return arr[rear]; } public static void main(String[] args) { Deque dq = new Deque(4); System.out.println("Insert element at rear end : 12 "); dq.insertrear(12); System.out.println("insert element at rear end : 14 "); dq.insertrear(14); System.out.println("get rear element : " + dq.getRear()); dq.deleterear(); System.out.println("After delete rear element new rear become : " + dq.getRear()); System.out.println("inserting element at front end"); dq.insertfront(13); System.out.println("get front element: " + dq.getFront()); dq.deletefront(); System.out.println("After delete front element new front become : " + +dq.getFront()); } } ``` ```c // Deque operations in C #include <stdio.h> #define MAX 10 void addFront(int *, int, int *, int *); void addRear(int *, int, int *, int *); int delFront(int *, int *, int *); int delRear(int *, int *, int *); void display(int *); int count(int *); int main() { int arr[MAX]; int front, rear, i, n; front = rear = -1; for (i = 0; i < MAX; i++) arr[i] = 0; addRear(arr, 5, &front, &rear); addFront(arr, 12, &front, &rear); addRear(arr, 11, &front, &rear); addFront(arr, 5, &front, &rear); addRear(arr, 6, &front, &rear); addFront(arr, 8, &front, &rear); printf("\nElements in a deque: "); display(arr); i = delFront(arr, &front, &rear); printf("\nremoved item: %d", i); printf("\nElements in a deque after deletion: "); display(arr); addRear(arr, 16, &front, &rear); addRear(arr, 7, &front, &rear); printf("\nElements in a deque after addition: "); display(arr); i = delRear(arr, &front, &rear); printf("\nremoved item: %d", i); printf("\nElements in a deque after deletion: "); display(arr); n = count(arr); printf("\nTotal number of elements in deque: %d", n); } void addFront(int *arr, int item, int *pfront, int *prear) { int i, k, c; if (*pfront == 0 && *prear == MAX - 1) { printf("\nDeque is full.\n"); return; } if (*pfront == -1) { *pfront = *prear = 0; arr[*pfront] = item; return; } if (*prear != MAX - 1) { c = count(arr); k = *prear + 1; for (i = 1; i <= c; i++) { arr[k] = arr[k - 1]; k--; } arr[k] = item; *pfront = k; (*prear)++; } else { (*pfront)--; arr[*pfront] = item; } } void addRear(int *arr, int item, int *pfront, int *prear) { int i, k; if (*pfront == 0 && *prear == MAX - 1) { printf("\nDeque is full.\n"); return; } if (*pfront == -1) { *prear = *pfront = 0; arr[*prear] = item; return; } if (*prear == MAX - 1) { k = *pfront - 1; for (i = *pfront - 1; i < *prear; i++) { k = i; if (k == MAX - 1) arr[k] = 0; else arr[k] = arr[i + 1]; } (*prear)--; (*pfront)--; } (*prear)++; arr[*prear] = item; } int delFront(int *arr, int *pfront, int *prear) { int item; if (*pfront == -1) { printf("\nDeque is empty.\n"); return 0; } item = arr[*pfront]; arr[*pfront] = 0; if (*pfront == *prear) *pfront = *prear = -1; else (*pfront)++; return item; } int delRear(int *arr, int *pfront, int *prear) { int item; if (*pfront == -1) { printf("\nDeque is empty.\n"); return 0; } item = arr[*prear]; arr[*prear] = 0; (*prear)--; if (*prear == -1) *pfront = -1; return item; } void display(int *arr) { int i; printf("\n front: "); for (i = 0; i < MAX; i++) printf(" %d", arr[i]); printf(" :rear"); } int count(int *arr) { int c = 0, i; for (i = 0; i < MAX; i++) { if (arr[i] != 0) c++; } return c; } ``` ```cpp // Deque operations in C++ #include <iostream> using namespace std; #define MAX 10 class Deque { int arr[MAX]; int front; int rear; int size; public: Deque(int size) { front = -1; rear = 0; this->size = size; } void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); bool isFull(); bool isEmpty(); int getFront(); int getRear(); }; bool Deque::isFull() { return ((front == 0 && rear == size - 1) || front == rear + 1); } bool Deque::isEmpty() { return (front == -1); } void Deque::insertfront(int key) { if (isFull()) { cout << "Overflow\n" << endl; return; } if (front == -1) { front = 0; rear = 0; } else if (front == 0) front = size - 1; else front = front - 1; arr[front] = key; } void Deque ::insertrear(int key) { if (isFull()) { cout << " Overflow\n " << endl; return; } if (front == -1) { front = 0; rear = 0; } else if (rear == size - 1) rear = 0; else rear = rear + 1; arr[rear] = key; } void Deque ::deletefront() { if (isEmpty()) { cout << "Queue Underflow\n" << endl; return; } if (front == rear) { front = -1; rear = -1; } else if (front == size - 1) front = 0; else front = front + 1; } void Deque::deleterear() { if (isEmpty()) { cout << " Underflow\n" << endl; return; } if (front == rear) { front = -1; rear = -1; } else if (rear == 0) rear = size - 1; else rear = rear - 1; } int Deque::getFront() { if (isEmpty()) { cout << " Underflow\n" << endl; return -1; } return arr[front]; } int Deque::getRear() { if (isEmpty() || rear < 0) { cout << " Underflow\n" << endl; return -1; } return arr[rear]; } int main() { Deque dq(4); cout << "insert element at rear end \n"; dq.insertrear(5); dq.insertrear(11); cout << "rear element: " << dq.getRear() << endl; dq.deleterear(); cout << "after deletion of the rear element, the new rear element: " << dq.getRear() << endl; cout << "insert element at front end \n"; dq.insertfront(8); cout << "front element: " << dq.getFront() << endl; dq.deletefront(); cout << "after deletion of front element new front element: " << dq.getFront() << endl; } ``` * * * ## 雙端隊列復雜度所有上述操作的時間復雜度是恒定的，即`O(1)`。 * * * ## 雙端隊列應用 1. 軟件中的撤消操作。 2. 在瀏覽器中存儲歷史記錄。 3. 為了實現[棧](https://www.programiz.com/dsa/stack)和[隊列](https://www.programiz.com/dsa/queue)。