225. Implement Stack using Queues

leetcode easy

#csharp#design#easy#leetcode#queue#stack

Task

Реализуйте стек (последним пришел - первым вышел, LIFO) с использованием только двух очередей. Реализованный стек должен поддерживать все функции обычного стека (push, top, pop и empty).

Реализуйте класс MyStack:

void push(int x): Добавляет элемент x на вершину стека.

int pop(): Удаляет элемент с вершины стека и возвращает его.

int top(): Возвращает элемент на вершине стека.

boolean empty(): Возвращает true, если стек пуст, иначе false.

Примечания:

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

Пример:

Input

["MyStack", "push", "push", "top", "pop", "empty"]

[[], [1], [2], [], [], []]

Output

[null, null, null, 2, 2, false]

Explanation

MyStack myStack = new MyStack();

myStack.push(1);

myStack.push(2);

myStack.top(); // return 2

myStack.pop(); // return 2

myStack.empty(); // return False

C# solution

matched/original

using System.Collections.Generic;
public class MyStack {
    private Queue<int> q1 = new Queue<int>();
    private Queue<int> q2 = new Queue<int>();
    private int topElement;
    public void Push(int x) {
        q2.Enqueue(x);
        topElement = x;
        while (q1.Count > 0) {
            q2.Enqueue(q1.Dequeue());
        }
        var temp = q1;
        q1 = q2;
        q2 = temp;
    }
    public void Pop() {
        q1.Dequeue();
        if (q1.Count > 0) {
            topElement = q1.Peek();
        }
    }
    public bool Empty() {
        return q1.Count == 0;
    }
    public int Top() {
        return topElement;
    }
}

C++ solution

auto-draft, review before submit

#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 MyStack {
    private queue<int> q1 = new queue<int>();
    private queue<int> q2 = new queue<int>();
    private int topElement;
    public void Push(int x) {
        q2.Enqueue(x);
        topElement = x;
        while (q1.size() > 0) {
            q2.Enqueue(q1.Dequeue());
        }
        var temp = q1;
        q1 = q2;
        q2 = temp;
    }
    public void Pop() {
        q1.Dequeue();
        if (q1.size() > 0) {
            topElement = q1.Peek();
        }
    }
    public bool Empty() {
        return q1.size() == 0;
    }
    public int Top() {
        return topElement;
    }
}

Java solution

matched/original

import java.util.LinkedList;
import java.util.Queue;

class MyStack {
    private Queue<Integer> q1 = new LinkedList<>();
    private Queue<Integer> q2 = new LinkedList<>();
    private int top;

    public void push(int x) {
        q2.add(x);
        top = x;
        while (!q1.isEmpty()) {
            q2.add(q1.remove());
        }
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }

    public void pop() {
        q1.remove();
        if (!q1.isEmpty()) {
            top = q1.peek();
        }
    }

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

    public int top() {
        return top;
    }
}

JavaScript solution

matched/original

class MyStack {
    constructor() {
        this.q1 = [];
        this.q2 = [];
        this.topElement = null;
    }

    push(x) {
        this.q2.push(x);
        this.topElement = x;
        while (this.q1.length) {
            this.q2.push(this.q1.shift());
        }
        [this.q1, this.q2] = [this.q2, this.q1];
    }

    pop() {
        const result = this.q1.shift();
        if (this.q1.length) {
            this.topElement = this.q1[0];
        }
        return result;
    }

    top() {
        return this.topElement;
    }

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

Python solution

matched/original

from collections import deque

class MyStack:

    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()
        self.top_element = None

    def push(self, x: int) -> None:
        self.q2.append(x)
        self.top_element = x
        while self.q1:
            self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1

    def pop(self) -> int:
        result = self.q1.popleft()
        if self.q1:
            self.top_element = self.q1[0]
        return result

    def top(self) -> int:
        return self.top_element

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

Go solution

matched/original

package main

import "fmt"

type MyStack struct {
    q1 []int
    q2 []int
    topElement int
}

func Constructor() MyStack {
    return MyStack{
        q1: []int{},
        q2: []int{},
    }
}

func (this *MyStack) Push(x int)  {
    this.q2 = append(this.q2, x)
    this.topElement = x
    for len(this.q1) > 0 {
        this.q2 = append(this.q2, this.q1[0])
        this.q1 = this.q1[1:]
    }
    this.q1, this.q2 = this.q2, this.q1
}

func (this *MyStack) Pop() int {
    res := this.q1[0]
    this.q1 = this.q1[1:]
    if len(this.q1) > 0 {
        this.topElement = this.q1[0]
    }
    return res
}

func (this *MyStack) Top() int {
    return this.topElement
}

func (this *MyStack) Empty() bool {
    return len(this.q1) == 0
}

Explanation

Algorithm

Реализация методов push и pop:

Метод push добавляет элемент x в очередь q2, затем перемещает все элементы из q1 в q2 и меняет местами q1 и q2.

Метод pop удаляет элемент из q1 и обновляет значение top.

Реализация методов top и empty:

Метод top возвращает верхний элемент стека.

Метод empty проверяет, пуста ли очередь q1, и возвращает соответствующее значение.

Поддержка стандартных операций очереди:

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

😎