Stack and queue in Python

Posted on Edited on In , Views:

Intro

A stack is a linear data structure that stores items in a Last-In/First-Out (LIFO) or First-In/Last-Out (FILO) manner. In stack, a new element is added at one end and an element is removed from that end only. The insert and delete operations are often called push and pop.

Like stack, queue is a linear data structure that stores items in First In First Out (FIFO) manner. With a queue the least recently added item is removed first. A good example of queue is any queue of consumers for a resource where the consumer that came first is served first.

Stack practices

[Leetcode 150] Evaluate Reverse Polish Notation

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

  • The valid operators are ‘+’, ‘-‘, ‘*’, and ‘/‘.
  • Each operand may be an integer or another expression.
  • The division between two integers always truncates toward zero.
  • There will not be any division by zero.
  • The input represents a valid arithmetic expression in a reverse polish notation.
  • The answer and all the intermediate calculations can be represented in a 32-bit integer.

Example 1:

1
2
3
Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

1
2
3
Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

1
2
3
4
5
6
7
8
9
Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Constraints:

  • 1 <= tokens.length <= 10^4
  • tokens[i] is either an operator: “+”, “-“, “*”, or “/“, or an integer in the range [-200, 200].

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        st = []
        op = ['+', '-', '*', '/']
        for t in tokens:
            if t in op:
                x , y = int(st.pop()), int(st.pop())
                temp = None
                if t == '+':
                    temp = x + y
                elif t == '-':
                    temp = y - x
                elif t == '*':
                    temp = x * y
                else:
                    temp = int(y / x)
                st.append(temp)
            else:
                st.append(t)

        return int(st[-1])

[Leetcode 155] Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

  • MinStack() initializes the stack object.
  • void push(int val) pushes the element val onto the stack.
  • void pop() removes the element on the top of the stack.
  • int top() gets the top element of the stack.
  • int getMin() retrieves the minimum element in the stack.
  • *ou must implement a solution with O(1) time complexity for each function.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Constraints:

  • -2^31 <= val <= 2^31 - 1
  • Methods pop, top and getMin operations will always be called on non-empty stacks.
  • At most 3 * 104 calls will be made to push, pop, top, and getMin.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class MinStack:

    def __init__(self):
        self.vals = []
        self.minVals = []
        
    def push(self, val: int) -> None:
        self.vals.append(val)
        if not self.minVals:
            self.minVals.append(val)
        else:
            if self.minVals[-1] >= val:
                self.minVals.append(val)

    def pop(self) -> None:
        if self.vals[-1] == self.minVals[-1]:
            self.minVals.pop()
        self.vals.pop()
        

    def top(self) -> int:
        return self.vals[-1]

    def getMin(self) -> int:
        return self.minVals[-1]  


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

[Leetcode 224] Basic Calculator

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

1
2
Input: s = "1 + 1"
Output: 2

Example 2:

1
2
Input: s = " 2 - (3 + 4) "
Output: -5

Example 3:

1
2
Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

Constraints:

  • 1 <= s.length <= 3 * 10^5
  • s consists of digits, ‘+’, ‘-‘, ‘(‘, ‘)’, and ‘ ‘.
  • s represents a valid expression.
  • ‘+’ is not used as a unary operation (i.e., “+1” and “+(2 + 3)” is invalid).
  • ‘-‘ could be used as a unary operation (i.e., “-1” and “-(2 + 3)” is valid).
  • There will be no two consecutive operators in the input.
  • Every number and running calculation will fit in a signed 32-bit integer.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
