编程知识 cdmana.com

Data structure must be queue and double ended queue (Python)

queue

1. What is the queue

​ The idea of queue is closer to our life , When we line up to check out at the supermarket , In fact, it is the implementation of a queue , That is, the people who line up first check out first , The idea of people in line after checking out .

​ Like the stack , A queue is also an ordered collection , The add operation occurs at the end , The removal operation occurs in the head , The new element will enter the queue from the tail , Then move straight forward to the head , Until it becomes the next element to be removed .

​ The nature of the queue stipulates that the newly added element must wait at the end of the queue , The longest element in the queue is at the head , This principle is called FIFO(first-in first-out)

 Insert picture description here

2. Implementation of queues

​ The implementation of queue is very simple , We just need to ensure that the elements “ From where , I don't know where it comes from ” That's all right. , Using a list to implement the queue, we can use... From the end insert() Function insert element , Reuse pop() Push out the elements of the head . The specific implementation method is as follows :

class Queue:
    def __init__(self):
        self.items = []
    
    #  Determine whether the queue is empty 
    def isEmpty(self):
        return self.items == []

    #  Queue entry 
    def enqueue(self, item):
        self.items.insert(0, item)

    #  Outgoing queue 
    def dequeue(self):
        return self.items.pop()

    #  Length of queue 
    def size(self):
        return len(self.items)

​ The test results are as follows :

#  Test queue 
q = Queue()
q.isEmpty()

#  Incoming elements 
q.enqueue('I')
q.enqueue('like')
q.enqueue('python')
q.size()
q.dequeue()

#  Output 
'I'

deque

1. The concept of double ended queue

​ The double ended queue is more free than the previous data structure , There is no limit on which end of the queue to add and remove elements , This means that you can add and remove elements from either end .

​ The nature of double ended queue also determines that it has two different principles :LIFO and FIFO.

 Insert picture description here

2. Implementation of double ended queue

​ When implementing double ended queue, we can combine the previous methods used on stack and queue LIFO and FIFO Two thoughts . The specific implementation method is as follows :

class Deque:
    def __init__(self):
        self.items = []

    #  Determine whether it is null 
    def isEmpty(self):
        return self.items == []

    #  Insert data from the front end 
    def addFront(self, item):
        self.items.append(item)

    #  Insert data from the tail 
    def addRear(self, item):
        self.items.insert(0, item)

    #  Delete data from the front end 
    def removeFront(self):
        return self.item.pop()

    #  Delete data from the tail 
    def removeRear(self):
        return self.item.pop(0)

    #  Length of queue 
    def size(self):
        return len(self.items)

​ The test results are as follows :

#  test 
d = Deque()
d.isEmpty()

#  Insert elements 
d.addFront('I')
d.addFront('like')
d.addRear('Python')

#  Test length 
d.size()

#  Output 
3

版权声明
本文为[The second brother is not like a programmer]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/10/20211002150018487K.html

Scroll to Top