[Python data structure series] ☀️ Queue (sequential queue, chain queue, double ended queue) - knowledge point explanation + code implementation ☀️

Soul torture: why learn data structures?
Data structure, to understand it bluntly, is to study the storage mode of data. Data storage has only one purpose, that is, to facilitate the reuse of data in the later stage. Therefore, the storage of data in computer storage space is by no means random, which requires us to choose a good way to store data, which is also the core content of data structure.
It can be said that data structure is the basis of all programming. Learning data structure is learning an idea: how to transform real problems into computer language representation.
For those who study computer, learning data structure is the basic skill. For friends who are not computer majors but want to develop in the direction of data analysis, big data, or make a big leap in the use of Python in the future, learning data structure is a very important exercise of logical thinking ability, which can be of great help in job hunting, career development, problem solving, etc.

Stack and queue of data structure

1. Queue storage structure

1.1 basic introduction to queue

Queue, like stack, is also a * * linear storage structure with strict requirements for data storage and retrieval.
**

Different from the stack structure, both ends of the queue are "open", which requires that data can only enter from one end and exit from the other end, as shown in Figure 1:

Generally, one end of incoming data is called "queue tail", one end of outgoing data is called "queue head", the process of data elements entering the queue is called "queue in", and the process of data elements leaving the queue is called "queue out".

Moreover, the data in and out of the queue should follow the principle of "first in, first out", that is, the data elements of the most advanced queue should also be out of the queue first. Take the queue in Figure 1 for example. From the storage status of data in the queue, it can be analyzed that element 1 is the most advanced queue, followed by element 2 and finally element 3. At this time, if element 3 is out of the queue, according to the "first in, first out" characteristics of the queue, element 1 should be out of the queue first, element 2 should be out of the queue, and then element 3 should be out of the queue.

Note: stack and queue should not be confused. The stack structure is sealed at one end and is characterized by "first in and last out"; Both ends of the queue are open, characterized by "first in, first out".

Therefore, the linear storage structure that data enters from one end of the table and exits from the other end and follows the "first in, first out" principle is queue.

1.2 implementation of queue

There are two ways to implement queue storage structure:

(1) Sequential queue: queue structure implemented on the basis of sequential table;

(2) Chain queue: queue structure implemented on the basis of linked list;

The difference between the two is only the difference between the sequential list and the linked list, that is, in the actual physical space, the queue stored in the data set is the sequential queue, and the queue stored in the decentralized storage is the chain queue.

In real life, queue applications can be seen everywhere, such as queuing to buy XXX, hospital registration system, etc., which adopt the queue structure.

Take queuing to buy tickets as an example. All people line up in a line. Those who arrive first are in the front, and those who arrive later can only wait from the end of the line. Everyone in the line must wait until all the people in front of him have successfully bought tickets and left the line from the head of the line before it is his turn to buy tickets. This is a typical queue structure.

2. Sequential queue

2.1 basic introduction to sequential queue

Sequential queue, that is, the queue structure simulated by sequential table.
We know that queues have the following two characteristics:
(1) data enters from one end of the queue and exits from the other end;
(2) data entry and exit shall follow the principle of "first in, first out";
Therefore, as long as the sequence table is used to operate the data according to the above two requirements, the sequence queue can be realized. First, let's learn the simplest implementation method.

2.2 simple implementation of sequential queue

Because the bottom layer of the sequential queue uses arrays, it is necessary to apply for a large enough memory space to initialize the sequential queue in advance. In addition, in order to meet the requirements of data from the end of the queue, the head of the queue and the first in first out in the sequential queue, we also need to define two pointers (top and rear) to point to the head of the queue and the tail of the queue, as shown in figure 1:

Because the initial state of the sequential queue does not store any elements, the top pointer and the rear pointer coincide. Because the bottom implementation of the sequential queue depends on the array, top and rear are actually two variables, and their values are the subscripts of the array positions of the queue head element and the queue tail element respectively.

On the basis of Fig. 1, when a data element enters the queue, the corresponding implementation operation is to store it in the array position pointed to by the pointer real, and then real + 1; When the team head element needs to be out of the team, you only need to do the top+1 operation.

For example, on the basis of Figure 1, the implementation operation of storing {1,2,3,4} in sequential queue is shown in Figure 2:

Based on Figure 2, the implementation process of data output queue in sequential queue is shown in Figure 3:

Code implementation: sequential representation and implementation of queues (difficulty: ★)

Realize basic functions: (including but not limited to, and can continue to expand according to their own capabilities)

(1) Initialize queue

(2) Determine whether the queue is empty

(3) Returns the queue header element

(4) Returns the length of the queue

