In this Leetcode Implement Queue using Stacks problem solution 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.
Problem solution in Python.
class MyQueue: def __init__(self): """ Initialize your data structure here. """ self._stack1 = [] self._stack2 = [] self._length = 0 def push(self, x: int) -> None: """ Push element x to the back of queue. """ self._stack1.append(x) self._length += 1 return None def pop(self) -> int: """ Removes the element from in front of queue and returns that element. """ if self._stack2: self._length -= 1 return self._stack2.pop() else: while self._stack1: self._stack2.append(self._stack1.pop()) if self._stack2: self._length -= 1 return self._stack2.pop() else: raise Exception() def peek(self) -> int: """ Get the front element. """ if self._stack2: return self._stack2[-1] else: while self._stack1: self._stack2.append(self._stack1.pop()) if self._stack2: return self._stack2[-1] else: raise Exception() def empty(self) -> bool: """ Returns whether the queue is empty. """ return not bool(self._length)
Problem solution in Java.
class MyQueue { Stack<Integer> s1; Stack<Integer> s2; /** Initialize your data structure here. */ public MyQueue() { this.s1 = new Stack<>(); this.s2 = new Stack<>(); } /** Push element x to the back of queue. */ public void push(int x) { s1.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { if(s2.isEmpty()){ while(!s1.isEmpty()){ s2.push(s1.pop()); } } return s2.pop(); } /** Get the front element. */ public int peek() { if(s2.isEmpty()){ while(!s1.isEmpty()){ s2.push(s1.pop()); } } return s2.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { if(s1.isEmpty() && s2.isEmpty()) return true; return false; } }
Problem solution in C++.
class MyQueue { std::stack<int> m_normal; std::stack<int> m_reversed; public: /** Initialize your data structure here. */ MyQueue() { } /** Push element x to the back of queue. */ void push(int x) { m_normal.push(x); } /** Removes the element from in front of queue and returns that element. */ int pop() { if(m_reversed.empty()) { while(!m_normal.empty()) { m_reversed.push(m_normal.top()); m_normal.pop(); } } int top = m_reversed.top(); m_reversed.pop(); return top; } /** Get the front element. */ int peek() { if(m_reversed.empty()) { while(!m_normal.empty()) { m_reversed.push(m_normal.top()); m_normal.pop(); } } return m_reversed.top(); } /** Returns whether the queue is empty. */ bool empty() { return m_normal.empty() and m_reversed.empty(); } };
Problem solution in C.
typedef struct { int *arr; int top; } Queue; /* Create a queue */ void queueCreate(Queue *queue, int maxSize) { queue->arr=(int*)malloc(maxSize*sizeof(int)); queue->top=0; } /* Push element x to the back of queue */ void queuePush(Queue *queue, int element) { int top=queue->top++; int i; if(top==0){ queue->arr[top]=element; } else{ for(i=top-1;i>=0;i--) queue->arr[i+1]=queue->arr[i]; queue->arr[0]=element; } } /* Removes the element from front of queue */ void queuePop(Queue *queue) { queue->top--; } /* Get the front element */ int queuePeek(Queue *queue) { int top=queue->top; return queue->arr[top-1]; } /* Return whether the queue is empty */ bool queueEmpty(Queue *queue) { return !queue->top; } /* Destroy the queue */ void queueDestroy(Queue *queue) { queue->top=0; }
0 Comments