author: Sergei Golitsyn link: https://leetcode.com/problems/implement-queue-using-stacks/ Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue ( , , , and ). push peek pop empty Implement the class: MyQueue Pushes element x to the back of the queue. void push(int x) Removes the element from the front of the queue and returns it. int pop() Returns the element at the front of the queue. int peek() Returns if the queue is empty, otherwise. boolean empty() true false Notes: You must use standard operations of a stack, which means only , , , and operations are valid. only push to top peek/pop from top size is empty Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations. Example 1: 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 Solution In this problem, I will show you only one solution. The main trick will be in and operations. But hold on. Let’s do it step by step. First of all, we have to prepare a class and needed data structures: pop peak static class MyQueue {

    Stack<Integer> current;
    Stack<Integer> tmp;

    public MyQueue() {
        current = new Stack<>();
        tmp = new Stack<>();
    }
static class MyQueue {

        Stack<Integer> current;
        Stack<Integer> tmp;

        public MyQueue() {
            current = new Stack<>();
            tmp = new Stack<>();
        }
} And now, let’s add a method: push public void push(int x) {
    current.push(x);
} Simple and clear, just add an element into the stack. And what about For pop operation, we pop? have to move all elements from the current stack to the tmp stack And before it, we should check out stack. If stack contains an elements we can simply return an element from this stack. tmp tmp public int pop() {
    if (!tmp.isEmpty()) {
        return tmp.pop();
    }
    while (!current.isEmpty()) {
        tmp.push(current.pop());
    }
    return tmp.pop();
} Let’s try to draw a picture. push 1. → 1 push 2. → 2, 1 push 3. → 3, 2, 1 pop. → move to tmp -→ cur: 2, 1, tmp: 3 cur: 1,     tmp: 2, 3

                                      cur:         tmp: 1, 2, 3 do you see it? after moving elements, all elements in the stack are in the correct order. tmp Ahh, I was a bit shocked, but it is true. If you move elements from one stack into another, you will have elements in insert order, like in a queue. Now, let’s implement function: peek public int peek() {
    if (!tmp.isEmpty()) {
        return tmp.peek();
    }
    while (!current.isEmpty()) {
        tmp.push(current.pop());
    }
    return tmp.peek();
} Same logic as in the method. pop And finally isEmpty method. Don’t forget that we have to check two queues. public boolean empty() {
    if (!tmp.isEmpty()) {
        return tmp.isEmpty();
    }
    return current.isEmpty();
} Complexity Analysis Time complexity: Amortized O(1) (1), Worst-case O(n) ( ). In the worst case scenario when stack is empty, the algorithm pops n elements from stack s1 and pushes n elements to , where n is the queue size. This gives 2n2 operations, which is O(n) ( ). But when stack is not empty the algorithm has O(1) (1) time complexity. So what does it mean by Amortized O(1) (1)? Please see the next section on Amortized Analysis for more information. O O n s2 n n s2 n n O n s2 O O Space complexity : O(1) (1). O

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

Stacks

House Robber

Implement Stack using Queues

2021 - HackerNoon Contributor of the Year - INNOVATION

2021 - HackerNoon Contributor of the Year - COMPUTER-SCIENCE

2021 - Rick Sanchez of the Year

Nominated for 2022 - HackerNoon Contributor of the Year - Design

Nominated for 2022 - HackerNoon Contributor of the Year - Software Architecture

Too Long; Didn't Read

Implement Queue using Stacks

Implement Queue using Stacks

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 JavaScript Interview Questions and Answers to Help you Land Your Next Role

10 Essential Javascript Questions

23 Common Data Science Interview Questions for Beginners

2022 Noonies Programming Nominee Roy Derks on GraphQL, React, and More

2022 Noonies Nominee Sergei on Programming, Technology, and More

10 Ways To Effectively Sell Yourself During A Job Interview

10 JavaScript Interview Questions and Answers to Help you Land Your Next Role

10 Essential Javascript Questions

23 Common Data Science Interview Questions for Beginners

2022 Noonies Programming Nominee Roy Derks on GraphQL, React, and More

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps