Сложность: easy
Реализуйте очередь (FIFO) с использованием только двух стеков. Реализованная очередь должна поддерживать все функции обычной очереди (push, peek, pop и empty).
Реализуйте класс MyQueue:
void push(int x) добавляет элемент x в конец очереди.
int pop() удаляет элемент из начала очереди и возвращает его.
int peek() возвращает элемент из начала очереди.
boolean empty() возвращает true, если очередь пуста, и false в противном случае.
Пример:
Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]
Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
👨💻 Алгоритм:
1⃣Добавление элемента: Для метода push(int x) переместите все элементы из стека s1 в стек s2. Добавьте элемент x в стек s2. Затем переместите все элементы обратно из стека s2 в стек s1. Если стек s1 пуст, обновите переменную front значением x.
2⃣Удаление и проверка первого элемента: Для метода pop() удалите элемент из начала очереди, извлекая верхний элемент из стека s1. Обновите переменную front на новый верхний элемент стека s1, если он не пуст. Для метода peek() верните значение переменной front, так как она всегда хранит первый элемент очереди.
3⃣Проверка на пустоту: Для метода empty() верните результат проверки, является ли стек s1 пустым.
😎 Решение:
class MyQueue {
private var s1: [Int] = []
private var s2: [Int] = []
private var front: Int = 0
func push(_ x: Int) {
if s1.isEmpty {
front = x
}
while !s1.isEmpty {
s2.append(s1.removeLast())
}
s2.append(x)
while !s2.isEmpty {
s1.append(s2.removeLast())
}
}
func pop() -> Int {
let res = s1.removeLast()
if !s1.isEmpty {
front = s1.last!
}
return res
}
func empty() -> Bool {
return s1.isEmpty
}
func peek() -> Int {
return front
}
}Ставь 👍 и забирай 📚 Базу знаний