Implementation module "deque" in queue and Python

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.

queue_example.png

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.

queue_enqueue.png queue_dequeue.png

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.

Recommended Posts

Implementation module "deque" in queue and Python
Stack and Queue in Python
Sorting algorithm and implementation in Python
Module import and exception handling in python
RNN implementation in python
ValueObject implementation in Python
Queue processing in Python
SVM implementation in python
Explanation of edit distance and implementation in Python
Merge sort implementation / complexity analysis and experiment in Python
Logical symbols learned in marriage (and implementation examples in Python)
Python debug and test module
Neural network implementation in python
Unittest and CI in Python
Maxout description and implementation (Python)
Overview of generalized linear models and implementation in Python
Implementation of quicksort in Python
Sample of getting module name and class name in Python
Python module num2words Difference in behavior between English and Russian
MIDI packages in Python midi and pretty_midi
Difference between list () and [] in Python
Difference between == and is in python
[Python] logging in your own module
View photos in Python and html
HMM parameter estimation implementation in python
Mixed normal distribution implementation in python
Manipulate files and folders in Python
About dtypes in Python and Cython
Assignments and changes in Python objects
Implementation of life game in Python
Cooperation between python module and API
[Code] Module and Python version output
Check and move directories in Python
[Python Queue] Convenient use of Deque
Ciphertext in Python: IND-CCA2 and RSA-OAEP
Hashing data in R and Python
Python3 socket module and socket communication flow
Python unittest module execution in vs2017
Function synthesis and application in Python
I wrote the queue in Python
Export and output files in Python
Implementation of original sorting in Python
Reverse Hiragana and Katakana in Python2.7
Reading and writing text in Python
[GUI in Python] PyQt5-Menu and Toolbar-
Create and read messagepacks in Python
Master the weakref module in Python
Overlapping regular expressions in Python and Java
Differences in authenticity between Python and JavaScript
Notes using cChardet and python3-chardet in Python 3.3.1.
Differences between Ruby and Python in scope
AM modulation and demodulation in Python Part 2
difference between statements (statements) and expressions (expressions) in Python
Eigenvalues and eigenvectors: Linear algebra in Python <7>
Line graphs and scale lines in python
Comparison of Japanese conversion module in Python3
Implement FIR filters in Python and C
Differences in syntax between Python and Java
Check and receive Serial port in Python (Port check)
Search and play YouTube videos in Python
Difference between @classmethod and @staticmethod in Python