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

0. Learning objectives

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:

• Basic concepts and different implementation methods of double-ended queues
• Implementation and time complexity of basic operations of double-ended queues
• Use the basic operations of double-ended queues to implement complex algorithms

1. Basic concepts of double-ended queues

1.1 Basic concepts of double-ended queues

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.

1.2 Double-ended queue abstract data type

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

2. Implementation of the double-ended queue

Like the ordinary queue, the double-ended queue also has sequential storage and There are two storage representation methods of chain storage.

2.1 Implementation of sequential double-ended queue

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.

2.1.1 Initialization of double-ended queue

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

2.1.2 Find the length of the double-ended queue

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

2.1.3 Judgment Double-ended queue is empty

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

2.1.4 Determining that the double-ended queue is full

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)

2.1.5 Add elements to the head and tail of the double-ended queue

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 operations$T(n)$ and $O(n)$ is directly proportional, so its amortized time complexity can be considered$O(1)$.

2.1.6 Delete the element at the head or tail of the queue

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")

2.2 Implementation of chained double-ended queue

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.

2.2.1 Double-ended queue node

The node implementation of double-ended queue is no different from that of 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 = 0

2.2.3 Find the length of the double-ended queue

Return 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

rear

and

front

pointers, and also modify the node's

next

and

previous 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

2.2.6 删除元素

若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

2.3 Python data structure and algorithm learning double-ended queue的不同实现对比

Python data structure and algorithm learning double-ended queue的不同实现对比与栈的不同实现类似，可以参考《栈及其操作实现》。

3. Python data structure and algorithm learning double-ended queue应用

接下来，我们首先测试上述实现的Python data structure and algorithm learning double-ended queue，以验证操作的有效性，然后利用实现的基本操作来解决实际算法问题。

3.1 顺序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

3.2 链Python data structure and algorithm learning double-ended queue的应用

首先初始化一个链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

3.3 利用Python data structure and algorithm learning double-ended queue基本操作实现复杂算法

[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!