Home >Backend Development >Python Tutorial >Python data structure and algorithm learning double-ended queue
This article brings you relevant knowledge about python, which mainly introduces issues related to double-ended queues, including the basic concepts of double-ended queues, the implementation of double-ended queues, and double-ended queues. The application of end queue, I hope it will be helpful to everyone.
Recommended learning: python tutorial
Double-ended queue is another linear data structure. Although it is also a restricted linear table, unlike stacks and queues, double-ended queues have few restrictions. Its basic operations are also a subset of linear table operations, but from the perspective of data types, they are different from Linear tables are hugely different. This section will introduce the definition of a double-ended queue and its different implementations, and give some practical applications of a double-ended queue.
Through studying this section, you should master the following content:
Double-ended queue (double-end queue, deque) is also a linear list in which insertion and deletion operations are restricted to both ends of the sequence, but unlike stacks and queues The difference is that double-ended queues have few restrictions. For double-ended queues, both the tail (rear) and the head (front) allow elements to be inserted and deleted. New elements can be added to the head or tail of the queue. Likewise, existing elements can be removed from either end. In a sense, a double-ended queue can be considered a combination of a stack and a queue.
Although a double-ended queue has many features of stacks and queues, it does not require following the LIFO principles and limitations defined by these two data structures. FIFO Principle operation element.
In addition to adding and removing elements, the double-ended queue also has auxiliary operations such as initialization, queue empty judgment, and queue length determination. . Specifically, the abstract data type of the deque is defined as follows:
Basic operations:
1. __itit__(): Initialize the double-ended queue
Create an empty deque
˜ 2. size(): Get and return the number n
of elements contained in the double-ended queue. ˜ ˜If the double-ended queue is empty, return the integer 0
˜ ˜ 3. isempty(): Determine whether it is empty. End queue
judge whether the element is stored in the double-ended queue
4. addfront(data): Add element to the head of the double-ended queue
Insert the element data into the head of the queue
5. addrear(data): Double Add elements to the end of the double-ended queue
Insert element data into the end of the queue
6. removefront(): Delete the head element of the double-ended queue
Delete and return the head element
7. removerear(): Delete The tail element of the double-ended queue
˜ ˜Delete and return the tail element
Like the ordinary queue, the double-ended queue also has sequential storage and There are two storage representation methods of chain storage.
Similar to the sequential queue, the sequential storage structure of the double-ended queue uses a set of storage units with consecutive addresses to store sequentially from the double-ended queue. From the elements from the head of the queue to the tail of the double-ended queue, two pointers front and rear are required to indicate the positions of the queue head element and the queue tail element respectively. When initializing an empty double-ended queue, front=rear=0, when an element enters the queue, rear increases by 1, and when an element dequeues, front increases by 1 , and in order to reuse free space, we assume that the sequential double-ended queue has a tail ring space, and the last space and the first space are regarded as continuous spaces (for specific reasons, please refer to
The same sequential double-ended queue can be of fixed length and dynamic length. When the double-ended queue is full, the fixed-length sequential double-ended queue will throw a double-ended queue full exception, and the dynamic sequential double-ended queue will throw a double-ended queue full exception. Free space will be dynamically applied for.
Initialization of sequential double-ended queue requires 4 pieces of information: deque List is used to store data elements , max_size is used to store the maximum length of the queue list, and front and rear are used to record the head and tail elements of the queue respectively. index of:
class Deque: def __init__(self, max_size=6): self.max_size = max_size self.deque = [None] * self.max_size self.front = 0 self.rear = 0
Since front and rear are used to record the head element and tail element respectively The index of the element, so we can easily calculate the length of the double-ended queue; at the same time, we need to consider that the double-ended queue is a circular queue, front may be larger than rear, and cannot be passed directly rear-front, we need to use formula calculation to solve this problem:
Python The implementation is as follows:
def size(self): return (self.rear-self.front+self.max_size) % self.max_size
You can easily determine whether the double-ended queue is empty based on the values of front and rear:
def isempty(self): return self.rear==self.front
According to the values of front and rear, it is easy to determine whether there is free space in the double-ended queue:
def isfull(self): return ((self.rear+1) % self.max_size == self.front)
When adding elements, you need to first determine whether there is free space in the double-ended queue, and then determine the size of the double-ended queue according to the Long sequential deque or dynamic sequential deque, the operation of adding elements is slightly different:
[Add element operation of fixed-length sequential deque] If the queue is full, an exception is thrown:
# 注意队头和队尾修改索引的添加元素的不同顺序
def addrear(self, data):
if not self.isfull():
self.deque[self.rear] = data
self.rear = (self.rear+1) % self.max_size else:
raise IndexError("Full Deque Exception")
def addfront(self, data):
if self.isfull():
self.resize()
if self.isempty():
# 当Python data structure and algorithm learning double-ended queue
self.deque[self.rear] = data
self.rear = (self.rear+1) % self.max_size else:
self.front = (self.front - 1 + self.max_size) % self.max_size
self.deque[self.front] = data
[Add element operation of dynamic sequence double-ended queue] If the double-ended queue is full, apply for new space first, and then perform the add operation:
def resize(self): new_size = 2 * self.max_size new_deque = [None] * new_size d = new_size - self.max_size for i in range(self.max_size): new_deque[(self.front+i+d) % new_size] = self.deque[(self.front+i) % self.max_size] self.deque = new_deque self.front = (self.front+d) % new_size self.max_size = new_size # 注意队头和队尾修改索引的添加元素的不同顺序 def addrear(self, data): if self.isfull(): self.resize() self.deque[self.rear] = data self.rear = (self.rear+1) % self.max_size def addfront(self, data): if self.isfull(): self.resize() self.front = (self.front - 1 + self.max_size) % self.max_size self.deque[self.front] = data
With dynamic sequence Similar to queues, we also need to consider the index after copying, otherwise there may be unusable free space:
The time complexity of adding elements is O(1). Although when the dynamic sequential double-ended queue is full, the elements in the original double-ended queue need to be copied to the new double-ended queue first, and then new elements are added. However, refer to the introduction of the sequential table append operation in "Sequence Table and Its Operation Implementation", Due to the total time of n add element operationsT(n) and O(n) is directly proportional, so its amortized time complexity can be consideredO(1).
If the double-ended queue is not empty, delete and return the element at the specified end:
# 注意队头和队尾修改索引的删除元素的不同顺序
def removefront(self):
if not self.isempty():
result = self.deque[self.front]
self.front = (self.front+1) % self.max_size return result else:
raise IndexError("Empty Deque Exception")
def removerear(self):
if not self.isempty():
self.rear = (self.rear - 1 + self.max_size) % self.max_size
result = self.deque[self.rear]
return result else:
raise IndexError("Empty Deque Exception")
Another storage representation of a double-ended queue is to use a chained storage structure, so it is also often called a chained double-ended queue, where## The #addfront operation and the addrear operation are implemented by inserting elements at the head and tail of the linked list respectively, while the removefront operation and the removerear operation are respectively This is achieved by deleting nodes from the head and tail. In order to reduce the time complexity of deleting nodes at the tail, a double-ended queue is implemented based on a doubly linked list.
class Node: def __init__(self, data=None): self.data = data self.next = None def __str__(self): return str(self.data)2.2.2 Initialization of double-ended queue In the initialization function of the double-ended queue, make the head pointer
front and the tail pointer rear both point to None, and initialize the length of the double-ended queue:
class Deque: def __init__(self): self.front = None self.rear = None self.num = 02.2.3 Find the length of the double-ended queueReturn the value of
num to find the length of the double-ended queue The length of The length of the queue can easily determine whether it is an empty double-ended queue:
def size(self): return self.num
2.2.5 Adding elements When adding elements to a double-ended queue, you can insert new elements at the end or head of the queue. element, so you need to modify the front
pointers, and also modify the node'sprevious pointers; if you add an element The former double-ended queue is empty and needs to be processed accordingly:
def addrear(self, data): node = Node(data) # 如果添加元素前Python data structure and algorithm learning double-ended queue为空，则添加结点时，需要将front指针也指向该结点 if self.front is None: self.rear = node self.front = node else: node.previous = self.rear self.rear.next = node self.rear = node self.num += 1 def addfront(self, data): node = Node(data) # 如果添加元素前Python data structure and algorithm learning double-ended queue为空，则添加结点时，需要将rear指针也指向该结点 if self.rear is None: self.front = node self.rear = node else: node.next = self.front self.front.previous = node self.front = node self.num += 1
若Python data structure and algorithm learning double-ended queue不空，可以从删除队头或队尾元素并返回，删除操作需要更新队头指针 front 以及尾指针 rear，同时也要修改结点的 next 和 previous 指针，若出队元素尾队中最后一个结点，还需要进行相应处理：
def removefront(self):
if self.isempty():
raise IndexError("Empty Queue Exception")
result = self.front.data
self.front = self.front.next
self.num -= 1
if self.isempty():
self.rear = self.front else:
# 若删除操作完成后，Python data structure and algorithm learning double-ended queue不为空，将 front 指针的前驱指针指向 None
self.front.previous = None
return result
def removerear(self):
if self.isempty():
raise IndexError("Empty Queue Exception")
result = self.rear.data
self.rear = self.rear.previous
self.num -= 1
if self.isempty():
self.front = self.rear else:
# 若删除操作完成后，Python data structure and algorithm learning double-ended queue不为空，将 rear 指针的后继指针指向 None
self.rear.next = None
return result
Python data structure and algorithm learning double-ended queue的不同实现对比与栈的不同实现类似，可以参考《栈及其操作实现》。
接下来，我们首先测试上述实现的Python data structure and algorithm learning double-ended queue，以验证操作的有效性，然后利用实现的基本操作来解决实际算法问题。
首先初始化一个顺序Python data structure and algorithm learning double-ended queue deque，然后测试相关操作：
# 初始化一个最大长度为5的Python data structure and algorithm learning double-ended queuedq = Deque(5)print('Python data structure and algorithm learning double-ended queue空?', dq.isempty())for i in range(3):
print('队头添加元素：', 2*i)
dq.addfront(2*i)
print('队尾添加元素：', 2*i+1)
dq.addrear(2*i+1)print('Python data structure and algorithm learning double-ended queue长度为：', dq.size())for i in range(3):
print('队尾删除元素：', dq.removerear())
print('队头删除元素：', dq.removefront())print('Python data structure and algorithm learning double-ended queue长度为：', dq.size())
测试程序输出结果如下：
Python data structure and algorithm learning double-ended queue空? True队头添加元素： 0队尾添加元素： 1队头添加元素： 2队尾添加元素： 3队头添加元素： 4队尾添加元素： 5Python data structure and algorithm learning double-ended queue长度为： 6队尾删除元素： 5队头删除元素： 4队尾删除元素： 3队头删除元素： 2队尾删除元素： 1队头删除元素： 0Python data structure and algorithm learning double-ended queue长度为： 0
首先初始化一个链Python data structure and algorithm learning double-ended queue queue，然后测试相关操作：
# 初始化新队列dq = Deque()print('Python data structure and algorithm learning double-ended queue空?', dq.isempty())for i in range(3):
print('队头添加元素：', i)
dq.addfront(2*i)
print('队尾添加元素：', i+3)
dq.addrear(2*i+1)print('Python data structure and algorithm learning double-ended queue长度为：', dq.size())for i in range(3):
print('队尾删除元素：', dq.removerear())
print('队头删除元素：', dq.removefront())print('Python data structure and algorithm learning double-ended queue长度为：', dq.size())
测试程序输出结果如下：
Python data structure and algorithm learning double-ended queue空? True队头添加元素： 0队尾添加元素： 3队头添加元素： 1队尾添加元素： 4队头添加元素： 2队尾添加元素： 5Python data structure and algorithm learning double-ended queue长度为： 6队尾删除元素： 5队头删除元素： 4队尾删除元素： 3队头删除元素： 2队尾删除元素： 1队头删除元素： 0Python data structure and algorithm learning double-ended queue长度为： 0
[1] 给定一字符串 string (如：abamaba)，检查其是否为回文。
使用Python data structure and algorithm learning double-ended queue可以快速检查一字符串是否为回文序列，只需要将字符串中字符依次入队，然后从Python data structure and algorithm learning double-ended queue两端依次弹出元素，对比它们是否相等：
def ispalindrome(string): deque = Deque() for ch in string: deque.addfront(ch) flag = True while deque.size() > 1 and flag: ch1 = deque.removefront() ch2 = deque.removerear() if ch1 != ch2: flag = False return flag
验证算法有效性：
print('abcba是否为回文序列：', ispalindrome('abcba'))print('charaahc是否为回文序列：', ispalindrome('charaahc'))
结果输出如下：
abcba是否为回文序列： True charaahc是否为回文序列： False
推荐学习：python教程
The above is the detailed content of Python data structure and algorithm learning double-ended queue. For more information, please follow other related articles on the PHP Chinese website!