Algorithm

Problem Name: 232. Implement Queue using Stacks

Problem 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 (push, peek, pop, and empty).

Implement the MyQueue class:

  • void push(int x) Pushes element x to the back of the queue.
  • int pop() Removes the element from the front of the queue and returns it.
  • int peek() Returns the element at the front of the queue.
  • boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

  • You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
  • 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

 

Constraints:

  • 1 <= x <= 9
  • At most 100 calls will be made to push, pop, peek, and empty.
  • All the calls to pop and peek are valid.

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct StackNode {
    int val;
    struct StackNode *next;
};

struct Stack {
    struct StackNode *top;
};

void push(struct Stack *stack, int new_val) {
    if (stack == NULL) return;

    struct StackNode *new_node
        = (struct StackNode *)malloc(sizeof(struct StackNode));

    new_node->val = new_val;
    new_node->next = stack->top;

    stack->top = new_node;
}

int pop(struct Stack *stack) {
    if (stack == NULL || stack->top == NULL) return 0;

    struct StackNode *t = stack->top;
    int ans = t->val;

    stack->top = stack->top->next;

    free(t);

    return ans;
}

bool isEmpty(struct Stack *stack) {
    if (stack == NULL) return true;

    return (stack->top == NULL) ? true : false;
}

typedef struct {
    struct Stack in;
    struct Stack out;
} Queue;

void queueCreate(Queue *queue, int maxSize) {
    if (queue == NULL) return;

    queue->in.top = queue->out.top = NULL;
}

void queuePush(Queue *queue, int element) {
    if (queue == NULL) return;

    while (!isEmpty(&queue->out)) {
        int top = pop(&queue->out);
        push(&queue->in, top);
    }

    push(&queue->in, element);
}

void queuePop(Queue *queue) {
    if (queue == NULL) return;

    if (isEmpty(&queue->out)) {
        while (!isEmpty(&queue->in)) {
            int top = pop(&queue->in);
            push(&queue->out, top);
        }
    }

    pop(&queue->out);
}

int queuePeek(Queue *queue) {
    if (isEmpty(&queue->out)) {
        while (!isEmpty(&queue->in)) {
            int top = pop(&queue->in);
            push(&queue->out, top);
        }
    }

    if (!isEmpty(&queue->out) && queue->out.top) {
        return queue->out.top->val;
    }
    else {
        return 0;
    }
}
bool queueEmpty(Queue *queue) {
    if (isEmpty(&queue->in) && isEmpty(&queue->out)) {
        return true;
    }
    else {
        return false;
    }
}

void queueDestroy(Queue *queue) {
    while (!isEmpty(&queue->in)) {
        pop(&queue->in);
    }

    while (!isEmpty(&queue->out)) {
        pop(&queue->out);
    }
}

int main() {
    int maxSize = 5;
    Queue q;

    printf("Create a queue.\n"); queueCreate(&q, maxSize);

    printf("Push 1\n"); queuePush(&q, 1);
    printf("Push 2\n"); queuePush(&q, 2);
    printf("Push 3\n"); queuePush(&q, 3);
    printf("Push 4\n"); queuePush(&q, 4);

    printf("Peek of queue: %d\n", queuePeek(&q));

    printf("Pop\n"); queuePop(&q);
    printf("Peek of queue: %d\n", queuePeek(&q));
    printf("Push 5\n"); queuePush(&q, 5);
    printf("Peek of queue: %d\n", queuePeek(&q));

    printf("Pop\n"); queuePop(&q);
    printf("Peek of queue: %d\n", queuePeek(&q));
    printf("Pop\n"); queuePop(&q);
    printf("Peek of queue: %d\n", queuePeek(&q));
    printf("Pop\n"); queuePop(&q);
    printf("Peek of queue: %d\n", queuePeek(&q));

    printf("Destroy\n"); queueDestroy(&q);

    return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []]

Output

x
–
+
cmd
[null, null, null, 1, 1, false]

#2 Code Example with Java Programming

Code - Java Programming


class MyQueue {
    
    private final Stack stackOne;
    private final Stack < Integer> stackTwo;

    public MyQueue() {
        this.stackOne = new Stack<>();
        this.stackTwo = new Stack < >();
    }
    
    public void push(int x) {
        this.stackOne.push(x);
    }
    
    public int pop() {
        exchangeElements(stackOne, stackTwo);
        int popped = stackTwo.pop();
        exchangeElements(stackTwo, stackOne);
        return popped;
    }
    
    public int peek() {
        exchangeElements(stackOne, stackTwo);
        int peeked = stackTwo.peek();
        exchangeElements(stackTwo, stackOne);
        return peeked;
    }
    
    public boolean empty() {
        return stackOne.isEmpty();
    }
    
    private void exchangeElements(Stack < Integer> stack1, Stack stack2) {
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []]

Output

x
–
+
cmd
[null, null, null, 1, 1, false]

#3 Code Example with Javascript Programming

Code - Javascript Programming


var MyQueue = function() {
  this.input = []
  this.output = []
};

MyQueue.prototype.push = function(x) {
  this.input.push(x)
};

MyQueue.prototype.pop = function() {
  if(this.output.length === 0) {
      while(this.input.length) {
          this.output.push(this.input.pop())
      }
  }
  return this.output.pop()
};

MyQueue.prototype.peek = function() {
  return this.output[this.output.length - 1] || this.input[0]
};

MyQueue.prototype.empty = function() {
  return this.input.length === 0 && this.output.length === 0
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []]

Output

x
–
+
cmd
[null, null, null, 1, 1, false]

#4 Code Example with Python Programming

Code - Python Programming


class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = []

    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: void
        """
        self.data.append(x)

    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        front = self.data[0]
        self.data = self.data[1:]
        return front

    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        return self.data[0]

    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        return not bool(self.data)
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []]

Output

x
–
+
cmd
[null, null, null, 1, 1, false]

#5 Code Example with C# Programming

Code - C# Programming


using System.Collections.Generic;

namespace LeetCode
{
    public class _0232_ImplementQueueUsingStacks
    {
        private readonly Stack < int> s1;
        private readonly Stack<int> s2;
        private int s1Front;

        public _0232_ImplementQueueUsingStacks()
        {
            s1 = new Stack < int>();
            s2 = new Stack<int>();
        }

        public void Push(int x)
        {
            if (s1.Count == 0)
                s1Front = x;
            s1.Push(x);
        }

        public int Pop()
        {
            if (s2.Count == 0)
                while (s1.Count > 0)
                    s2.Push(s1.Pop());

            return s2.Pop();
        }

        public int Peek()
        {
            if (s2.Count > 0)
                return s2.Peek();

            return s1Front;
        }

        public bool Empty()
        {
            return s1.Count == 0 && s2.Count == 0;
        }
    }

}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []]

Output

x
–
+
cmd
[null, null, null, 1, 1, false]
Advertisements

Demonstration

Previous
#231 Leetcode Power of Two Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#233 Leetcode Number of Digit One Solution in C, C++, Java, JavaScript, Python, C# Leetcode