class Solution:
    def calculate(self, s: str) -> int:
        """
        Refer to https://leetcode.com/problems/basic-calculator/solutions/546092/simple-python-solution-using-stack-with-explanation-inline/?envType=study-plan-v2&envId=top-interview-150
        1. Take 3 containers:
        num -> to store current num value only
        sign -> to store sign value, initially +1
        res -> to store sum
        When ( comes these containers used for calculate sum of intergers within () brackets.
        --------------------
        2. When c is + or -
        Move num to res, because we need to empty num for next integer value.
        set num = 0
        sign = update with c
        --------------------
        3. When c is '('
        Here, we need num, res, sign to calculate sum of integers within ()
        So, move num and sign to stack => [num, sign]
        Now reset - res = 0, num = 0, sign = 1 (default)
        --------------------
        4. When c is ')' -> 2-(3+4), Here res=3, num=4, sign=1 stack [2, -] 
        res +=sign*num -> calculate sum for num first, then pop items from stack, res=7
        res *=stack.pop() - > Pop sign(+ or -) to multiply with res, res = 7*(-1)
        res +=stack.pop() - > Pop integer and add with prev. sum, res = -7 + 2 - 5
        --------------------
        Simple Example: 2 - 3
        Initially res will have 2,i.e. res = 2
        then store '-' in sign. it will be used when 3 comes. ie. sign = -1
        Now 3 comes => res = res + num*sign
        Return statement: res+num*sign => res = 2 + 3(-1) = 2 - 3 = -1
        """
        num = 0
        sign = 1
        res = 0
        stack = []
        for i in range(len(s)): # iterate characters
            c = s[i]
            
            if c.isdigit(): 
                # parse the consecutive digits. e.g. 23 -> 2 * 10 + 3
                num = num*10 + int(c) 
            
            elif c in '-+': # check for - and +
                # calculate the temporary result before '+' or '-'
                res += num*sign
                # save the new sign
                sign = -1 if c == '-' else 1
                # reset num to 0 for parsing the next operand
                num = 0
            elif c == '(':
                # we need res and sign to save the temporary result within '()'. Reset sign to default 1.
                stack.append(res)
                stack.append(sign)
                res = 0
                sign = 1
            elif c == ')':
                # calculate the result within '()'
                # e.g. 2 -(3 + 4) -> res = 3, num = 4, sign = 1, stack = [2, -]
                res +=sign*num # res = 3 * 1 + 4 = 7
                res *=stack.pop() # res = 7 * (-1) = -7
                res +=stack.pop() # res = -7 + 2 = -5
                num = 0 # reset num to 0
                
        return res + num*sign

    def calculate_recursive(self, s: str) -> int:
        def evaluate(i):
            res, digits, sign = 0, 0, 1

            while i < len(s):
                
                if s[i].isdigit():
                    # parse the operand
                    digits = digits * 10 + int(s[i])
                
                elif s[i] in '+-':
                    # evaluate the subresult before the next operator
                    res += digits * sign

                    # reset digits to 0
                    digits = 0

                    # reset operator sign
                    sign = 1 if s[i] == '+' else -1

                elif s[i] == '(':
                    # evalute the sub results in '()' and return the index of ')'
                    subres, i = evaluate(i+1)

                    # accumulate the result
                    res += subres * sign

                elif s[i] == ')':
                    # evaluate the subresult before ')'
                    res += digits * sign

                    # return the result and index
                    return res, i
                
                i += 1

            return res + digits * sign        

        return evaluate(0)

[Leetcode 394] Decode String

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 105.

Example 1:

1
2
Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2:

1
2
Input: s = "3[a2[c]]"
Output: "accaccacc"

Example 3:

1
2
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Constraints:

  • 1 <= s.length <= 30
  • s consists of lowercase English letters, digits, and square brackets ‘[]’.
  • s is guaranteed to be a valid input.
  • All the integers in s are in the range [1, 300].

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def decodeString(self, s: str) -> str:
        st = []
        num = 0
        res = ""

        for ch in s:
            # parse the repeat number
            if ch.isnumeric():
                num = num * 10 + int(ch)

            #  save the temporary string and repeat number
            elif ch == '[':
                st.append(res)
                st.append(num)
                res = ""
                num = 0
            
            # create the repeated strings
            elif ch == ']':
                repeat = st.pop()
                temp = st.pop()
                res = temp + res * repeat

            # parse the string to repeat
            else:
                res += ch

        return res

[Leetcode 735] Asteroid Collision

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

1
2
3
Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:

1
2
3
Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.

Constraints:

  • 2 <= asteroids.length <= 104
  • -1000 <= asteroids[i] <= 1000
  • asteroids[i] != 0

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        st = []

        for asteroid in asteroids:
            # only case to collide: -> <-
            if asteroid < 0:
                exploded = False
                while st and st[-1] > 0:
                    # explode both
                    if st[-1] == abs(asteroid):
                        exploded = True
                        st.pop()
                        break

                    # explode the smaller asteroid on the left
                    elif st[-1] < abs(asteroid):     
                        st.pop()
                        
                    # explode the asteroid and continue check the next asteroid
                    else:
                        exploded = True
                        break

                if not exploded:
                    st.append(asteroid)

            # cases not to collide:
            # -> ->
            # <- ->
            # <- <-
            else:
                st.append(asteroid)

        return st

