LeetCode Day9 Stack&Queue Part 1
Tags: leetcode, java, algorithms, datastructures
Published: 2024-06-15 07:52:11

#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] (leftmost is front of the queue)
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](https://leetcode.com/problems/implement-queue-using-stacks/description/)


##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;
    }
}
```


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/w6d469qkkhh732j94hax.png)
Here for each push operation, we do update the inner stack but it is not necessary.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ws5p8k3qvzllzl9bcfbb.png)


##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()
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uzce59yqls9043po97c4.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5ysizk26clag2dr2aiub.png)



#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?

[Original Page](https://leetcode.com/problems/implement-stack-using-queues/description/)

```
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();   
    }
```

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tkzj7hece451p4fdbume.png)

More elegant way to do the evaluation 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wtg3e7uyygiuw5p8ic24.png)