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 = [];

<span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="n">self</span><span class="p">):</span>
    <span class="n">self</span><span class="p">.</span><span class="n">items</span> <span class="o">=</span> <span class="p">[]</span>

<span class="k">def</span>  <span class="nf">push</span><span class="p">(</span><span class="n">self</span><span class="p">,</span> <span class="n">element</span><span class="p">):</span> 
    <span class="n">self</span><span class="p">.</span><span class="n">items</span><span class="p">.</span><span class="nf">append</span><span class="p">(</span><span class="n">element</span><span class="p">)</span> 

<span class="k">def</span>  <span class="nf">pop</span><span class="p">(</span><span class="n">self</span><span class="p">):</span> 
    <span class="k">if</span> <span class="nf">len</span><span class="p">(</span><span class="n">self</span><span class="p">.</span><span class="n">items</span><span class="p">)</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
        <span class="nf">print</span><span class="p">(</span><span class="sh">'</span><span class="s">Can not pop form an empty list</span><span class="sh">'</span><span class="p">)</span>
    <span class="n">self</span><span class="p">.</span><span class="n">items</span><span class="p">.</span><span class="nf">pop</span><span class="p">();</span>
    <span class="nf">print</span><span class="p">(</span><span class="sh">'</span><span class="s">Last item has been poped from the list</span><span class="sh">'</span><span class="p">)</span>

<span class="k">def</span> <span class="nf">isEmpty</span><span class="p">(</span><span class="n">self</span><span class="p">):</span>
    <span class="nf">print</span><span class="p">(</span><span class="nf">len</span><span class="p">(</span><span class="n">self</span><span class="p">.</span><span class="n">items</span><span class="p">)</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span>

<span class="k">def</span> <span class="nf">peek</span><span class="p">(</span><span class="n">self</span><span class="p">):</span>
    <span class="k">if</span> <span class="nf">len</span><span class="p">(</span><span class="n">self</span><span class="p">.</span><span class="n">items</span><span class="p">)</span> <span class="o">==</span> <span class="mi">0</span><span class="p">:</span>
        <span class="nf">print</span><span class="p">(</span><span class="sh">'</span><span class="s">Stack is Empty</span><span class="sh">'</span><span class="p">)</span>
    <span class="nf">print</span><span class="p">(</span><span class="n">self</span><span class="p">.</span><span class="n">items</span><span class="p">[</span><span class="nf">len</span><span class="p">(</span><span class="n">self</span><span class="p">.</span><span class="n">items</span><span class="p">)</span> <span class="o">-</span> <span class="mi">1</span><span class="p">])</span> <span class="p">;</span>



    

    

Linked List

class Node:

<span class="c1"># Class to create nodes of linked list



    

    




    # constructor initializes node automatically

    def init(self,data):

        self.data = data

        self.next = None

class Stack:

<span class="c1"># head is default NULL



    

    




    def init(self):

        self.head = None

<span class="c1"># Checks if stack is empty



    

    




    def isempty(self):

        if self.head == None:

            return True

        else:

            return False

<span class="c1"># Method to add data to the stack



    

    




    # adds to the start of the stack

    def push(self,data):

    <span class="k">if</span> <span class="n">self</span><span class="p">.</span><span class="n">head</span> <span class="o">==</span> <span class="bp">None</span><span class="p">:</span>
        <span class="n">self</span><span class="p">.</span><span class="n">head</span><span class="o">=</span><span class="nc">Node</span><span class="p">(</span><span class="n">data</span><span class="p">)</span>

    <span class="k">else</span><span class="p">:</span>
        <span class="n">newnode</span> <span class="o">=</span> <span class="nc">Node</span><span class="p">(</span><span class="n">data</span><span class="p">)</span>
        <span class="n">newnode</span><span class="p">.</span><span class="nb">next</span> <span class="o">=</span> <span class="n">self</span><span class="p">.</span><span class="n">head</span>
        <span class="n">self</span><span class="p">.</span><span class="n">head</span> <span class="o">=</span> <span class="n">newnode</span>

<span class="c1"># Remove element that is the current head (start of the stack)



    

    




    def pop(self):

    <span class="k">if</span> <span class="n">self</span><span class="p">.</span><span class="nf">isempty</span><span class="p">():</span>
        <span class="k">return</span> <span class="bp">None</span>

    <span class="k">else</span><span class="p">:</span>
        <span class="c1"># 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

<span class="c1"># Returns the head node data



    

    




    def peek(self):

    <span class="k">if</span> <span class="n">self</span><span class="p">.</span><span class="nf">isempty</span><span class="p">():</span>
        <span class="k">return</span> <span class="bp">None</span>

    <span class="k">else</span><span class="p">:</span>
        <span class="k">return</span> <span class="n">self</span><span class="p">.</span><span class="n">head</span><span class="p">.</span><span class="n">data</span>



    

    

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.