Implement Queue using Stacks
leetcode: https://leetcode.com/problems/implement-queue-using-stacks/
Description:
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
Do not modify the linked list.
Idea:
**solution **
Step1: create two stack, one for in, one for out
Step2: push all elements to stack1, and then when pop element, add all stack1’s elements to stack2. It will change the Fisrt in Last out to First In First out, because stack pop the element from the top of the stack.
Step3: the same operations of peek method
Code:
class MyQueue {
//define two stack, one for in, the other for out
Stack<Integer> StackIn;
Stack<Integer> StackOut;
public MyQueue() {
//create two stack instance;
StackIn = new Stack<>();
StackOut = new Stack<>();
}
public void push(int x) {
//add elements into the Stack(IN)
StackIn.push(x);
}
public int pop() {
//extract elements from StackIN and add them to the StackOut
if(StackOut.isEmpty()){
//extract all StackIn elements and put them to the outStack
while(!StackIn.isEmpty()){
StackOut.push(StackIn.pop());
}
}
return StackOut.pop();
}
public int peek() {
//get StackOut elements from StackIn
if(StackOut.isEmpty()){
while(!StackIn.isEmpty()){
StackOut.push(StackIn.pop());
}
}
return StackOut.peek();
}
//if two stack are both empty
public boolean empty() {
return StackIn.isEmpty() && StackOut.isEmpty() ;
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/