数据结构之队列（双向队列）

概念

双向队列（Double-ends Queues简称Dequeue）是一种前后2端都可以添加数据（入队）、移除（出队）数据的有序线性表。

特点

双向队列（Deque，全名Double Ended Queue）是一种具有两个指针的线性表，允许从两端都可以进行插入和删除操作即双向队列可以在任意一端进行元素的插入和删除操作，而单向队列只能在一端进行操作。

双向队列支持四种基本操作：

• push_front(x)：将元素x添加到队列头部。
• push_back(x)：将元素x添加到队列尾部。
• pop_front()：移除队列头部的元素，并返回该元素的值。
• pop_back()：移除队列尾部的元素，并返回该元素的值。

双向队列可以看作是一个特殊的队列，它兼具了栈和队列的特点。

栈是一种后进先出(LIFO)的数据结构，只允许在一端进行插入和删除操作；而队列是一种先进先出(FIFO)的数据结构，只允许在一端插入，在另一端删除。而双向队列则可以同时实现这两种功能，既可用于队列，也可用于栈，所以称为“双向”队列。

通常我们使用一个双向链表来实现双向队列，因为插入和删除操作时间复杂度都是O(1)，但是如果要删除中间某个节点则需要O(n)的时间，不过很少需要删除中间的节点，所以在大多数情况下效率是很高的。

在Java中，Java 6引入了一个新的双向队列接口Deque和LinkedList实现类。

Python

在Python中，可以通过collections模块的deque类来实现双向队列（deque）。deque是一种双向队列，即可以从两端进行插入和删除操作。

from collections import deque

# 创建一个空的双向队列
d = deque()

# 在右侧插入元素
d.append(1)  # 默认入队是队尾入队
print(d)  # 输出：deque([1])

# 在左侧插入元素
d.appendleft(2)
print(d)  # 输出：deque([2, 1])

# 弹出最右边的元素
print(d.pop())  # 输出：1   默认入队是队尾出队
print(d)  # 输出：deque([2])

# 弹出最左边的元素
print(d.popleft())  # 输出：2
print(d)  # 输出：deque([])

# 判断双向队列是否为空
print(d)  # 输出：True

# 获取双向队列的长度
print(len(d))  # 输出：0

 Java语言

在Java语言中，可以通过使用LinkedList类来实现双向队列。LinkedList类实现了List接口，并且还实现了Deque接口，Deque接口继承自Queue接口，因此LinkedList可以作为双向队列使用。

对于双向队列，我们可以在队列的两端进行插入和删除操作。LinkedList提供了一系列方法来支持双向队列的操作，包括在队头和队尾插入元素、获取队头和队尾元素、移除队头和队尾元素等。

import java.util.LinkedList;

public class MyDequeueDemo {


    public static void main(String[] args) {
        LinkedList<Integer> deque = new LinkedList<>();

        // 在队尾添加元素
        deque.addLast(1);
        deque.addLast(2);
        deque.addLast(3);

        // 在队头添加元素
        deque.addFirst(0);

        // 获取队头和队尾元素
        System.out.println("队头元素：" + deque.getFirst()); // 输出：0
        System.out.println("队尾元素：" + deque.getLast()); // 输出：3

        // 删除队头和队尾元素
        deque.removeFirst();
        deque.removeLast();

        // 遍历队列
        System.out.println("遍历队列：");
        for (Integer num : deque) {
            System.out.print(num + " "); // 输出：1 2
        }
    }
}

输出：

队头元素：0
队尾元素：3
遍历队列：
1 2 

Javascript

 1 class Deque {
 2     constructor() {
 3         this.items = []; // 存储元素
 4     }
 5 
 6     enqueue(val) {
 7         // 向队列尾部插入元素
 8         this.items.push(val);
 9     }
10 
11     dequeue() {
12         // 删除队列头部元素，并返回删除的元素
13         return this.items.shift();
14     }
15 
16     addFront(val) {
17         // 向队列头部插入元素
18         this.items.unshift(val);
19     }
20 
21     removeEnd() {
22         // 删除队列尾部元素，并返回删除的元素
23         return this.items.pop();
24     }
25 
26     isEmpty() {
27         // 判断队列是否为空
28         return this.items.length === 0;
29     }
30 
31     size() {
32         // 返回队列长度
33         return this.items.length;
34     }
35 }
36 
37 queue= new Deque();
38 queue.enqueue(1)
39 queue.enqueue(2)
40 queue.enqueue(3)
41 console.log(queue)
42 console.log(queue.dequeue())
43 console.log(queue)
44 queue.addFront(4)
45 console.log(queue)
46 queue.removeEnd()
47 console.log(queue)
48 console.log(queue.isEmpty())
49 console.log(queue.size())

输出：

Deque { items: [ 1, 2, 3 ] }
1
Deque { items: [ 2, 3 ] }
Deque { items: [ 4, 2, 3 ] }
Deque { items: [ 4, 2 ] }
false
2