Premium

Стек

Стек на очередях

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

Легкий

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

Описание (LeetCode - 225. Implement Stack using Queues)

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

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

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

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

Пример:

MyStack stack = new MyStack()
stack.push(1)
stack.push(2)
stack.top()
stack.pop()
stack.empty()

Результат:

2
2
false

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

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

Решение

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

Нам нужно сделать так, чтобы последний добавленный элемент всегда оказывался в начале очереди. Тогда pop и top будут работать так же, как у стека.

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

Будем хранить все элементы в одной очереди. При push(x) добавим новый элемент в конец очереди, а затем повернем очередь: все элементы, которые были до x, перенесем из начала в конец.

После такого поворота новый элемент окажется первым.

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

  1. push(1): очередь пуста, добавляем элемент.
push(1)
  1. push(2): сначала добавляем 2 в конец.
push(2): добавляем в конец
  1. Затем поворачиваем очередь: переносим старые элементы из начала в конец. Теперь вершина стека снова в начале.
push(2): поворачиваем очередь
  1. top() возвращает первый элемент очереди.
top()
  1. pop() удаляет первый элемент.
pop()

Основные шаги для push:

  1. Запоминаем текущий размер очереди.
  2. Добавляем x в конец.
  3. size раз удаляем элемент из начала и добавляем его в конец.

Остальные операции становятся простыми:

  1. pop() удаляет первый элемент очереди.
  2. top() возвращает первый элемент очереди.
  3. empty() проверяет, пуста ли очередь.

Мы платим медленным push за быстрый pop. После каждого добавления очередь уже лежит в порядке стека: вершина находится в начале.

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

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

push работает за O(n), потому что мы поворачиваем очередь. Операции pop, top и empty работают за O(1).

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

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

Код решения

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

type MyStack struct {
    queue []int
}
 
func Constructor() MyStack {
    return MyStack{
        queue: []int{},
    }
}
 
func (s *MyStack) Push(x int) {
    size := len(s.queue)
    s.queue = append(s.queue, x)
 
    for i := 0; i < size; i++ {
        front := s.queue[0]
        s.queue = s.queue[1:]
        s.queue = append(s.queue, front)
    }
}
 
func (s *MyStack) Pop() int {
    top := s.queue[0]
    s.queue = s.queue[1:]
    return top
}
 
func (s *MyStack) Top() int {
    return s.queue[0]
}
 
func (s *MyStack) Empty() bool {
    return len(s.queue) == 0
}

Итоги

Задача Implement Stack using Queues показывает, как одну структуру данных можно заставить вести себя как другую.

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