Premium

Стек

Очередь на стеках

Реализовать очередь с помощью стеков

Легкий

Постановка задачи

Описание (LeetCode - 232. Implement Queue using Stacks)

Нужно реализовать очередь, используя только стандартные операции стека.

Класс MyQueue должен поддерживать операции:

  1. push(x) - добавить элемент x в конец очереди.
  2. pop() - удалить элемент из начала очереди и вернуть его.
  3. peek() - вернуть элемент из начала очереди, не удаляя его.
  4. empty() - проверить, пуста ли очередь.

Можно использовать только операции стека: добавить на вершину, удалить с вершины, посмотреть вершину и проверить, пуст ли стек.

Пример:

MyQueue queue = new MyQueue()
queue.push(1)
queue.push(2)
queue.peek()
queue.pop()
queue.empty()

Результат:

1
1
false

Ограничения:

  • 1 <= x <= 9
  • Будет выполнено не более 100 вызовов операций.
  • Операции pop и peek вызываются только для непустой очереди.

Решение

Очередь работает по правилу FIFO: первым добавили, первым достали. Стек работает наоборот: последним добавили, первым достали.

Нам нужны два стека. Один принимает новые элементы, второй отдает их в нужном порядке.

Идея решения:

  1. inStack - сюда кладем элементы при push.
  2. outStack - отсюда забираем элементы при pop и peek.

При push(x) просто делаем push в inStack.

При pop или peek, если outStack пуст, перекладываем все элементы из inStack в outStack. После такого переноса порядок разворачивается, и на вершине outStack оказывается начало очереди.

Основные шаги:

  1. push(x) добавляет элемент в inStack.
  2. Перед pop или peek, если outStack пуст, переносим все из inStack в outStack.
  3. pop() удаляет вершину outStack.
  4. peek() возвращает вершину outStack.
  5. empty() проверяет, пусты ли оба стека.

Каждый элемент перекладывается между стеками не больше одного раза. Поэтому дорогая операция переноса амортизируется, и в среднем операции работают быстро.

Рассмотрим пример:

  1. push(1): кладем элемент в inStack.
push(1)
  1. push(2): снова кладем в inStack. Начало очереди пока внизу.
push(2)
  1. peek(): outStack пуст, поэтому переносим элементы из in в out.
peek(): переносим in → out
  1. Теперь вершина outStack - это начало очереди. peek() возвращает 1.
peek()
  1. pop() удаляет вершину outStack.
pop()

Задачи про стек на очередях и очередь на стеках - базовые. Они проверяют, что кандидат умеет работать с этими структурами и понимает, как они устроены.

Кроме того, очередь на двух стеках легко расширить до очереди с текущим минимумом или максимумом: достаточно уметь реализовать Min стек или Max стек и хранить такой стек вместо обычного в inStack и outStack.

Оценка сложности

Временная сложность

push работает за O(1). pop и peek работают за амортизированное O(1): каждый элемент переносится из inStack в outStack только один раз. empty работает за O(1).

Пространственная сложность

Мы храним все элементы в двух стеках, поэтому пространственная сложность равна O(n).

Код решения

Приведем код решения.

type MyQueue struct {
    inStack  []int
    outStack []int
}
 
func Constructor() MyQueue {
    return MyQueue{
        inStack:  []int{},
        outStack: []int{},
    }
}
 
func (q *MyQueue) Push(x int) {
    q.inStack = append(q.inStack, x)
}
 
func (q *MyQueue) move() {
    for len(q.inStack) > 0 {
        n := len(q.inStack)
        top := q.inStack[n-1]
        q.inStack = q.inStack[:n-1]
        q.outStack = append(q.outStack, top)
    }
}
 
func (q *MyQueue) Pop() int {
    if len(q.outStack) == 0 {
        q.move()
    }
 
    n := len(q.outStack)
    top := q.outStack[n-1]
    q.outStack = q.outStack[:n-1]
    return top
}
 
func (q *MyQueue) Peek() int {
    if len(q.outStack) == 0 {
        q.move()
    }
 
    return q.outStack[len(q.outStack)-1]
}
 
func (q *MyQueue) Empty() bool {
    return len(q.inStack) == 0 && len(q.outStack) == 0
}

Итоги

Задача Implement Queue using Stacks показывает, как с помощью двух стеков получить поведение очереди.

  1. Суть алгоритма: push идет в inStack, а pop и peek работают через outStack. Когда outStack пуст, мы перекладываем элементы из in в out и разворачиваем порядок.
  2. Эффективность:
    • Временная сложность: push и empty работают за O(1), pop и peek - за амортизированное O(1).
    • Пространственная сложность: O(n), так как мы храним элементы в двух стеках.
  3. Граничные случаи:
    • Пустая очередь: empty() возвращает true.
    • outStack еще не пуст: новые элементы остаются в inStack, пока не закончатся элементы в outStack.
  4. Оптимальное решение: мы делаем push быстрым, а стоимость переноса распределяем между последующими pop и peek. Это удобный вариант, когда мы часто выполняем операции чтения и удаления из начала очереди.
Войдите чтобы отмечать прогресс