Title: Implement Queue using Stacks Source: leetcode.com
Implement the following operations of a queue using stacks.
- push(x) — Push element x to the back of queue.
- pop() — Removes the element from in front of queue.
- peek() — Get the front element.
- empty() — Return whether the queue is empty.
Notes:
- You must use only standard operations of a stack — which means only
push to top,peek/pop from top,size, andis emptyoperations are valid. - Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
- You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
/* https://leetcode.com/problems/implement-queue-using-stacks/ */ import java.util.Stack; public class ImplementQueueUsingStacks { Stack<Integer> primary = new Stack<Integer>(); Stack<Integer> auxiliary = new Stack<Integer>(); // Push element x to the back of queue. public void push(int x) { primary.push(x); } // Removes the element from in front of queue. public void pop() { if(auxiliary.isEmpty()) { while(!primary.isEmpty()) { auxiliary.push(primary.pop()); } } if(!auxiliary.isEmpty()) { auxiliary.pop(); } } // Get the front element. public int peek() { if(auxiliary.isEmpty()) { while(!primary.isEmpty()) { auxiliary.push(primary.pop()); } } if(!auxiliary.isEmpty()) { return auxiliary.peek(); } return -1; } // Return whether the queue is empty. public boolean empty() { if(primary.isEmpty() && auxiliary.isEmpty()) { return true; } return false; } public static void main(String args[]) { ImplementQueueUsingStacks i = new ImplementQueueUsingStacks(); i.push(1); i.push(2); System.out.println(i.peek()); i.push(3); System.out.println(i.peek()); i.pop(); System.out.println(i.peek()); } } |