(5) Join: adds an element to the end of the queue

(6) Out of line: delete the team head element

(7) Traversal queue

(8) Empty queue

[note]: stack is first in first out, last in first out, queue is first in first out, last in last out!

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/7/27 16:09 
# @Author : vaxtiandao
# @File : ds_queue.py
# coding=utf-8

"""
This time, the definition of sequential queue and related functions are widely used Python The function of the list carried by itself
"""
class Queue(object):
    """queue"""
    # Queue initialization
    def __init__(self):
        self.items = []

    # Determine whether the queue is empty
    def is_empty(self):
        return self.items == []

    # Element team
    def enqueue(self, item):
        """Enter queue"""
        self.items.insert(0,item)

    # The first element of the team is out of the team
    def dequeue(self):
        """Out of queue"""
        return self.items.pop()

    # Return queue length
    def size(self):
        """Return size"""
        return len(self.items)

    # Empty queue
    def clear(self):
        self.items.clear()

    # Get team leader element
    def getTop(self):
        return self.items[self.size()-1]

    # Traversal queue
    def display(self):
        return self.items

if __name__ == "__main__":
    q = Queue()
    print("---------------------")
    print("Queue after initialization:", q)
    print("---------------------")
    print("Whether the current queue is empty:", q.is_empty())
    print("---------------------")
    print("Before joining the team, the team elements are:", q.display())
    q.enqueue(5)
    q.enqueue(9)
    q.enqueue(14)
    print("After joining the team, the team elements are:", q.display())
    print("---------------------")
    print("The current team leader element is:", q.getTop())
    print("---------------------")
    print("Before leaving the team, the team elements are:", q.display())
    q.dequeue()
    print("After leaving the team, the elements in the team are:", q.display())
    print("---------------------")
    print("The current queue length is:", q.size())
    print("---------------------")
    print("The elements in the team before emptying are:", q.display())
    q.clear()
    print("After emptying, the elements in the team are:", q.display())
    print("---------------------")

Effect achieved:

3. Chain queue and basic operation

3.1 basic introduction of chain queue

Chain queue, referred to as "chain queue", is a queue storage structure implemented by linked list.

The implementation idea of chained queue is similar to that of sequential queue. You only need to create two pointers (named top and rear) to point to the queue head element and queue tail element of the queue in the linked list, as shown in Figure 1:

Figure 1 shows the initial state of the chain queue. At this time, no data elements are stored in the queue, so the top and rear pointers point to the head node at the same time.

When creating a chained queue, it is strongly recommended that beginners create a linked list with a header node, which will make it easier to implement the chained queue.

3.2 chained queue data entry

In the chain queue, when a new data element enters the queue, you only need to perform the following three steps:

(1) Wrap the data element with a node, for example, the new node name is elem;

(2) Establish a logical relationship with the node pointed to by the real pointer, that is, execute real - > next = elem;

(3) Finally, move the rear pointer to the new node, that is, rear=elem;

Thus, the new node joined the team successfully.

For example, on the basis of Figure 1, we queue {1,2,3} in turn. The process of queuing each data element is shown in Figure 2:

3.3 chained queue data outgoing

When there are data elements in the chain queue that need to be out of the queue, according to the principle of "first in, first out", only the nodes that store the data and the element nodes that entered the queue before it need to be out of the queue in turn according to the principle. Here, we first learn how to remove the team head element from the team.
　
　
The following three steps are required for the queue head element out of the queue in the chain queue:

(1) Directly find the queue head node through the top pointer, and create a new pointer p to the node about to leave the queue;

(2) Remove the p node (i.e. the team head node to be out of the team) from the linked list;

(3) Release node p and reclaim its memory space;
　
　
For example, on the basis of Fig. 2b), we dequeue elements 1 and 2, and the operation process is shown in Fig. 3:

Code implementation: chain representation and implementation of queue (difficulty: ★★)

Implementation of basic functions: (the same as the implementation of sequential queue, but in the form of linked list)

(1) Initialize queue

(2) Determine whether the queue is empty

(3) Returns the queue header element

(4) Returns the length of the queue

(5) Join: adds an element to the end of the queue

(6) Out of line: delete the team head element

(7) Traversal queue

(8) Empty queue

[note]: stack is first in first out, last in first out, queue is first in first out, last in last out!

The representation and implementation of chain queue are completed by Python programming!

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/7/28 8:10 
# @Author : vaxtiandao
# @File : ds_liqueue.py

'''
1. Queue features: first in first out, team tail in, team head out
2. Using single linked list: adding nodes at the tail(Join the team),Header delete node(Out of the team)operation
'''


