Stack in Data structure

The stack is an abstract type of data structure. it contains elements in linear order and we allow to insert and delete the data only at one end.

Example of the stack in Data structure

as you see in the above image here is the stack of the plates. and in this stack, we can only insert a new plate from the top and can remove the 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 means last in first out. the element which is entered at the last can be deleted first. and we don’t allow to perform operations in the middle area.

Push operation

to insert a new value or element in the stack is called a push operation.

Pop operation

to delete a value or element is called a pop operation.

Overflow state

when the stack becomes full and we don’t allow to insert of a new element in it. this condition or state is called the overflow state of the stack.

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.

Top-end 

the end position from where we want to insert and delete the elements in the stack is called the top end of the list.

Example

if we implement a stack using the array and we want to insert and delete the element from the last position of the array then the last position is called the top end of the stack.

Implementation of the stack

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

Implementation of stack using an array.

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 a 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 backward 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.

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 Implementation of stack using an array in the 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 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.

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.

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 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()