### 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）

#### 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.

#### 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
```