# Define chained queue nodes
class Node:
    def __init__(self, value):
        self.data = value
        self.next = None


# Define queue function
class Queue:

    # Queue initialization
    def __init__(self):
        self.front = Node(None)
        self.rear = self.front

    # Element team
    def enQueue(self, element):
        n = Node(element)
        self.rear.next = n
        self.rear = n

    # Queue element dequeued
    def deQueue(self):
        if self.is_empty():
            print('Queue is empty')
            return
        temp = self.front.next
        self.front.next = self.front.next.next
        if self.rear == temp:
            self.rear = self.front
        del temp

    # Get team leader element
    def gettop(self):
        if self.is_empty():
            print('Queue is empty')
            return
        return self.front.next.data

    # Determine whether the queue is empty
    def is_empty(self):
        return self.rear == self.front

    # Traversal queue
    def display(self):
        if self.is_empty():
            print('Queue is empty')
            return
        cur = self.front.next
        while cur != None:
            print(cur.data, end=" ")
            cur = cur.next
        print()

    # Empty queue
    def clear(self):
        while self.front.next != None:
            temp = self.front.next
            self.front.next = temp.next
        self.rear = self.front

    # Return queue length
    def size(self):
        cur = self.front.next
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count


if __name__ == '__main__':
    queue = Queue()
    print("-----------------------------")
    print("Initialized chained queue:", queue)
    print("-----------------------------")
    print("Whether the current queue is empty:", queue.is_empty())
    print("-----------------------------")
    print("The queue elements before joining the queue are:", end="")
    queue.display()
    queue.enQueue(1)
    queue.enQueue(47)
    queue.enQueue("tr")
    print("After joining the queue, the queue elements are:", end="")
    queue.display()
    print("-----------------------------")
    print("The current queue length is:", queue.size())
    print("-----------------------------")
    print("The current queue header element is:", queue.gettop())
    print("-----------------------------")
    print("After leaving the queue, the queue elements are:", end="")
    queue.display()
    queue.deQueue()
    print("After leaving the queue, the queue elements are:", end="")
    queue.display()
    print("-----------------------------")
    print("Whether the current queue is empty:", queue.is_empty())
    print("-----------------------------")
    print("After emptying, the queue elements are:", end="")
    queue.display()
    queue.clear()
    print("After leaving the queue, the queue elements are:", end="")
    queue.display()
    print("-----------------------------")

Effect achieved:

4. Double ended queue

4.1 definitions

deque refers to a queue that allows both ends to enter and leave the queue. The logical structure of its elements is still linear. The two ends of the queue are called the front end and back end respectively. Both ends can enter and leave the queue. deque is the abbreviation of "double ended queue".

4.2 prototype of double ended queue

For the prototype of double ended queue, we can also use the example of queue. Here we mainly illustrate the examples of entering the queue from the head of the queue and leaving the queue from the tail of the queue:

(1) If a customer at the head of the queue enters the restaurant and finds that there is no empty table, the behavior of returning to the head of the queue again is equivalent to entering the queue from the head of the queue;

(2) If a customer at the end of the queue leaves the queue because the queue is too long, his behavior is equivalent to leaving the queue from the end of the queue.

4.3 ADT of double ended queue

In order to provide all operations supported by the above two terminal queue, its ADT must include at least the following four methods:

(1) D.add_first(e): insert element e in the team head;

(2) D.add_last(e): insert element e at the end of the queue;

(3) D.delete_first(): delete and return the queue header element, and throw an exception when the double ended queue is empty;

(4) D.delete_last(): delete and return the end of queue element, and throw an exception when the double ended queue is empty.

Code implementation: sequential representation and implementation of double ended queue (difficulty: ★★)

Realize basic functions: (including but not limited to, and can continue to expand according to their own capabilities)

(1) It is the same as sequential queue and chain queue (all 8 functions need to be implemented. The difference is that see the following)

(2) Team leader join: adds an element to the team leader

(3) Join at the end of the queue: add elements to the end of the queue

(4) Team leader out of team: delete the team leader element

(5) Out of queue at the end of the queue: delete the element at the end of the queue

[note]: a double ended queue refers to a linear data structure in which both ends can enter and exit elements. Although the entry and exit are arbitrary, the order of data in the double ended queue cannot be changed, which is the same as that of an ordinary queue;

**Representation and implementation of double ended queue, * * programmed in Python!

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/7/28 9:28 
# @Author : vaxtiandao
# @File : dou_queue.py

