Stack data structure

The data structure is one of the important parts of programming. It will help you to solve your problem more efficiently. Both in terms of run time and memory used. Provided if you have implemented the correct data structure. So let’s understand the stack data structure. Its implementation and uses of it.

What is a stack?

Stack is the linear type of data structure. It uses the Last In First Out(LIFO) principle for its operation. The last inserted element comes out first. In order to understand the stack concept, let us consider an open container. Where we can insert/put things from only one open side. Whatever you put in the container in last, you can take it out at first then followed by its previous one. This means you can take out the first inserted thing at last only.

Basic operations on a stack

Some of the basic operations that we perform on a stack data structure are listed below.

1. Push(element): We can insert or add the element using the push function. It will take the element to be inserted inside the stack. You can insert elements from only one side(i.e top).
2. Pop(): It is used to delete the element from the stack. You can delete the element from the top only.
3. isEmpty(): It is to check whether the stack is empty or not.
4. isFull(): It is to check whether the stack is full or not.

Implementation of stack data structure

We will implement the stack data structure using python and C programming languages.

Pseudocode for stack push and pull functions

Algorithm Stacks(stack, size, indx){
//Push function to insert an element
Push(element){
    if indx+1 == size then 
        return "full"
    else then
        stack[indx+1] = element
    } 
// Pop function to delete the element
Pop(){
    if indx == -1 then
        return "stack is empty"
    else then
        data = stack[indx]
        indx = indx - 1
        print data
    }
}

Stack implementation using the list in python

The source code for stack implementation in python looks different from the above pseudocode. Because it is very simple to implement it using the list data type. The list data type has its own function to handle the operations.

#Stack implementation in python

stack = [] #empty stack initialization

#insert an element
def Push(element):
    stack.append(element)
    print("Inserted | stack: ",stack)

#Pop function to delete an element
def Pop():
    stack.pop()
    print("Deleted | stack: ",stack)

def isEmpty():
    if len(stack) == 0:
        return True
    else:
        return False

#Stack Opetations
Push(3)
Push(6)
Pop()
print("stack: ",stack, isEmpty())
Pop()
print("stack: ",stack, isEmpty())

'''
The isFull() function is not implemented. 
As list in python can have dynamic size.
'''

Stack implementation using array in C

The source code for the stack implementation in C using an array is given below. It is very similar to the pseudocode given above.

#include<stdio.h>

#define size 4
int stack[size], indx = -1;

void Push(int element){
	if(indx+1 == 10){
		printf("Stack is full\n");
	}else{
		indx = indx + 1;
		stack[indx] = element;
		printf("Push element is %d\n", element);
	}
}

void Pop(){
	if(indx == -1){
		printf("Stack is empty\n");
	}else{
		printf("Pop element is %d\n", stack[indx]);
		indx = indx - 1;
	}
}

void isEmpty(){
	if(indx == -1){
		printf("Stack is empty\n");
	}else{
		printf("Stack is not empty\n");
	}
}

void isFull(){
	if(indx+1 == size){
		printf("Stack is full\n");
	}else{
		printf("Stack is not full\n");
	}
}

int main(){
	Push(20);
	Push(10);
	isFull();
	Pop();
	isEmpty();
	Pop();
	isEmpty();
	Push(1);
	Push(2);
	Push(3);
	Push(4);
	isFull();
	return 0;
}

Watch the video to understand better the stack data structure

Time and space complexity

The run time complexity of push and pop operations in the stack is O(1). It will take a constant time to perform the operations. The space complexity of push and pop operation in the stack is O(1). As does not require additional memory to perform the operations.

Uses of stack data structure

Some of the uses of a stack are listed below.

• Reverse a string. You can use the stack to store the string and print out the reverse of it by popping out the stack elements or by traversing through it.
• Depth First Search(DFS). You can implement DFS using the stack.
• Undo function in the text editor.
• Balance parenthesis problem. You can solve the balance parenthesis problem using the stack data structure.
• Recursion function.
• Browser back and forth button.
• Expression Conversion(Infix, Prefix, Postfix). Basically to evaluate the arithmetic operations.

Conclusion

In this article, you have learned about the stack data structure. Implementation of the stack in python and C programming languages. You have seen the uses/application of the stack in the various problem-solving domains.

You may be interested to learn about the following topics:

• Create text to speech converter application using python and flask framework.[ Read More ]
• Image classification using machine learning algorithms.[ Read More ]
• Audio word classification using machine learning algorithms.[ Read More ]