Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack ( , , , and ). push top pop empty Implement the class: MyStack Pushes element x to the top of the stack. void push(int x) Removes the element on the top of the stack and returns it. int pop() Returns the element on the top of the stack. int top() Returns if the stack is empty, otherwise. boolean empty() true false Notes: You must use standard operations of a queue, which means that only , , and operations are valid. only push to back peek/pop from front size is empty Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations. Example 1: 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 Constraints: 1 <= x <= 9 At most calls will be made to , , , and . 100 push pop top empty All the calls to and are valid. pop top Can you implement the stack using only one queue? Follow-up: Solution Here will be two amazing variants. And you can discuss with the interviewer which variant is the best and discuss all pros and cons. In the first variant we are going to use Two Queues, push - (1), pop O(n) O . Ok, Lets start. Our class looks like: class MyStack {

        private Queue<Integer> current;
        private Queue<Integer> tmp;

        public MyStack() {
            current = new ArrayDeque<>();
            tmp = new ArrayDeque<>();
        }
} Then let’s implement operation. For it, we just need to push the element into the queue push public void push(int x) {
    current.add(x);
} operation can be tricky. Firstly we have to check the current queue. If it is empty, we can throw err or return for example.  Then we have to to the tmp queue. After it we and finally swap the queues. Pop -1 move all elements except one remember the last element in a current queue public int pop() {
    if (current.isEmpty()){
        return -1;
    }
    int size = current.size();
    for (int i = 0; i < size - 1; i ++){
        tmp.add(current.poll());
    }
    int ret = current.poll();
    current = tmp;
    return ret;
} Let’s draw it. For example: 1) we have in currentQ elements [3, 2, 1] -→ move to temp 2) currentQ [3, 2], tmpQ = [1] 3)  currentQ [3], tmpQ = [2, 1] 4) remember 3 5) currentQ = tmpQ = [2, 1] 6) return 3 Kinda the same algorithm we use for operation: top public int top() {
    if (current.isEmpty()){
        return -1;
    }
    int size = current.size();
    for (int i = 0; i < size - 1; i ++){
        tmp.add(current.poll());
    }
    int ret = current.peek();
    tmp.add(current.poll());
    current = tmp;
    return ret;
} And a simple method to check if our stack is empty: public boolean empty() {
    return current.isEmpty();
} Looks like wisdom to me. In the second solution, we use only one Queue, but the push operation will take - O(n) time and pop O(1). class MyStack2 {

    private Queue<Integer> current;

    public MyStack2() {
        current = new ArrayDeque<>();
    }
} In this approach, the main trick will be in the method: push public void push(int x) {
    current.add(x);
    int size = current.size();

    for (int i = 0; i < size-1; i ++){
        current.add(current.poll());
    }
} We push a new element to the end of the queue. Then we move all elements step by step to the end. For example: 1) push(1) → current add 1 = [1] 2) push(2) → current add [2, 1] → move [1, 2] 3)  push(3) → current add [3, 1, 2] → move [2, 3, 1] → move [1, 2, 3] And… and that is it =) All other operations use the current queue public int pop() {
    return current.poll();
}

public int top() {
   return current.peek();
}

public boolean empty() {
    return current.isEmpty();
} Oh, do you like it? leave add your comments below. link: https://leetcode.com/problems/implement-stack-using-queues/

The writer is smart, but don't just like, take their word for it. #DoYourOwnResearch

Implement Queue using Stacks

Implementing Stack Using Queue

2021 - HackerNoon Contributor of the Year - INNOVATION

2021 - HackerNoon Contributor of the Year - COMPUTER-SCIENCE

Implement Stack using Queues

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

2022 Noonies Nominee Sergei on Programming, Technology, and More

10 Ways To Effectively Sell Yourself During A Job Interview

10 Tips for Using Diagrams to Ace The System Design Interview

10 Technical Interview Tips

10 Questions for Aswin Ganesh, Noonie Nominee for Functional Programming

10 Proven Techniques to Improve Candidate Experience

2022 Noonies Nominee Sergei on Programming, Technology, and More

10 Ways To Effectively Sell Yourself During A Job Interview

10 Tips for Using Diagrams to Ace The System Design Interview

10 Technical Interview Tips

10 Questions for Aswin Ganesh, Noonie Nominee for Functional Programming

10 Proven Techniques to Improve Candidate Experience

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps