Shulou(Shulou.com)06/01 Report--

This article mainly introduces the relevant knowledge of how to achieve Python double-ended queue, the content is detailed and easy to understand, the operation is simple and fast, and it has a certain reference value. I believe you will gain something after reading this article on how to realize Python double-ended queue. Let's take a look at it.

0. Learning goal

Double-ended queues are another linear data structure. Although it is also a restricted linear table, unlike stacks and queues, double-ended queues have few restrictions, and its basic operation is a subset of linear table operations, but in terms of data types, they are very different from linear tables. This section introduces the definition of double-ended queues and their different implementations, and gives some practical applications of double-ended queues.

Through this section, you should master the following:

The basic concept of double-ended queue and its different implementation methods

Implementation and time complexity of basic Operation of double-ended queue

Using the basic operation of double-ended queue to realize complex algorithm

1. Basic concept of double-ended queue 1.1 basic concept of double-ended queue

Double-ended queues (double-end queue, deque) are also linear tables in which insert and delete operations are limited to both ends of the sequence, but unlike stacks and queues, double-ended queues have few restrictions. For double-ended queues, both rear and front allow insertion and deletion of elements. New elements can be added either to the head of the line or to the end of the line. In the same way, existing elements can be removed from either end. In a sense, a double-ended queue can be thought of as a combination of stack and queue.

Although a double-ended queue has many features of stack and queue, it does not require elements to be manipulated according to the LIFO and FIFO principles defined by these two data structures.

1.2 double-ended queue Abstract data Type

In addition to adding and removing elements, double-ended queues also have auxiliary operations such as initialization, judging queue emptiness, and finding queue length. Specifically, the abstract data type of a double-ended queue is defined as follows:

Basic operation of  :

   1. _ _ itit__ (): initializes a double-ended queue

    creates an empty double-ended queue

   2. Size (): gets and returns the number of elements in the double-ended queue n

    returns an integer 0 if the double-ended queue is empty

   3. Isempty (): determines whether the double-ended queue is empty

    determines whether elements are stored in a double-ended queue.

   4. Addfront (data): add elements to the head of a double-ended queue

    inserts element data into the head of the line

   5. Addrear (data): add elements at the end of a double-ended queue

    inserts the element data into the end of the line

   6. Removefront (): delete the queue header element of the double-ended queue

    deletes and returns the line header element

   7. Removerear (): delete the tail element of a double-ended queue

    deletes and returns the tail-end element

two。 Implementation of double-ended queue

Like ordinary queues, double-ended queues also have two storage representations: sequential storage and 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 consecutive storage cells to store the elements from the head of the double-ended queue to the end of the double-ended queue in turn. At the same time, two pointers front and rear are needed to indicate the location of the head element and the tail element of the queue. When initializing the empty double-ended queue, front=rear=0, when the element joins the queue, rear adds 1, and when the element leaves the queue, front adds 1. At the same time, in order to reuse the free space, we assume the tail ring space of the sequential double-ended queue, and the last space and the first space are regarded as contiguous space (for specific reasons):

The same sequential double-ended queues can be of fixed length and dynamic length. When the double-ended queues are full, the fixed-length sequential double-ended queues will throw a double-ended queue full exception, and the dynamic sequential double-ended queues will dynamically apply for free space.

2.1.1 initialization of double-ended queues

The initialization of a sequential double-ended queue requires four pieces of information: the 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 indexes of the header and tail elements, respectively:

Class Deque: def _ init__ (self, max_size=6): self.max_size = max_size self.deque = [None] * self.max_size self.front = 0 self.rear = 02.1.2 calculate the double-ended queue length

Since front and rear are used to record the indexes of the head and tail elements of the queue, we can easily calculate the length of the double-end queue. At the same time, we need to consider that the double-end queue is listed as a circular queue. Front may be greater than rear and cannot be directly passed through rear-front. We need to use formula calculation to solve this problem:

The Python implementation is as follows:

Def size (self): return (self.rear-self.front+self.max_size)% self.max_size2.1.3 determines that the double-end queue is empty

You can easily determine whether the double-end queue is empty according to the values of front and rear:

Def isempty (self): return self.rear==self.front2.1.4 decides that the double-end queue is full

You can easily determine whether there is any free space in the double-end queue according to the values of front and rear:

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 any free space in the double-end queue, and then add elements slightly differently according to whether the double-end queue is listed as a fixed-length order double-end queue or a dynamic order two-end queue:

[add elements to a fixed-length sequence double-ended queue] if the queue is full, an exception is thrown:

# Note the different order of 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 (): # when 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 sequential 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 # Note the different order def addrear (self) of the elements added to the modified index at the beginning and end of the line 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

Similar to dynamic sequential queues, we also need to consider replicated indexes, otherwise there may be unusable free space:

The time complexity of adding elements is O (1). Although when the dynamic sequence 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 need to be added, but referring to the introduction of the sequence table append operation in "sequence Table and its Operation implementation", because the total time T (n) of n adding element operations is proportional to O (n), the amortization time complexity can be regarded as O (1).

2.1.6 Delete elements at the beginning or end of the line

If the double-end queue is not empty, delete and return the specified end element:

# Note: 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 chain double-ended queue implementation

Another storage representation of double-ended queues is the chained storage structure, so it is often called chained double-ended queues, in which addfront and addrear operations are implemented by inserting elements at the head and tail of the linked list, while removefront and removerear operations are implemented by deleting nodes from the head and tail, respectively. In order to reduce the time complexity of deleting nodes at the tail, the double-ended queue is implemented based on the two-way linked list.

2.2.1 double-ended queue node

The node implementation of a double-ended queue is no different from a two-way 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 queues

In the initialization function of the double-end queue, make its head pointer front and end-of-queue pointer rear point to None, and initialize the length of the two-end queue:

Class Deque: def _ _ init__ (self): self.front = None self.rear = None self.num = 02.2.3 calculate the double-ended queue length

The returned value of num is used to calculate the length of the double-ended queue. If there is no num attribute, you need to traverse the entire linked list to get the length of the double-ended queue:

Def size (self): return self.num2.2.4 determines that the double-end queue is empty

According to the length of the double-ended queue, it is easy to judge whether it is an empty double-ended queue:

Def isempty (self): return self.num 1 and flag: ch2 = deque.removefront () ch3 = deque.removerear () if ch2! = ch3: flag = False return flag

Verify the effectiveness of the algorithm:

Print ('abcba is a palindrome sequence:', ispalindrome ('abcba')) print (' charaahc is a palindrome sequence:', ispalindrome ('charaahc'))

The output is as follows:

Whether abcba is a palindrome sequence: whether Truecharaahc is a palindrome sequence: this is the end of False's article on "how to implement Python double-ended queues". Thank you for reading! I believe that everyone has a certain understanding of the knowledge of "how to realize Python double-ended queue". If you want to learn more knowledge, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.