Data Structures: Stacks

This week in our data structure series.

We are tackling the stack.

Table of Contents

• What is a stack?
• Implementation
• Complexity
• Real Life Use-Cases
• Conclusion

What is a stack?

A stack is a linear data structure that stores items in Last-In/First-Out (LIFO) manner. In a stack, insertion, and deletion happen at the same end called "top of the stack".

It's similar to a pile of plates or a deck of cards. For example, in a pile of plates you can:

1. Put a new plate on the top
2. Remove the top plate

If you want to remove the plate at the bottom, then your gonna have to remove all the plates on the top. Hence why it's called Last-In/First-Out.

Methods

At the end of the day, a stack is an abstract data type, meaning that it can be implemented in many different ways but they all must comply with the same common functionality.

1. Push: add an item to the stack
2. Pop: remove the top-most item in the stack
3. isEmpty: checks if the stack is empty
4. isFull: checks if the stack is full
5. Peek: gets the top-most element without removing it

Implementation

As we said above, stacks can be implemented mainly in two ways:

1. Array
2. Linked-List

But keep in mind that a stack implemented using arrays are fixed stacks. Meaning they have a fixed size, however, because linked-list is not sequential, this gives them the advantage of being able to make a dynamic or limitless stack.

PS. You can bypass the array restriction by using a dynamic array.

We will now go through both implementations.

Array

For the sake of simplicity, we will use a fixed-sized array.

class Stack: 
    items = [];

    def __init__(self):
        self.items = []

    def  push(self, element): 
        self.items.append(element) 

    def  pop(self): 
        if len(self.items) == 0:
            print('Can not pop form an empty list')
        self.items.pop();
        print('Last item has been poped from the list')

    def isEmpty(self):
        print(len(self.items) == 0)

    def peek(self):
        if len(self.items) == 0:
            print('Stack is Empty')
        print(self.items[len(self.items) - 1]) ;

Linked List

class Node:

    # Class to create nodes of linked list
    # constructor initializes node automatically
    def __init__(self,data):
        self.data = data
        self.next = None

class Stack:

    # head is default NULL
    def __init__(self):
        self.head = None

    # Checks if stack is empty
    def isempty(self):
        if self.head == None:
            return True
        else:
            return False

    # Method to add data to the stack
    # adds to the start of the stack
    def push(self,data):

        if self.head == None:
            self.head=Node(data)

        else:
            newnode = Node(data)
            newnode.next = self.head
            self.head = newnode

    # Remove element that is the current head (start of the stack)
    def pop(self):

        if self.isempty():
            return None

        else:
            # Removes the head node and makes 
            #the preceeding one the new head
            poppednode = self.head
            self.head = self.head.next
            poppednode.next = None
            return poppednode.data

    # Returns the head node data
    def peek(self):

        if self.isempty():
            return None

        else:
            return self.head.data

Complexity

Push

Because we have direct access to the beginning of our array or linked-list, we can directly append to the list. Making it a time complexity of O(1)

Pop

The same thing with the push, we simply remove from the top-most item, which we have direct access to the top of the stack. Making it a time complexity of O(1)

Peek

We have access to the top of the stack, so it's also O(1)

Search

To search we are gonna have to go through each item sequentially, making it a O(n)

Real Life Use-Cases

1. Back/Forward Button In Web Browsers

A stack is used in back and forward buttons of web-browsers.

• As we move from one page to another those pages are placed on a stack
• URL's of a website get stored on a stack
• Current page is placed on the top of the stack
• When we press the back button that the elements start popping up and display the result in reverse order.
• In this way stack is used in the forward and backward button of a web browser

PS. This is method is also used in tech editors for the undo/redo mechanism.

2. In compilers

Compilers use the stack to calculate the value of expressions like 2 + 4 / 5 * (7 - 9) by converting the expression to prefix or postfix form.

3. To reverse a word

Put all the letters in a stack and pop them out. Because of the LIFO order of stack, you will get the letters in reverse order.

Conclusion

In summary:

1. A stack is a linear data structure that stores items in Last-In/First-Out (LIFO) manner.
2. In a stack, insertion, and deletion happen at the same end called "top of the stack".
3. The three main functions of the stack are push, pull, and peek.

I hope you got something out of this post, and if you have any questions feel free to leave them down below.