一种特殊的队列,允许在两端(前端和后端)进行元素的插入和删除操作,它结合了栈和队列的特性
双端队列(Double-ended queue,简称Deque)是一种特殊的队列,它允许在队列的两端(前端和后端)进行元素的插入和删除操作。与普通队列(只允许在一端插入,另一端删除)和栈(只允许在同一端插入和删除)不同,双端队列提供了更高的灵活性。

双端队列可以被视为同时结合了栈和队列特性的数据结构,既可以作为栈使用(后进先出),也可以作为队列使用(先进先出)。
▼Java复制代码import java.util.ArrayDeque; import java.util.Deque; public class DequeExample { public static void main(String[] args) { // 创建双端队列 Deque<Integer> deque = new ArrayDeque<>(); // 在前端添加元素 deque.addFirst(10); deque.offerFirst(20); // 优先使用offer方法,不会抛异常 // 在后端添加元素 deque.addLast(30); deque.offerLast(40); System.out.println("双端队列: " + deque); // 输出: [20, 10, 30, 40] // 查看前端元素(不移除) int first = deque.peekFirst(); System.out.println("前端元素: " + first); // 输出: 20 // 查看后端元素(不移除) int last = deque.peekLast(); System.out.println("后端元素: " + last); // 输出: 40 // 从前端移除元素 int removedFirst = deque.pollFirst(); System.out.println("从前端移除: " + removedFirst); // 输出: 20 // 从后端移除元素 int removedLast = deque.pollLast(); System.out.println("从后端移除: " + removedLast); // 输出: 40 System.out.println("最终双端队列: " + deque); // 输出: [10, 30] // 使用双端队列作为栈 Deque<Integer> stack = new ArrayDeque<>(); stack.push(50); // 等同于addFirst() stack.push(60); System.out.println("栈顶元素: " + stack.peek()); // 输出: 60 System.out.println("弹出元素: " + stack.pop()); // 输出: 60 } }
▼Javascript复制代码// JavaScript中没有内置的双端队列,可以使用数组实现 class Deque { constructor() { this.items = []; } // 在前端添加元素 addFirst(item) { this.items.unshift(item); } // 在后端添加元素 addLast(item) { this.items.push(item); } // 从前端移除元素 removeFirst() { if (this.isEmpty()) { return null; } return this.items.shift(); } // 从后端移除元素 removeLast() { if (this.isEmpty()) { return null; } return this.items.pop(); } // 查看前端元素 peekFirst() { if (this.isEmpty()) { return null; } return this.items[0]; } // 查看后端元素 peekLast() { if (this.isEmpty()) { return null; } return this.items[this.items.length - 1]; } // 判断双端队列是否为空 isEmpty() { return this.items.length === 0; } // 获取双端队列大小 size() { return this.items.length; } } // 使用示例 const deque = new Deque(); deque.addFirst(10); deque.addFirst(20); deque.addLast(30); deque.addLast(40); console.log("双端队列:", deque.items); // 输出: [20, 10, 30, 40] console.log("前端元素:", deque.peekFirst()); // 输出: 20 console.log("后端元素:", deque.peekLast()); // 输出: 40 console.log("从前端移除:", deque.removeFirst()); // 输出: 20 console.log("从后端移除:", deque.removeLast()); // 输出: 40 console.log("最终双端队列:", deque.items); // 输出: [10, 30]
▼Python复制代码from collections import deque # 创建双端队列 deque_obj = deque() # 在前端添加元素 deque_obj.appendleft(10) deque_obj.appendleft(20) # 在后端添加元素 deque_obj.append(30) deque_obj.append(40) print("双端队列:", list(deque_obj)) # 输出: [20, 10, 30, 40] # 查看前端元素(不移除) first = deque_obj[0] print("前端元素:", first) # 输出: 20 # 查看后端元素(不移除) last = deque_obj[-1] print("后端元素:", last) # 输出: 40 # 从前端移除元素 removed_first = deque_obj.popleft() print("从前端移除:", removed_first) # 输出: 20 # 从后端移除元素 removed_last = deque_obj.pop() print("从后端移除:", removed_last) # 输出: 40 print("最终双端队列:", list(deque_obj)) # 输出: [10, 30] # 自定义双端队列实现 class MyDeque: def __init__(self): self.items = [] def add_first(self, item): self.items.insert(0, item) def add_last(self, item): self.items.append(item) def remove_first(self): if self.is_empty(): return None return self.items.pop(0) def remove_last(self): if self.is_empty(): return None return self.items.pop() def peek_first(self): if self.is_empty(): return None return self.items[0] def peek_last(self): if self.is_empty(): return None return self.items[-1] def is_empty(self): return len(self.items) == 0 def size(self): return len(self.items)
▼Go复制代码package main import ( "container/list" "fmt" ) // 使用双向链表实现双端队列 type Deque struct { list *list.List } // 创建新的双端队列 func NewDeque() *Deque { return &Deque{list: list.New()} } // 在前端添加元素 func (d *Deque) AddFirst(value interface{}) { d.list.PushFront(value) } // 在后端添加元素 func (d *Deque) AddLast(value interface{}) { d.list.PushBack(value) } // 从前端移除元素 func (d *Deque) RemoveFirst() interface{} { if d.IsEmpty() { return nil } return d.list.Remove(d.list.Front()) } // 从后端移除元素 func (d *Deque) RemoveLast() interface{} { if d.IsEmpty() { return nil } return d.list.Remove(d.list.Back()) } // 查看前端元素 func (d *Deque) PeekFirst() interface{} { if d.IsEmpty() { return nil } return d.list.Front().Value } // 查看后端元素 func (d *Deque) PeekLast() interface{} { if d.IsEmpty() { return nil } return d.list.Back().Value } // 判断双端队列是否为空 func (d *Deque) IsEmpty() bool { return d.list.Len() == 0 } // 获取双端队列大小 func (d *Deque) Size() int { return d.list.Len() } func main() { deque := NewDeque() deque.AddFirst(10) deque.AddFirst(20) deque.AddLast(30) deque.AddLast(40) fmt.Println("前端元素:", deque.PeekFirst()) // 输出: 20 fmt.Println("后端元素:", deque.PeekLast()) // 输出: 40 fmt.Println("从前端移除:", deque.RemoveFirst()) // 输出: 20 fmt.Println("从后端移除:", deque.RemoveLast()) // 输出: 40 fmt.Println("队列大小:", deque.Size()) // 输出: 2 }
▼C复制代码#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX_SIZE 100 typedef struct { int array[MAX_SIZE]; int front; int rear; int size; } Deque; // 初始化双端队列 void initialize(Deque* deque) { deque->front = 0; deque->rear = 0; deque->size = 0; } // 判断双端队列是否为空 bool isEmpty(Deque* deque) { return deque->size == 0; } // 判断双端队列是否已满 bool isFull(Deque* deque) { return deque->size == MAX_SIZE; } // 在前端添加元素 bool addFirst(Deque* deque, int item) { if (isFull(deque)) { return false; } // 前端指针向前移动(循环) deque->front = (deque->front - 1 + MAX_SIZE) % MAX_SIZE; deque->array[deque->front] = item; deque->size++; return true; } // 在后端添加元素 bool addLast(Deque* deque, int item) { if (isFull(deque)) { return false; } deque->array[deque->rear] = item; deque->rear = (deque->rear + 1) % MAX_SIZE; deque->size++; return true; } // 从前端移除元素 bool removeFirst(Deque* deque, int* result) { if (isEmpty(deque)) { return false; } *result = deque->array[deque->front]; deque->front = (deque->front + 1) % MAX_SIZE; deque->size--; return true; } // 从后端移除元素 bool removeLast(Deque* deque, int* result) { if (isEmpty(deque)) { return false; } deque->rear = (deque->rear - 1 + MAX_SIZE) % MAX_SIZE; *result = deque->array[deque->rear]; deque->size--; return true; } // 查看前端元素 bool peekFirst(Deque* deque, int* result) { if (isEmpty(deque)) { return false; } *result = deque->array[deque->front]; return true; } // 查看后端元素 bool peekLast(Deque* deque, int* result) { if (isEmpty(deque)) { return false; } int index = (deque->rear - 1 + MAX_SIZE) % MAX_SIZE; *result = deque->array[index]; return true; } // 获取双端队列大小 int size(Deque* deque) { return deque->size; } int main() { Deque deque; initialize(&deque); addFirst(&deque, 10); addFirst(&deque, 20); addLast(&deque, 30); addLast(&deque, 40); int first, last; peekFirst(&deque, &first); peekLast(&deque, &last); printf("前端元素: %d\n", first); // 输出: 20 printf("后端元素: %d\n", last); // 输出: 40 int removedFirst, removedLast; removeFirst(&deque, &removedFirst); removeLast(&deque, &removedLast); printf("从前端移除: %d\n", removedFirst); // 输出: 20 printf("从后端移除: %d\n", removedLast); // 输出: 40 printf("队列大小: %d\n", size(&deque)); // 输出: 2 return 0; }
▼C++复制代码#include <iostream> #include <deque> int main() { // 使用STL的deque std::deque<int> deque; // 在前端添加元素 deque.push_front(10); deque.push_front(20); // 在后端添加元素 deque.push_back(30); deque.push_back(40); std::cout << "前端元素: " << deque.front() << std::endl; // 输出: 20 std::cout << "后端元素: " << deque.back() << std::endl; // 输出: 40 // 从前端移除元素 deque.pop_front(); std::cout << "从前端移除后的前端元素: " << deque.front() << std::endl; // 输出: 10 // 从后端移除元素 deque.pop_back(); std::cout << "从后端移除后的后端元素: " << deque.back() << std::endl; // 输出: 30 std::cout << "队列大小: " << deque.size() << std::endl; // 输出: 2 std::cout << "队列是否为空: " << (deque.empty() ? "是" : "否") << std::endl; // 输出: 否 // 使用迭代器遍历 std::cout << "双端队列内容: "; for (const auto& item : deque) { std::cout << item << " "; } std::cout << std::endl; // 输出: 10 30 return 0; }
使用循环数组实现双端队列,需要维护前端和后端两个指针,并在边界条件下进行循环操作。优点是空间利用率高,缺点是需要预先分配固定大小的空间。
使用双向链表实现双端队列,每个节点包含前驱和后继指针。这种实现的优点是可以动态调整大小,不需要预先分配空间;缺点是每个元素需要额外空间存储指针,且内存不连续。
有些实现,如C++的std::deque,使用分段数组等技术优化性能,结合了数组和链表的优点。(Java的ArrayDeque则是基于可扩容的循环数组实现的。)
1)双端队列与普通队列的主要区别是什么?
2)若使用双端队列实现栈,应该使用哪些操作方法?
3)双端队列在两端操作的时间复杂度是多少?
测验答案
1)双端队列允许在队列的两端(前端和后端)进行元素的插入和删除操作,而普通队列只允许在一端(后端)插入元素,在另一端(前端)删除元素。双端队列更加灵活,既可以用作栈,也可以用作队列。
2)使用双端队列实现栈只使用前端(或只使用后端)的操作方法,即:
- 压栈:addFirst()/offerFirst()或addLast()/offerLast()
- 出栈:removeFirst()/pollFirst()或removeLast()/pollLast()
- 查看栈顶:peekFirst()或peekLast()
3)时间复杂度为O(1)。
双端队列是一种强大且灵活的数据结构,通过上述练习题目,可以帮助大家更好地理解和应用它。