# Stack and queue in Python

## 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 | Input: tokens = ["2","1","+","3","*"] |

Example 2:

1 | Input: tokens = ["4","13","5","/","+"] |

Example 3:

1 | Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] |

Constraints:

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

Solution:

1 | class Solution: |

### [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 | Input |

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 | class MinStack: |

### [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 | Input: s = "1 + 1" |

Example 2:

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

Example 3:

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

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 | class Solution: |

### [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 | Input: s = "3[a]2[bc]" |

Example 2:

1 | Input: s = "3[a2[c]]" |

Example 3:

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

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 | class Solution: |

### [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 | Input: asteroids = [5,10,-5] |

Example 2:

1 | Input: asteroids = [8,-8] |

Constraints:

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

Solution:

1 | class Solution: |

### [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 | Input: s = "leet**cod*e" |

Constraints:

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

Solution:

1 | class Solution: |

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

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 | class RecentCounter: |

### [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 | Input: senate = "RD" |

Example 2:

1 | Input: senate = "RDD" |

Constraints:

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

Solution:

1 | class Solution: |