Queue & Stack
Stack
Stack is the data structure The first item that comes in will be the first to go out. Let's look at this question (LeetCode Link)
Given a string
s
containing just the characters'('
,')'
,'{'
,'}'
,'['
and']'
, determine if the input string is valid.An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
To validate a string of parentheses is valid, we must have a corresponding opening bracket when we see a closing bracket. Lets look at some examples:
valid_string_1 = "([])"
We can process the string in the following way:
#1st character from valid_string_1
valid_string_1_step_1 = ["("]
We have the first character first. We do not need to do anything if it is an opening bracket.
#2nd character from valid_string_1
valid_string_1_step_2 = ["(", "["]
We have the second character now. Again, we do not need to do anything if it is an opening bracket.
#3rd character from valid_string_1
valid_string_1_step_3a = ["(", "[", "]"]
Here, we see a matching pair "["
and "]"
, so we can cancel them out.
#3rd character from valid_string_1 (removing valid pair)
valid_string_1_step_3b = ["("]
We have removed the two last seen elements form the stack.
#4th character from valid_string_1 (after removing 2nd and 3rd)
valid_string_1_step_4a = ["(", ")"]
After adding the fourth character, we see a matching pair between the 1st character and the 4th character. We can remove it now.
#4th character from valid_string_1 (after removing 1st and 4th)
valid_string_1_step_4a = []
With no more character to process and with an empty stack, we know that there are no remaining opening and closing brackets. Hence, we can validate this string.
Now let's look at a counter example:
invalid_string_1 = "[()}"
Similar to the scenario above, we can skip the first two characters and have:
invalid_string_1_step3a = ["[", "(", ")"]
We see a matching pair in the 2nd character and the 3rd character, so we can remove them.
invalid_string_1_step3b = ["["]
Now we look at the 4th character:
invalid_string_1_step4 = ["[", "}"]
We have a closing bracket, and it is not matching its corresponding opening bracket ("{"
), so we know that this string is invalid.
Are you able to code the solution out after looking at these two examples?
class Solution:
def isValid(self, s: str) -> bool:
#we use a stack to keep track of brackets
stack = []
#iterate the characters in the string
for c in s:
#we store the character in the stack if it is an opening bracket
if(c == "(" or c == "[" or c == "{"):
stack.append(c)
#we check if there is a matching opening bracket
#when we see a closing bracket
elif(c == ")"):
if(len(stack) == 0 or stack[-1] != "("):
return False
else:
stack.pop()
#we check if there is a matching opening bracket
#when we see a closing bracket
elif(c == "]"):
if(len(stack) == 0 or stack[-1] != "["):
return False
else:
stack.pop()
#we check if there is a matching opening bracket
#when we see a closing bracket
elif(c == "}"):
if(len(stack) == 0 or stack[-1] != "{"):
return False
else:
stack.pop()
#if the stack is not empty, there are some unmatched opening brackets
#this suggests it is not valid
if(len(stack) != 0):
return False
return True
Queue
Queue is the data structure that is First-In-First-Out. The first person who enters the queue should be the first person to leave the queue.
We can look at the following problem (LeetCode Link)
As the problem statement and examples are quite long, we kindly ask you to read them on LeetCode.
To implement a Queue, we must have a data structure that handles adding element on the left in __ time. These are the options in different languages:
- Python:
queue = deque([]) # queue.appendleft(x) , queue.pop()
- C++:
queue<int> q; // q.push(x), q.pop()
We can use these data structures to simulate this problem
class Solution:
def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
queue = deque([])
#we initialize the queue first
#as we need to keep track of the kth person, we add the index as well
for i in range(len(tickets)):
ticket_needed = tickets[i]
queue.appendleft([i,ticket_needed])
#keep track of overall time
time = 0
#we continue until queue is empty
while(queue):
#each person spends one second for purchase
time += 1
#access the first person and her ticket needed from the queue
first_person_in_queue, tickets_remaining = queue[-1]
#the first person buys one ticket , so she needs one less ticket
tickets_remaining -= 1
#we remove the first person from the queue
queue.pop()
#if the first person still needs to buy more tickets, we move her back to the end of the queue
if(tickets_remaining != 0):
queue.appendleft([first_person_in_queue, tickets_remaining])
#if the first person is the target and she has bought all the tickets, we return the time
else:
if(first_person_in_queue == k):
return time
return time
Suggested Problems
Problem Name | Difficulty | Solution Link |
---|---|---|
0155 - Min Stack | Easy | View Solutions |
0496 - Next Greater Element I | Easy | View Solutions |
1475 - Final Prices With a Special Discount in a Shop | Easy | View Solutions |