Leetcode Day 9 - Stack & Queue Fundamentals

Stack & Queue

Diff	Problem	Python	Java
	232 Implement Queue using Stacks	✅
	225 Implement Stack using Queues	✅
	20 Valid Parentheses	✅
	1047 Remove All Adjacent Duplicates In String	✅

Implement Queue using Stacks

Link to Leetcode question¹

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

Solution

A detailed explaination of solution can be found here².

Python

class MyQueue(object):

    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def push(self, x):
        self.stack_in.append(x)

    def pop(self):
        if self.empty():
            return None
        else:
            return self.stack_out.pop()

    def peek(self):
        """
        :rtype: int
        """
        if self.empty():
            return None
        else:
            return self.stack_out[-1]
        

    def empty(self):
        if(len(self.stack_out) != 0):
            return False
        if(len(self.stack_in) != 0):
            for i in range(len(self.stack_in)):
                self.stack_out.append(self.stack_in.pop())
            return False
        return True

Implement Stack using Queues

Link to Leetcode question³

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

Solution

A detailed explaination of solution can be found here⁴.

Python

from collections import deque
class MyStack(object):

    def __init__(self):
        self.queue_in = deque()
        self.queue_out = deque()

    def push(self, x):
        self.queue_in.append(x)
        
    def pop(self):
        if self.empty():
            return None

        for i in range(len(self.queue_in) - 1):
            self.queue_out.append(self.queue_in.popleft())
        
        self.queue_in, self.queue_out = self.queue_out, self.queue_in    
        return self.queue_out.popleft()

        

    def top(self):
        if self.empty():
            return None

        for i in range(len(self.queue_in) - 1):
            self.queue_out.append(self.queue_in.popleft())
        
        self.queue_in, self.queue_out = self.queue_out, self.queue_in 
        temp = self.queue_out.popleft()   
        self.queue_in.append(temp)
        return temp

        

    def empty(self):
        return len(self.queue_in) == 0

Valid Parentheses

Link to Leetcode question⁵

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1

Input: s = "()"
Output: true

Example 2

Input: s = "()[]{}"
Output: true

Example 3

Input: s = "(]"
Output: false

Solution

A detailed explaination of solution can be found here⁶.

Python

class Solution(object):
    def isValid(self, s):
        stack = []
        end = {'(': ')', '{': '}', '[': ']'}

        for c in s:
            if c in end.keys():
                stack.append(c)
            elif len(stack) == 0 or end[stack[-1]] != c:
                return False
            else:
                stack.pop()
    
        
        return len(stack) == 0

Similar Questions

Diff	Similar Questions	Python	Java
	22 Generate Parentheses7
	32 Longest Valid Parentheses8
	301 Remove Invalid Parentheses9

Remove All Adjacent Duplicates In String

Link to Leetcode question¹⁰

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"

Solution

A detailed explaination of solution can be found here¹¹.

Python

class Solution(object):
    def removeDuplicates(self, s):
        stack = []

        for c in s:
            if len(stack) != 0:
                if stack[-1] == c:
                    stack.pop()
                else:
                    stack.append(c)
            else:
                stack.append(c)
        
        return ''.join(stack)

Similar Questions

Diff	Similar Questions	Python	Java
	1209 Remove All Adjacent Duplicates in String II12
	2390 Removing Stars From a String13

Reference

1. Leetcode-232 Implement Queue using Stacks: https://leetcode.com/problems/implement-queue-using-stacks/description/. ↩︎

2. 代码随想录-用栈实现队列: https://programmercarl.com/0232.用栈实现队列.html. ↩︎

3. Leetcode-225 Implement Stack using Queues: https://leetcode.com/problems/implement-stack-using-queues/. ↩︎

4. 代码随想录-用队列实现栈: https://programmercarl.com/0225.用队列实现栈.html. ↩︎

5. Leetcode-20 Valid Parentheses: https://leetcode.com/problems/valid-parentheses/description/. ↩︎

6. 代码随想录-有效的括号: https://programmercarl.com/0020.有效的括号.html. ↩︎

7. Leetcode-22 Generate Parentheses: https://leetcode.com/problems/generate-parentheses/description/. ↩︎

8. Leetcode-32 Longest Valid Parentheses: https://leetcode.com/problems/longest-valid-parentheses/description/. ↩︎

9. Leetcode-301 Remove Invalid Parentheses: https://leetcode.com/problems/remove-invalid-parentheses/. ↩︎

10. Leetcode-1047 Remove All Adjacent Duplicates In String: https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/description/. ↩︎

11. 代码随想录-删除字符串中的所有相邻重复项: https://programmercarl.com/1047.删除字符串中的所有相邻重复项.html. ↩︎

12. Leetcode-1209 Remove All Adjacent Duplicates in String II: https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/description/. ↩︎

13. Leetcode-2390 Removing Stars From a String: https://leetcode.com/problems/removing-stars-from-a-string/. ↩︎