Stack

What is it? What are the best implementations of a stack?

A stack is a linear data structure, where it follows the Last-In-First-Out principle (LIFO) to store items. The LIFO principle is where the last items stored are the first items to be removed. A stack strictly follows this principle, and we will need to remember this when we later discuss different methods of implementing a stack and how it affects its time complexity. Let's start by going over the basic functions any stack will contain.

Basic Stack Class Functions

• __init__() — Initializes the type of data structure
• is_empty() — Returns True if the stack is empty, or False otherwise
• length() — Returns the number of items in the stack
• push() — Inserts the given item on the top of the stack
• peek() — Returns the item on the top of the stack
• pop() — Removes and returns the item on top of the stack

In the __init__(), you define which data structure you will use throughout the stack. We will go over implementing a stack using two different data structures, linked list and dynamic array. Later in this article, we will look at when we should use a linked list when we should use a dynamic array and their time complexity.

We will use the is_empty() and length() to quickly give us feedback on our stack. These are helper functions that are optional but do make it easier to interact with a stack.

The main functions of a stack are push(), peek(), pop(). These functions allow us to Create, Read, Update, and Delete (CRUD) items in a stack. Remember all these functions are always interacting with the top of the stack. The peek() function will always return the top of the stack. The push() function will always add items to the top of the stack, and the pop() function will only delete the top item on the stack. Remember how these functions strictly work for it affects the time complexity of the stack, and is important to consider when deciding which data structure, in the __init__(), to initialize the stack.

StackClass Implementations using different Data Structures

Dynamic Array

Using a dynamic array is the easiest way to initialize a stack, but it is not the best when it comes to time and space complexity. We will use a list as our dynamic array.

To initialize a list as our dynamic array, we will declare a variable called self.list and set it equal to an empty list. We will use self.list to interact with our stack inside our ArrayStack class.

Since we are using a list as our dynamic array we can use the built-in Python function called len() to return the size of our stack for length(). In order to check if our stack is empty, we will simply check if the length of our list is 0.

The next functions we have to code, push(), peek(), and pop(), all depend on how you setup up your stack. Going back to the basics of a stack, it’s based on LIFO, so we have an option of always interacting with the beginning of our stack, self.list[0], or the end of the stack, self.list[(n-1)].

Do we want our stack to always interact with the front of the list or the back of the list?

This is an important question because it will affect the time complexity of our push() and pop() functions of the Stack Class. Using Big O Notation, peek() will always be O(1) but is coded differently depending on where the top of the stack is at.

Top of the Stack is at index 0

When the top of the stack is at index 0, our push() and pop() functions will have a time complexity of O(n). The reason being is because of our dynamic array will have to shift all elements every time an element is added or deleted to the stack.

Having the top of the stack at index 0 our space complexity is high for when a dynamic array gets too larger, it will resize itself by making a new array with more space and then copying over all the values from the old array to the new array.

Top of the Stack is at index n-1

Setting the top of the stack at index n-1 is the best for time complexity when implementing a stack using a dynamic array. With setting up the stack to strictly interact with the end of the dynamic array, our push() and pop() will have a time complexity of O(1), for we no longer need to move all the other elements when adding or deleting an item from a stack.

Unfortunately, our space complexity is still high for our dynamic array still has to resize anytime it gets too big. For this reason, it's more accurate to say on average push() will have a time complexity of O(1), because occasionally our dynamic array will have to resize itself.

Linked List

Using a linked list is one of the best ways to implement a stack. If time-efficiency is important in your project, a linked list is highly recommended. Even though a linked list requires more code, it all better for a stack in terms of time and space complexity.

A linked list consists of nodes that store data and a reference link to the next node in the linked list. This allows the stack to no longer resize when it getting larger, for the nodes can be scattered in memory and with the reference link be found when needed.

There are still two ways to implement a listed list as your data structure for our StackClass, but let's initialize it first.

To implement our is_empty(), we will be checking if the head in our linked list is pointing to something. For length(), we will return the length of our stack using the built-in functions of our linked list.

Again depending on where you have the top of the stack start will affect how you code your StackClass push(), peek(), pop(). Whether you choose to have the top of the stack is at the head or tail of the linked list, the time complexity for push(), and peek() will be O(1).

Only when the top of the stack is at the tail of the linked list does the time complexity change for pop().

When the top of the stack is at the head of the linked list, the pop() is O(1) for it can easily have the head now point at the node that is next to the node that you are deleting, and delete the top of the stack without breaking our linked list.

When the top of the stack is at the tail, the pop() is O(n) for our nodes only reference the next node. With the top of stack being at the tail, the last node is pointing to the tail. Therefore we can’t simply delete it the node the tail is pointing at for it breaks our linked list.