232. Implement Queue using Stacks

LeetCode easy оригинал: C# #csharp #design #easy #leetcode #queue #stack #two-pointers

LeetCode Static

Реализуйте очередь (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

C# решение

сопоставлено/оригинал

public class MyQueue {
    private Stack<int> s1 = new Stack<int>();
    private Stack<int> s2 = new Stack<int>();
    private int front;
    public void Push(int x) {
        if (s1.Count == 0)
            front = x;
        while (s1.Count != 0)
            s2.Push(s1.Pop());
        s2.Push(x);
        while (s2.Count != 0)
            s1.Push(s2.Pop());
    }
    public int Pop() {
        int res = s1.Pop();
        if (s1.Count != 0)
            front = s1.Peek();
        return res;
    }
    public bool Empty() {
        return s1.Count == 0;
    }
    public int Peek() {
        return front;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class MyQueue {
    private stack<int> s1 = new stack<int>();
    private stack<int> s2 = new stack<int>();
    private int front;
    public void Push(int x) {
        if (s1.size() == 0)
            front = x;
        while (s1.size() != 0)
            s2.push(s1.pop());
        s2.push(x);
        while (s2.size() != 0)
            s1.push(s2.pop());
    }
    public int Pop() {
        int res = s1.pop();
        if (s1.size() != 0)
            front = s1.Peek();
        return res;
    }
    public bool Empty() {
        return s1.size() == 0;
    }
    public int Peek() {
        return front;
    }
}

Java решение

сопоставлено/оригинал

class MyQueue {
    private Stack<Integer> s1 = new Stack<>();
    private Stack<Integer> s2 = new Stack<>();
    private int front;

    public void push(int x) {
        if (s1.empty())
            front = x;
        while (!s1.isEmpty())
            s2.push(s1.pop());
        s2.push(x);
        while (!s2.isEmpty())
            s1.push(s2.pop());
    }

    public int pop() {
        int res = s1.pop();
        if (!s1.empty())
            front = s1.peek();
        return res;
    }

    public boolean empty() {
        return s1.isEmpty();
    }

    public int peek() {
        return front;
    }
}

JavaScript решение

сопоставлено/оригинал

class MyQueue {
    constructor() {
        this.s1 = [];
        this.s2 = [];
        this.front = null;
    }

    push(x) {
        if (this.s1.length === 0) {
            this.front = x;
        }
        while (this.s1.length > 0) {
            this.s2.push(this.s1.pop());
        }
        this.s2.push(x);
        while (this.s2.length > 0) {
            this.s1.push(this.s2.pop());
        }
    }

    pop() {
        const res = this.s1.pop();
        if (this.s1.length > 0) {
            this.front = this.s1[this.s1.length - 1];
        }
        return res;
    }

    empty() {
        return this.s1.length === 0;
    }

    peek() {
        return this.front;
    }
}

Python решение

сопоставлено/оригинал

class MyQueue:

    def __init__(self):
        self.s1 = []
        self.s2 = []
        self.front = 0

    def push(self, x: int) -> None:
        if not self.s1:
            self.front = x
        while self.s1:
            self.s2.append(self.s1.pop())
        self.s2.append(x)
        while self.s2:
            self.s1.append(self.s2.pop())

    def pop(self) -> int:
        res = self.s1.pop()
        if self.s1:
            self.front = self.s1[-1]
        return res

    def empty(self) -> bool:
        return not self.s1

    def peek(self) -> int:
        return self.front

Go решение

сопоставлено/оригинал

type MyQueue struct {
    s1, s2 []int
    front  int
}

func Constructor() MyQueue {
    return MyQueue{}
}

func (this *MyQueue) Push(x int) {
    if len(this.s1) == 0 {
        this.front = x
    }
    for len(this.s1) > 0 {
        this.s2 = append(this.s2, this.s1[len(this.s1)-1])
        this.s1 = this.s1[:len(this.s1)-1]
    }
    this.s2 = append(this.s2, x)
    for len(this.s2) > 0 {
        this.s1 = append(this.s1, this.s2[len(this.s2)-1])
        this.s2 = this.s2[:len(this.s2)-1]
    }
}

func (this *MyQueue) Pop() int {
    res := this.s1[len(this.s1)-1]
    this.s1 = this.s1[:len(this.s1)-1]
    if len(this.s1) > 0 {
        this.front = this.s1[len(this.s1)-1]
    }
    return res
}

func (this *MyQueue) Empty() bool {
    return len(this.s1) == 0
}

func (this *MyQueue) Peek() int {
    return this.front
}

Algorithm

Добавление элемента: Для метода push(int x) переместите все элементы из стека s1 в стек s2. Добавьте элемент x в стек s2. Затем переместите все элементы обратно из стека s2 в стек s1. Если стек s1 пуст, обновите переменную front значением x.

Удаление и проверка первого элемента: Для метода pop() удалите элемент из начала очереди, извлекая верхний элемент из стека s1. Обновите переменную front на новый верхний элемент стека s1, если он не пуст. Для метода peek() верните значение переменной front, так как она всегда хранит первый элемент очереди.

Проверка на пустоту: Для метода empty() верните результат проверки, является ли стек s1 пустым.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.