The “Stack” Data Structure and its Python Implementation

Imagine, we are piling up three plates — one on top of each other. We take Plate 1 and put it on the table. Next, we get hold of Plate 2 and stack it on Plate 1. Finally, we procure Plate 3 and place it over Plate 2.

Now, once we have a pile of three plates, we extract all the plates from the pile one by one. So, we would first pull out Plate 3, which is on the top. Next, Plate 2 and finally Plate 1.

Note the following observations in the above thought-experiment:

1. Newer items are placed near the top of the pile while older items are near the base
2. During the entire process, Plates have been inserted and extracted from the “top” of the pile rather than the “base”.
3. The order of insertion (putting Plates on a pile) is the reverse of the order of removal (extracting Plates from the pile). Thus, Plate 3 was the last Plate to be placed on the pile, whereas it was the first to be extracted from the pile.
4. In this process, the Plates have followed a LIFO (Last In First Out) ordering principle. The later Plates were among the first to be extracted out of the pile.

This is the main essence of the stack data structure! A stack data structure is an ordered collection of items where items follow a LIFO principle. Items in a stack are added and removed from the “top” end.

Stack Operations

The stack data structure has the following operations:

1. Stack(): Creates and returns an empty stack.
2. push(item): Adds a new item to the top of the stack.
3. pop(): Removes the top item from the stack.
4. peek(): The top item in the stack is returned but the stack is not modified.
5. isEmpty(): Checks if the stack is empty.
6. size(): Returns the number of items in the stack.

Python Implementation

To represent the stack data structure in Python, we create a Stack class. The stack operations would be implemented as methods of the aforementioned class. We can use the Python’s list data structure to represent the stack data structure’s operations. The following image shows the Python representation of the Stack data structure:

Stack Class

Balanced Parenthesis

A notable use of the stack data structure is in balancing parenthesis. Consider the following sequence of parenthesis:

((()))

The above sequence represents a balanced parenthesis. For every open parenthesis there’s a closing parenthesis. To figure out if a sequence of parenthesis is balanced or not, we can exploit the operations of the stack data structure.

Following is a typical algorithm to figure out if a sequence of parenthesis is balanced or not:

1. We read the sequence of parenthesis from left to right.
2. Whenever we encounter an open parenthesis “(“, we push it onto a stack.
3. Whenever we encounter a closing parenthesis “)”, we pop it from the stack.
4. At the end of the sequence, if the stack is empty, the sequence of parenthesis is balanced.