Stack is one of the most popular data structures used in algorithms. When using stacks, the elements added last would be the first ones to be removed. It's like a stack of plates, where the plate on top is the only one that can be removed until all the plates on top of it are taken away.
A stack can be used in many real-world situations. When opening websites in a web browser, you can click on the back button to move to the previous page. The history of pages could be stored in a stack, and as soon as you hit a back button you can be navigated to the top of the stack. If you hit back again, the top page from the stack is removed, and you are navigated to the one below it.
There are several ways of implementing a stack in a programming language like Python:
Using list - the top element of the queue will be the last element of the list. We can add with append, remove with pop, and get the element with [-1].
Using deque from collections - it supports adding and removing elements from both the start and the end.
LifoQueue from queue - Last-in-first-out queue, which is essentially the definition of the stack data structure.
from queue import LifoQueue
stack = LifoQueue()
# push
stack.put(1)
stack.put(2)
stack.put(3)
# pop
print(stack.get()) # prints 3
print(stack.get()) # prints 2
# peek
print(stack.queue[-1]) # prints 1
print(stack.empty()) # check if empty -> prints False
# Using a simple list
stack = []
# push
stack.append(1)
stack.append(2)
stack.append(3)
# pop
print(stack.pop()) # prints 3
print(stack.pop()) # prints 2
# peek
print(stack[-1]) # prints 1
print(len(stack) == 0) # check if empty -> prints False
Challenge: Check if the sequence of brackets is valid
Given a sequence of brackets of a mathematical expression (i.e. (()())), you are asked to check if that sequence is valid. A sequence of brackets is valid if every opening bracket has a corresponding closing one and there are no extra opening or closing brackets.
Input
The only line of the input contains a single line b (1 β€ |b| β€ ) containing the bracket sequence.
Output
The program should print Yes in case the bracket sequence is valid, and No otherwise.