Stack in Data Structure | DSA Tutorials

YASH PAL,

Stack – The stack is an abstract type of data structure. It contains elements in linear order, and we are allowed to insert and delete the data only at one end.

Stack in Data Structure
Figure 1: Stack in Data Structure

Example of Stack – As you see in Figure 1, here is the stack of plates. And in this stack, we can only insert a new plate from the top and can remove a plate from the top. So we only allow insertion and removal of the plate from the stack at the top end. And it follows the LIFO property, which means last in, first out. The element that is entered last can be deleted first. And we don’t allow performing operations in the middle area.

Implementation of the Stack

We can implement a stack using an array or a linked list. First, let’s see how we can implement a stack using an array.

Implementation of a stack using an array

Implementation of stack
Figure 1: Implementation of a stack

But before we implement a stack using an array, we need to find the top position of the stack from where we can easily perform insertion and deletion operations in the stack.  If we take the first position as the top position of the stack, then to insert a new value, we need to push one step forward for every element. Also, to delete an element from the stack, we need to push one step backwards for every element. And if we take the last position of the array as the top position of the stack, then we can easily insert and delete an element.

Stack implementation example using array
Figure 2: Stack implementation example using an array

In the above example, we take an empty array. First, we insert or push the values 20, 30, 15, and 40, then we pop the last entered values 40 and 15. And after that, we push 56 into the stack, and then we pop 56 from the stack.

Program to Implement a Stack using an array in Python

class EmptyStackError(Exception):
    pass
class Stack:

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

    def is_empty(self):
        return self.items == []

    def size(self):
        return len(self.items)

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

    def pop(self):
        if self.is_empty():
            raise EmptyStackError("Stack is empty")
        return self.items.pop()

    def peek(self):
        if self.is_empty():
            raise EmptyStackError("Stack is empty")
        return self.items[-1]

    def display(self):
        print(self.items)


if __name__ == '__main__':
    st = Stack()

    while True:
        print("1. Push")
        print("2. Pop")
        print("3. Peek")
        print("4. Size")
        print("5. Display")
        print("6. Quit")

        choice = int(input("Enter your choice : "))

        if choice == 1:
            x = int(input("Enter the element to be pushed : "))
            st.push(x)
        elif choice == 2:
            x = st.pop()
            print("Popped element is : ", x)
        elif choice == 3:
            print("Element at the top is : ", st.peek())
        elif choice == 4:
            print("Size of stack ", st.size())
        elif choice == 5:
            st.display()
        elif choice == 6:
            break        else:
            print("Wrong choice ")
        print()

Implementation of a stack using a linked list

Implementation of a stack using a linked list
Figure 3: Implementation of a stack using a linked list

First, we need to find which end we need to choose to perform operations on the linked list so we can easily insert and delete a new node or value in the stack. If we choose the last position of the linked list as the top position of the stack, then we need to traverse the whole list to insert and delete the node or value. 

And if we choose the first position of the linked list as the top position of the stack, then we don’t need to traverse the whole list to insert and delete the node or value. So we choose the first position of the linked list as the top position to implement the stack.

Push operation

To perform a push operation in a stack, we need to insert a new node at the beginning position of the linked list. And we already know how to insert a new node at the beginning of the linked list.

Push operation in stack
Figure 4: Push operation in the stack

If you don’t know how to insert a new node at the first position, then check out the insertion in the linked list tutorial.

Pop operation

To perform the pop operation in a stack, we need to delete the first node of the linked list. And we already know how to delete the first node of the linked list.

Pop operation in stack
Figure 5: Pop operation in the stack

If you don’t know how to delete the first node of the linked list, then check out the deletion in the linked list tutorial.

Python program to implement a stack

class EmptyStackError(Exception):
    pass
class Node:

    def __init__(self,value):
        self.info = value
        self.link = None
class Stack:

    def __init__(self):
        self.top = None
    def is_empty(self):
        return self.top == None
    def size(self):

        if self.is_empty():
            return 0
        count = 0        p = self.top
        while p is not None:
            count +=1            p = p.link
        return count

    def push(self,data):
        temp = Node(data)
        temp.link = self.top
        self.top = temp

    def pop(self):
        if self.is_empty():
            raise EmptyStackError("Stack is empty")
        popped = self.top.link
        self.top = self.top.link
        return popped

    def peek(self):
        if self.is_empty():
            raise EmptyStackError("Stack is empty")
        return self.top.info

    def display(self):
        if self.is_empty():
            print("Stack is empty")
            return
        print("Stack is :   ")
        p = self.top
        while p is not None:
            print(p.info, " ")
            p = p.link


if __name__ == '__main__':
    st = Stack()

    while True:
        print("1. Push")
        print("2. Pop")
        print("3. Peek")
        print("4. Size")
        print("5. Display")
        print("6. Quit")

        choice = int(input("Enter your choice : "))

        if choice == 1:
            x = int(input("Enter the element to be pushed : "))
            st.push(x)
        elif choice == 2:
            x = st.pop()
            print("Popped element is : ", x)
        elif choice == 3:
            print("Element at the top is : ", st.peek())
        elif choice == 4:
            print("Size of stack ", st.size())
        elif choice == 5:
            st.display()
        elif choice == 6:
            break        else:
            print("Wrong choice")
        print()

Stack Operations

  1. Push operation – To insert a new value or element in the stack is called a push operation.
  2. Pop operation – To delete a value or element is called a pop operation.
  3. Overflow state – When the stack becomes full, we don’t allow the insertion of a new element in it. This condition or state is called the overflow state of the stack.
  4. Underflow state – If we want to delete an element or value from an empty stack. This condition is called an underflow state of the stack.
  5. Top-end – The end position from where we want to insert and delete the elements in the stack is called the top of the list.

Example – If we implement a stack using an array and we want to insert and delete elements from the last position of the array, then the last position is called the top end of the stack.

Data Structures & Algorithms Tutorials for Beginners
Computer Science Tutorials Data Structures Tutorials

Leave a Reply

Your email address will not be published. Required fields are marked *