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:
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
collections- it supports adding and removing elements from both the start and the end.
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.
The only line of the input contains a single line
b(1 ≤ |b| ≤ ) containing the bracket sequence.
The program should print
Yesin case the bracket sequence is valid, and
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB