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
Please bring the original link to reprint ,thank
Similar articles