Очередь (Queue) - структура данных FIFO

Очередь представляет собой абстрактный тип данных и линейную структуру, работающую по принципу "первым вошел, первым вышел" (First In - First Out, FIFO). Аналогия - очередь в магазине: новые покупатели встают в конец, а обслуживаются первым пришедшим.

Сложность выполнения: Аналогично связным спискам и стекам. 

Пример кода:

Создаем очередь при помощи связных списков.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedListQueue:
    def __init__(self):
        self.front = None  # начало очереди
        self.rear = None   # конец очереди
        self._size = 0
    
    def enqueue(self, item):
        """Добавление в конец очереди"""
        new_node = Node(item)
        if self.rear is None:
            self.front = self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node
        self._size += 1
    
    def dequeue(self):
        """Удаление из начала очереди"""
        if self.is_empty():
            raise IndexError('Удаление из пустой очереди')
        temp = self.front
        self.front = temp.next
        if self.front is None:
            self.rear = None
        self._size -= 1
        return temp.data
    
    def peek(self):
        """Просмотр первого элемента"""
        if self.is_empty():
            raise IndexError('Очередь пуста')
        return self.front.data
    
    def is_empty(self):
        """Проверка на пустоту"""
        return self.front is None
    
    def size(self):
        """Размер очереди"""
        return self._size

Создаем очередь при помощи двух стеков 

class TwoStacksQueue:
    def __init__(self):
        self.in_stack = []  # для добавления элементов
        self.out_stack = [] # для удаления элементов
    
    def enqueue(self, item):
        """Добавление элемента"""
        self.in_stack.append(item)
    
    def dequeue(self):
        """Удаление элемента"""
        if self.is_empty():
            raise IndexError('Удаление из пустой очереди')
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack.pop()
    
    def peek(self):
        """Просмотр первого элемента"""
        if self.is_empty():
            raise IndexError('Очередь пуста')
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack[-1]
    
    def is_empty(self):
        """Проверка на пустоту"""
        return not (self.in_stack or self.out_stack)
    
    def size(self):
        """Размер очереди"""
        return len(self.in_stack) + len(self.out_stack)