Stack

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.

1. 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].

2. Using deque from collections - it supports adding and removing elements from both the start and the end.

3. 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

Input

Output

Examples