#data-structures #queue #stack #time-complexity
Вопрос:
Мне интересно, можно ли реализовать очередь с использованием двух стеков, чтобы каждая операция очереди занимала амортизированное постоянное время.
Ответ №1:
class QQ: def __init__(self): self.s = [] self.ss = [] def enque(self, val): self.s.append(val) def deque(self): if not self.s and not self.ss: return None if not self.ss: while self.s: self.ss.append(self.s.pop()) return self.ss.pop() Второй стек ss содержит содержимое первого стека s в обратном порядке, когда мы вставляем элементы s в ss . Обратный стек — это просто очередь. Всякий ss раз, когда пусто, мы загружаем все элементы в s into ss . Если он не пуст, мы просто deque один элемент из него.
Временная сложность амортизируется как постоянная, так как мы делаем только один ход в enque ing и в долгосрочной перспективе только 2 хода для deque ing.
Комментарии:
1. спасибо, но здесь сложность deque() не O(1)
2. Если вы измените цикл while на 0:self.s.длина, то, поскольку мы знаем количество повторов, сложность будет O(1) умножена на константу, равную O(1). Но в любом случае, я должен поблагодарить тебя за помощь.
3.
dequeимеет амортизированнуюO(1)временную сложность. Возможно, вы не знакомы с python.while self.s, гдеsнаходится список, делает то, что вы описываете0:self.s.length. Это верно, покаself.sудерживает каких-либо участников. Когда он пуст, он ломается.
Ответ №2:
Мы используем 2 стопки с тегами «спереди» и «сзади».
В переднем стеке мы должны использовать методы size и clear, которые возвращают указатель стека, а clear устанавливает указатель на 0.
Для enqueue() этого мы должны поместить новый элемент в передний стек. Так что временная сложность будет O(1) .
Ибо dequeue() , если стек пуст, мы должны наполнить его элементы в стек, каждый элемент, который находится внутри стойки стека мы должны вызвать pop() функцию, а затем использовать push() функцию, чтобы вставить его в задний стек, поскольку мы знаем, что размер передних стек (и постоянно) и поп и функцией push успел-сложность O(1) , вся сложность извлечения будет O(1) .
Для size() этого он вернет сумму переднего и заднего стеков size() . Ибо isEmpty() он должен вернуться, если размер равен нулю или нет.