It seems better to use a data structure called a queue when implementing breadth-first search, so This time I looked into the queue.

What is a queue?

Queues, or queues, are one of the basic data structures of a computer. Data is held in a first-in, first-out list structure. When retrieving data from the queue, the data that was put in first is fetched in order. Putting data in a queue is called enqueue, and taking it out is called dequeue. (From Wikipedia)

The figure shows a data structure with the following structure.

The image is like a cylinder. Data can be put into the queue from behind the queue (enqueue), Data can be retrieved from the beginning of the queue (dequeue). Due to the structure, the data that can be retrieved are in the order in which they are queued. Enqueue and dequeue are shown in the figure below.

How to implement in Python

To implement a queue in Python, use the ** deque ** type of the ** collections ** module. Although it is this deque type, it has a data structure that has a stack function in addition to a queue, and can be used as a stack depending on how it is used. This time, the explanation is based on the assumption that it will be used as a queue.

Creating a queue

Import the deque to create a queue object.

>>> from collections import deque
>>> 
>>> a=deque()
>>>

Adding elements to the queue

To add an element to the deque, use the ** append ** () function. The append function appends the element from the right side of the queue. Although it is not the original usage of the queue, use the ** appendleft ** () function to add from the left.

>>> a
deque([])
>>> 
>>> a.append(1)
>>> a
deque([1])
>>> 
>>> a.append(2)
>>> a
deque([1, 2])
>>> 
>>> a.appendleft(3)
>>> a
deque([3, 1, 2])
>>>

Add another list element to the queue at once

If you want to add elements from another list to the queue at once, use the ** extend ** function. If you want to add from the left side of the queue, use the ** extendleft ** function. (The elements on the left of the list are added to the queue in order.)

>>> a
deque([1])
>>> 
>>> b=[2,3,4]
>>> 
>>> a.extend(b)
>>> 
>>> a
deque([1, 2, 3, 4])
>>> 
>>> a.extendleft(b)
>>> 
>>> a
deque([4, 3, 2, 1, 2, 3, 4])
>>>

Remove / delete elements from the queue

Use the ** pop ** function to retrieve an element from a deque. The pop function removes an element from the right side of the deque and returns that element. If you want to retrieve the element from the left side of the deque, use the ** popleft ** function.

Also, if you want to remove a specific element from the deque, use the ** remove ** function. Use deque.remove (x) to remove the first x that appears in the deque.

>>> a
deque([3, 1, 2])
>>> 
>>> a.pop()
2
>>> a
deque([3, 1])
>>> 
>>> a.popleft()
3
>>> a
deque([1])
>>> 
>>> 
>>> a.append(2)
>>> a.append(2)
>>> a.append(3)
>>> 
>>> 
>>> a
deque([1, 2, 2, 3])
>>> 
>>> a.remove(2)
>>> a
deque([1, 2, 3])
>>>

Remove all elements from the queue

Use the ** clear ** function to remove all elements from the queue.

>>> a
deque([1, 2, 3])
>>> 
>>> a.clear()
>>> 
>>> a
deque([])
>>>

Reverse the order of the elements in the queue

Use the ** reverse ** function to reverse the order of the elements in the queue.

>>> a
deque([1, 2, 3, 4])
>>> 
>>> a.reverse()
>>> 
>>> a
deque([4, 3, 2, 1])
>>>

I want to utilize it in the future.

Implementation module "deque" in queue and Python