Data structure: Stack
Introduction
A stack is a linear data structure that follows a LIFO (First In Last Out) order. There is a common example about a stack, imagine a stack of plates, the plate that is placed first is the last to leave the stack and the last that is placed is the first to leave it.
Another example could be the back button in the browser, each time you navigate on pages, the pages are stacked (push) and when you click on the back button it removes your last visited page (pop), then the forward button stack is filled (push) with the page that the back button was removing (pop). Therefore, the first visited page is the last to leave the stack and the last one is the first to leave it.
I tried to explain the functionality of a stack using a simple example like the back button.
Operations
A stack is an ADT (Abstract Data Type) that mentions what operations will perform but not how it will be implemented, this means that you can implement a stack using a linked list data structure, therefore, the stack name is gained for the operations it does. It contains the following basics operations:
- push(data) — Inserts a data in the stack
- pop() — Removes the last data inserted in the stack
- peek() — Displays the last data inserted in the stack, but it doesn’t remove it
- isEmpty() — Displays if the stack is empty
Implementation
It’s time to implement a stack, first of all, we need to create the stack class and the node class, I’ll explain in detail about them.
Implementing the Node class
A node is a structure which contains the passed data and the reference to another node. It looks like this:
Implementing the Stack Class
The Stack class will contain the operations that it needs and use the node class in it. We are going to implement the class constructor and then, we’ll create and explain each method (operation) it has.
Get Luis Aguilar’s stories in your inbox
Join Medium for free to get updates from this writer.
This is a basic stack class
Push(data)
This method adds items or elements to the stack, it creates a new node and checks if the list is empty, if it is, assigns the node to the head (it is the first element), else, the new node points to the head property becoming it as the next node of it and the new one is become to the first one.
Pop()
It checks if the list is not empty, otherwise, it has nothing to remove. It assigns the head to its next node and returns the obtained value.
peek()
It just returns the last element in the list, returning null (None in python) if the list is empty.
isEmpty()
This method returns a boolean telling us whether the list is empty or not, the way of knowing if a list is empty, it’s checking if the head is null (None in python).
This is a basic implementation of a stack, you can also add extra properties like length and a method to get it, this would displays the number of elements that the list has.
