Algorithm

Problem Name: 225. Implement Stack using Queues

Problem Link:  https://leetcode.com/problems/implement-stack-using-queues/
 

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

  • void push(int x) Pushes element x to the top of the stack.
  • int pop() Removes the element on the top of the stack and returns it.
  • int top() Returns the element on the top of the stack.
  • boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

  • You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
  • 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 100 calls will be made to push, pop, top, and empty.
  • All the calls to pop and top are valid.

Code Examples

#1 Code Example with C Programming

Code - C Programming


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

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

struct Queue{
    int size;
    struct QueueNode *front;
    struct QueueNode *tail;
};

void push(struct Queue *queue, int new_val) {
    if (queue == NULL) return;

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

    new_node->val = new_val;
    new_node->next = NULL;

    if (queue->tail != NULL) {
        queue->tail->next = new_node;
    }

    queue->tail = new_node;

    if (queue->front == NULL) {
        queue->front = new_node;
        queue->size = 1;
    }
    else{
        queue->size++;
    }
}

void pop(struct Queue *queue) {
    if (queue == NULL || queue->front == NULL) return;

    struct QueueNode *tmp = queue->front;
    queue->front = queue->front->next;

    free(tmp);
    queue->size--;

    if (queue->front == NULL) {
        queue->tail = NULL;
        queue->size = 0;
    }
}

int size(struct Queue *queue) {
    if (queue == NULL) {
        return 0;
    }
    else {
        return queue->size;
    }
}

bool isEmpty(struct Queue *queue) {
    if (queue == NULL) {
        return true;
    }
    else {
        return (queue->size == 0) ? true : false;
    }
}

typedef struct {
    struct Queue queue;
} Stack;

void stackCreate(Stack *stack, int maxSize) {
    if (stack == NULL) return;

    stack->queue.front = stack->queue.tail = 0;
    stack->queue.size = 0;
}

void stackPush(Stack *stack, int element) {
    if (stack == NULL) return;

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

/* Removes the element on top of the stack */
void stackPop(Stack *stack) {
    if (stack == NULL) return;

    int originalSize = size(&stack->queue);
    int i;
    for (i = 0; i  <  originalSize - 1; i++) {
        if (stack->queue.front == NULL) {
            return;
        }
        int tmp = stack->queue.front->val;
        pop(&stack->queue);
        push(&stack->queue, tmp);
    }

    pop(&stack->queue);
}

int stackTop(Stack *stack) {
    if (stack == NULL || stack->queue.tail == NULL) {
        return 0;
    }
    else {
        return stack->queue.tail->val;
    }
}

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

    return isEmpty(&stack->queue);
}

void stackDestroy(Stack *stack) {
    if (stack == NULL) return;

    while (size(&stack->queue) > 0) {
        pop(&stack->queue);
    }
}

int main() {

    Stack s;
    int maxSize = 5;
    stackCreate(&s, maxSize);

    printf("push 1 to stack.\n");
    stackPush(&s, 1);

    printf("push 2 to stack.\n");
    stackPush(&s, 2);

    printf("push 3 to stack.\n");
    stackPush(&s, 3);

    printf("current top of stack is: %d.\n", stackTop(&s));
    printf("stack is empty? %d.\n", stackEmpty(&s));

    printf("pop from stack.\n");
    stackPop(&s);

    printf("current top of stack is: %d.\n", stackTop(&s));

    printf("destroy stack.\n");
    stackDestroy(&s);

    printf("current top of stack is: %d.\n", stackTop(&s));
    printf("stack is empty? %d.\n", stackEmpty(&s));

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

Input

x
–
+
cmd
["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []]

Output

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

#2 Code Example with Java Programming

Code - Java Programming


class MyStack {
  
  private Queue primaryQueue;
  private Queue < Integer> secondaryQueue;
  
  public MyStack() {
    this.primaryQueue = new LinkedList<>();
    this.secondaryQueue = new LinkedList < >();
  }

  public void push(int x) {
    this.primaryQueue.add(x);
  }

  public int pop() {
    int result = moveFromPrimaryToSecondary();
    moveFromSecondaryToPrimary(true);
    return result;
  }

  public int top() {
    int result = moveFromPrimaryToSecondary();
    moveFromSecondaryToPrimary(false);
    return result;
  }
  
  public boolean empty() {
    return this.primaryQueue.isEmpty();
  }
  
  private int moveFromPrimaryToSecondary() {
    int last = this.primaryQueue.peek();
    while (!this.primaryQueue.isEmpty()) {
      last = this.primaryQueue.peek();
      this.secondaryQueue.add(this.primaryQueue.remove());
    }
    return last;
  }
  
  private void moveFromSecondaryToPrimary(boolean removeLast) {
    while (this.secondaryQueue.size() > 1) {
      this.primaryQueue.add(this.secondaryQueue.remove());
    }
    if (removeLast) {
      this.secondaryQueue.remove();
    } else {
      this.primaryQueue.add(this.secondaryQueue.remove());
    }
  }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []]

Output

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

#3 Code Example with Javascript Programming

Code - Javascript Programming


const MyStack = function() {
    this.stack = []
};

MyStack.prototype.push = function(x) {
    this.stack.push(x)
};

MyStack.prototype.pop = function() {
    return this.stack.pop()
};

MyStack.prototype.top = function() {
    return this.stack.length === 0 ? null : this.stack[this.stack.length - 1]
};

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

Input

x
–
+
cmd
["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []]

Output

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

#4 Code Example with Python Programming

Code - Python Programming


class MyStack:

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

    def push(self, x):
        """
        Push element x onto stack.
        :type x: int
        :rtype: void
        """
        self.data.append(x)

    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        :rtype: int
        """
        return self.data.pop()

    def top(self):
        """
        Get the top element.
        :rtype: int
        """
        return self.data[-1]

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

Input

x
–
+
cmd
["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []]

Output

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

#5 Code Example with C# Programming

Code - C# Programming


using System.Collections.Generic;

namespace LeetCode
{
    public class _0225_ImplementStackUsingQueues
    {
        private readonly Queue < int> queue;

        public _0225_ImplementStackUsingQueues()
        {
            queue = new Queue<int>();
        }

        public void Push(int x)
        {
            queue.Enqueue(x);
            var i = queue.Count - 1;
            while (i-- > 0)
                queue.Enqueue(queue.Dequeue());
        }

        public int Pop()
        {
            return queue.Dequeue();
        }

        public int Top()
        {
            return queue.Peek();
        }

        public bool Empty()
        {
            return queue.Count == 0;
        }
    }

}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []]

Output

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

Demonstration

Previous
#224 Leetcode Basic Calculator Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#226 Leetcode Invert Binary Tree Solution in C, C++, Java, JavaScript, Python, C# Leetcode