A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. In the pushdown stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack. A stack is a limited access data structure - elements can be added and removed from the stack only at the top. Here is a structural definition of a Stack: a stack is either empty or it consists of a top and the rest which is a Stack.
- stack =  # Create the stack
- stack.append(object) # Add object to the top of the stack
- stack.pop() -> object # Return the top most object from the stack and also remove it
- list[-1] -> object # Peek the top most object without removing it
In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed.
Due to the way their elements are accessed, stacks are also known as Last-In, First-Out (LIFO) stacks.
In Python one can use lists as stacks with
append() as push and
pop() as pop operations. Both operations run in constant time O(1).
deque data structure can also be used as a stack. Compared to lists,
deques allow push and pop operations with constant time complexity from both ends.
Creating a Stack class with a List Object
list object you can create a fully functional generic Stack with helper methods such as peeking and checking if the stack is Empty. Check out the official python docs for using
An example run:
Stacks are often used for parsing. A simple parsing task is to check whether a string of parentheses are matching.
For example, the string
() is matching, because the outer and inner brackets form pairs.
()<>) is not matching, because the last
) has no partner.
([)] is also not matching, because pairs must be either entirely inside or outside other pairs.