Easy
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:
push to back
, peek/pop from front
, size
and is empty
operations are valid.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
100
calls will be made to push
, pop
, top
, and empty
.pop
and top
are valid.Follow-up: Can you implement the stack using only one queue?
import java.util.LinkedList
class MyStack {
private var queuePair = Pair(LinkedList<Int>(), LinkedList<Int>())
private var top: Int? = null
fun push(x: Int) {
queuePair.first.addLast(x)
top = x
}
fun pop(): Int {
if (isQueuesEmpty()) {
throw Exception()
}
val queuePair = selectSourceAndDestinationQueues(queuePair)
var value = 0
repeat(queuePair.first.size) {
when (queuePair.first.size) {
2 -> {
top = queuePair.first.removeFirst()
queuePair.second.addLast(top)
}
1 -> {
value = queuePair.first.removeFirst()
}
else -> {
queuePair.second.addLast(queuePair.first.removeFirst())
}
}
}
return value
}
fun top(): Int {
if (isQueuesEmpty()) {
throw Exception()
}
return top!!
}
fun empty(): Boolean {
return isQueuesEmpty()
}
private fun isQueuesEmpty(): Boolean {
if (queuePair.first.isEmpty() && queuePair.second.isEmpty()) {
return true
}
return false
}
private fun selectSourceAndDestinationQueues(queuePair: Pair<LinkedList<Int>, LinkedList<Int>>):
Pair<LinkedList<Int>, LinkedList<Int>> {
return if (queuePair.first.isNotEmpty()) {
Pair(queuePair.first, queuePair.second)
} else {
Pair(queuePair.second, queuePair.first)
}
}
}
/*
* Your MyStack object will be instantiated and called as such:
* var obj = MyStack()
* obj.push(x)
* var param_2 = obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.empty()
*/