class Queue(object):
    def __init__(self):
        # Queue initialization 
        self.items = []

    # Determine whether the queue is empty
    def is_empty(self):
        # Judge whether it is empty
        return len(self.items) == 0

    # Change the original push and pop functions to the following four functions
    # It is used to realize head insertion, tail insertion, head deletion and tail deletion respectively
    # The team first joined the team
    def en_front(self, item):
        self.items.insert(0, item)

    # Join the team at the end of the team
    def en_back(self, item):
        self.items.append(item)

    # Team first team
    def de_front(self):
        print("Team leader{}Out of the team!".format(self.items[0]))
        self.items.pop(0)

    # Out of the team at the end of the team
    def de_back(self):
        print("Team tail{}Out of the team!".format(self.items[self.size()-1]))
        self.items.pop()

    # View queue length
    def size(self):
        # Return queue length
        return len(self.items)

    # Traversal queue
    def display(self):
        if self.is_empty():
            print("Queue is empty", end=' ')
        # ergodic
        for i in self.items:
            print(i, end=' ')
        print('')

    # Empty queue
    def clear(self):
        self.items = []

    # Get team leader element
    def getTop(self):
        return self.items[0]

    # Get tail element
    def getTail(self):
        return self.items[self.size()-1]


if __name__ == '__main__':
    # Initialize a queue object
    q = Queue()
    print("------------------------")
    print("Initialize Dual Ended queue:", q)
    print("------------------------")
    print("Whether the current queue is empty:", q.is_empty())
    print("------------------------")
    print("The internal elements before joining the team are:", end="")
    q.display()
    for i in range(5):
        if i % 2 == 0:
            q.en_front(i)
        else:
            q.en_back(i)
    print("After joining the team, the internal elements are:", end="")
    q.display()      # Print out 0-5
    print("------------------------")
    print("The current queue length is:", q.size())
    print("------------------------")
    print("The internal elements before leaving the team are:", end="")
    q.display()
    q.de_front()
    q.de_back()     # Conduct 2 out of team operations
    print("After leaving the team, the internal elements are:", end="")
    q.display()
    print("------------------------")
    print("The current team leader element is:", q.getTop())
    print("------------------------")
    print("The current tail element is:", q.getTail())
    print("------------------------")
    print("The current queue length is:", q.size())
    print("------------------------")
    print("The internal elements before emptying are:", end="")
    q.display()
    q.clear()
    print("After emptying, the internal elements are:", end="")
    q.display()
    print("------------------------")

Effect achieved:

5. Application of queue

Application 1: palindrome test

Palindrome word checking is a common task in data structure. This task can be completed intuitively and effectively by using double ended queue. Load the strings to be checked into the queue in order, pop them up at the beginning and end and compare them. In case of inconsistency, it is judged that they are not palindromes. When the queue is empty or there is only one element left, it can be judged as the number of palindromes.

Test case:
Case 1: abcgcba
Case 2: refer
Case 3: reference

Operation results:

code implementation

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/7/28 10:39 
# @Author : vaxtiandao
# @File : ds_palCheck.py

class Queue(object):
    def __init__(self):
        # Queue initialization
        self.items = []

    # Determine whether the queue is empty
    def is_empty(self):
        # Judge whether it is empty
        return len(self.items) == 0

    # Change the original push and pop functions to the following four functions
    # It is used to realize head insertion, tail insertion, head deletion and tail deletion respectively
    # The team first joined the team
    def en_front(self, item):
        self.items.insert(0, item)

    # Join the team at the end of the team
    def en_back(self, item):
        self.items.append(item)

    # Team first team
    def de_front(self):
        self.items.pop(0)
        return self.items[0]

    # Out of the team at the end of the team
    def de_back(self):
        self.items.pop()
        return self.items[self.size() - 1]

    # View queue length
    def size(self):
        # Return queue length
        return len(self.items)

    # Traversal queue
    def display(self):
        if self.is_empty():
            print("Queue is empty", end=' ')
        # ergodic
        for i in self.items:
            print(i, end=' ')
        print('')

    # Empty queue
    def clear(self):
        self.items = []

    # Get team leader element
    def getTop(self):
        return self.items[0]

    # Get tail element
    def getTail(self):
        return self.items[self.size() - 1]


def palChecker(aString):
    de = Queue()

    for i in aString:
        de.en_back(i)

    stillEqual = True

    while de.size() > 1 and stillEqual:
        first = de.de_front()
        last = de.de_back()
        if first != last:
            stillEqual = False

    return stillEqual


def check(stro):
    if palChecker(stro):
        print(stro, "It's a palindrome!")
    else:
        print(stro, "Not a palindrome!")


if __name__ == "__main__":
    s = ['abcgcba', 'refer', 'reference']
    for i in range(3):
        check(s[i])

Effect achieved: