LeetCode No.232. Implement Queue using Stacks
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.
Notes:
You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.
Example 1:
Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]
Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: 1, 2
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
Constraints:
1 <= x <= 9
At most 100 calls will be made to push, pop, peek, and empty.
All the calls to pop and peek are valid.
Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.
Original Page
Method 1
class MyQueue {
Deque<Integer> stackIn;
Deque<Integer> stackOut;
public MyQueue() {
stackIn = new LinkedList<>();
stackOut = new LinkedList<>();
}
public void push(int x) {
while(stackOut.size()!=0){
stackIn.push(stackOut.pop());
}
stackOut.push(x);
while(stackIn.size()!=0){
stackOut.push(stackIn.pop());
}
}
public int pop() {
return stackOut.pop();
}
public int peek() {
return stackOut.peek();
}
public boolean empty() {
return stackOut.size()==0;
}
}
Here for each push operation, we do update the inner stack but it is not necessary.
Method2
class MyQueue {
Deque<Integer> stackIn;
Deque<Integer> stackOut;
public MyQueue() {
stackIn = new LinkedList<>();
stackOut = new LinkedList<>();
}
public void push(int x) {
stackIn.push(x);
}
public int pop() {
if(stackOut.size()==0){
while(stackIn.size()!=0){
stackOut.push(stackIn.pop());
}
}
return stackOut.pop();
}
public int peek() {
int first = this.pop();
stackOut.push(first);
return first;
}
public boolean empty() {
return stackOut.size()==0 && stackIn.size()==0;
}
}
Be careful here we cannot guarantee that stackOut is the final version stack, there might be some elements that exist in stackIn as well, so we need to do other steps in peek()and empty()
LeetCode 225. 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.
Follow-up: Can you implement the stack using only one queue?
class MyStack {
Deque<Integer> queueIn;
Deque<Integer> queueOut;
public MyStack() {
queueIn = new LinkedList<>();
queueOut = new LinkedList<>();
}
public void push(int x) {
queueOut.offer(x);
}
public int pop() {
if(queueOut.size()==0){
Deque<Integer> temp = queueIn;
queueIn = queueOut;
queueOut = temp;
}
while(queueOut.size() > 1){
queueIn.offer(queueOut.poll());
}
return queueOut.poll();
}
public int top() {
int result = this.pop();
this.push(result);
return result;
}
public boolean empty() {
return queueIn.size()==0 && queueOut.size()==0;
}
}
class MyStack {
Deque<Integer> queue;
public MyStack() {
queue = new LinkedList<>();
}
public void push(int x) {
queue.offer(x);
}
public int pop() {
int count = 1;
while(count < queue.size()){
queue.offer(queue.poll());
count++;
}
return queue.poll();
}
public int top() {
int result = this.pop();
this.push(result);
return result;
}
public boolean empty() {
return queue.size()==0;
}
}
LeetCode
public boolean isValid(String s) {
Deque<Character> stack = new LinkedList<>();
for(int i=0; i<s.length(); i++){
char cur = s.charAt(i);
if(cur=='(' || cur=='[' || cur=='{'){
stack.push(cur);
}
else{
if(stack.size()==0){
return false;
} else{
if(!isMatch(stack.pop(),cur)){
return false;
}
}
}
}
return stack.size()==0;
}
public boolean isMatch(char left, char right){
return switch (right) {
case ')' -> left == '(';
case ']' -> left == '[';
case '}' -> left == '{';
default -> false;
};
}
LeetCode 1047. Remove All Adjacent Duplicates In String
You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.
We repeatedly make duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.
Example 1:
Input: s = "abbaca"
Output: "ca"
Explanation:
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".
Example 2:
Input: s = "azxxzy"
Output: "ay"
Constraints:
1 <= s.length <= 105
s consists of lowercase English letters.
public String removeDuplicates(String s) {
Deque<Character> deque = new LinkedList<>();
for(int i=0; i<s.length(); i++){
if(!deque.isEmpty()){
if(deque.peek() == s.charAt(i)){
deque.pop();
} else{
deque.push(s.charAt(i));
}
} else{
deque.push(s.charAt(i));
}
}
StringBuffer sb = new StringBuffer();
while(!deque.isEmpty()){
sb.append(deque.pollLast());
}
return sb.toString();
}
More elegant way to do the evaluation
Top comments (0)