[Leetcode 2390] Removing Stars From a String

You are given a string s, which contains stars *.

In one operation, you can:

  • Choose a star in s.
  • Remove the closest non-star character to its left, as well as remove the star itself.

Return the string after all stars have been removed.

Note:

  • The input will be generated such that the operation is always possible.
  • It can be shown that the resulting string will always be unique.

Example 1:

1
2
3
4
5
6
7
Input: s = "leet**cod*e"
Output: "lecoe"
Explanation: Performing the removals from left to right:
- The closest character to the 1st star is 't' in "leet**cod*e". s becomes "lee*cod*e".
- The closest character to the 2nd star is 'e' in "lee*cod*e". s becomes "lecod*e".
- The closest character to the 3rd star is 'd' in "lecod*e". s becomes "lecoe".
There are no more stars, so we return "lecoe".

Constraints:

  • 1 <= s.length <= 105
  • s consists of lowercase English letters and stars *.
  • The operation above can be performed on s.

Solution:

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def removeStars(self, s: str) -> str:
        st = []
        for c in s:
            if c != '*':
                st.append(c)
            else:
                st.pop()

        return "".join(st)

Queue practices

[Leetcode 933] Number of Recent Calls

You have a RecentCounter class which counts the number of recent requests within a certain time frame.

Implement the RecentCounter class:

  • RecentCounter() Initializes the counter with zero recent requests.
  • int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].

It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
Input
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
Output
[null, 1, 2, 3, 3]

Explanation
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1], range is [-2999,1], return 1
recentCounter.ping(100);   // requests = [1, 100], range is [-2900,100], return 2
recentCounter.ping(3001);  // requests = [1, 100, 3001], range is [1,3001], return 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002], range is [2,3002], return 3

Constraints:

  • 1 <= t <= 109
  • Each test case will call ping with strictly increasing values of t.
  • At most 104 calls will be made to ping.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
class RecentCounter:
    def __init__(self):
        self.qu = deque()

    def ping(self, t: int) -> int:
        self.qu.append(t)
        while self.qu:
            if self.qu[0] < t - 3000:
                self.qu.popleft()
            else:
                break

        return len(self.qu)

[Leetcode 649] Dota2 Senate

In the world of Dota2, there are two parties: the Radiant and the Dire.

The Dota2 senate consists of senators coming from two parties. Now the Senate wants to decide on a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

  • Ban one senator’s right: A senator can make another senator lose all his rights in this and all the following rounds.
    Announce the victory: If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and decide on the change in the game.
  • Given a string senate representing each senator’s party belonging. The character ‘R’ and ‘D’ represent the Radiant party and the Dire party. Then if there are n senators, the size of the given string will be n.

The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.

Suppose every senator is smart enough and will play the best strategy for his own party. Predict which party will finally announce the victory and change the Dota2 game. The output should be “Radiant” or “Dire”.

Example 1:

1
2
3
4
5
6
Input: senate = "RD"
Output: "Radiant"
Explanation: 
The first senator comes from Radiant and he can just ban the next senator's right in round 1. 
And the second senator can't exercise any rights anymore since his right has been banned. 
And in round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.

Example 2:

1
2
3
4
5
6
7
Input: senate = "RDD"
Output: "Dire"
Explanation: 
The first senator comes from Radiant and he can just ban the next senator's right in round 1. 
And the second senator can't exercise any rights anymore since his right has been banned. 
And the third senator comes from Dire and he can ban the first senator's right in round 1. 
And in round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.

Constraints:

  • n == senate.length
  • 1 <= n <= 104
  • senate[i] is either ‘R’ or ‘D’.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        radiant = deque()
        dire = deque()
        
        # add senate to separate queues
        for i, s in enumerate(senate):
            if s == 'R':
                radiant.append(i)
            else:
                dire.append(i)

        # senate votes to ban the opponent
        n = len(senate)
        while radiant and dire:
            # senator stays if he/she can vote earlier
            if radiant[0] < dire[0]:
                # front dire is eliminated from queue
                dire.popleft()

                # front radiant moves to the end of queue for next round
                radiant.popleft()
                radiant.append(n)
            else:
                # front radiant is eliminated
                radiant.popleft()

                # front dire moves to the end of queue for next round
                dire.popleft()
                dire.append(n)
            
            # increment the position in the queue
            n += 1

        return "Radiant" if radiant else "Dire"