What is Stack in Data Structure?

Data structures play a significant role in arranging data in a specific format or order within an application. Without applying the proper data structure, your app will not function properly. Stack and queue are prominent data structures that enable developers to perform various concepts and operations. For Data Science professionals, an understanding of various data structures is essential. Learn through this Data Science Training Course. This article will take a comprehensive walkthrough of the stack, its representation, working, essential operation & real-life applications.

What is a Stack Data Structure?

Stack is a linear data structure that follows the LIFO (Last In First Out) principle for inserting and deleting elements from it. By LIFO, we mean the last element that we insert within the stack is the first element we can remove from it. You can assume a stack data structure as the pile of books or rack of plates on top of another.

Here, we can put a new book or plate on the other. Again, we can only remove one book or plate from the top of the stack. In the stack data structure, the position from where we can add or remove elements is called the "Top" of the stack.

How can we Implement a Stack Data Structure?

We can implement stack data structure in almost every programming language like C, C++, Python, Java, C#, etc. In C and C++, we can perform this using an array. In Python, we can use a list to achieve the concept of a stack using Array or ArrayList in Java & C#.

Basic Operations of a Stack Data Structure

Here is a list of some significant operations through which we can perform different activities on a stack.

Push: It helps in adding an element to the top of a stack
Pop: It helps in removing one element at a time from the top of a stack
IsEmpty: It helps in checking whether the stack is empty or not
IsFull: It helps in checking whether the stack is full or not
Peek: It helps in fetching the top element value without removing it

How does the Stack Data Structure Work?

You can assume the stack data structure as a pile of books, and you can only put or remove books from the top of it. Here is an algorithmic approach to understanding the working of a stack data structure.

The first thing is to understand the "TOP" pointer that keeps track of the top element of the stack data structure.
While creating the stack for the first time, we set the top value to “1”, which helps check whether the stack is empty. We check whether TOP == -1. If yes, we set the "empty" flag to True.
As we push an element, we have to increase the value of the TOP and point the TOP to the place where the new element gets inserted.
As we pop an element from the stack, we return our pointer to the location where it has an element.
Before pushing an element into the stack, we check if the stack is already full.
Before popping an element into the stack, we check whether the stack is already empty or not.

What is Overflow and Underflow Situation?

These are two situations in a stack data structure that occur as an error handling mechanism to mark the two extreme scenarios.

Stack underflow: This situation occurs when an item is called or popped from the stack, but the stack is empty. Therefore, while popping an existing element, we check whether the TOP position is in -1 or not.
Stack overflow: This situation occurs when programmers want to push a new element to the stack, but the stack is always at its maximum potential; that is, the stack is full. Thus, while pushing a new element, we check whether the TOP is equal to the SIZE of the stack.

Algorithm for Push operation

First, check if your stack is full.
In case your stack is full or all the element completes it, stop the program from pushing a new element into it.
If not, increment the top by one location.
Insert the new element to the point where the top is pointing.

Algorithm for Pop operation

First, check if your stack is empty or not.
If the stack is empty, i.e., there is no element in the stack, we cannot perform the pop operation.
If not, look for the topmost element from the stack and remove it.
Then, decrement the top by one and done.

Implementing Stack using C

Here is a simple code snippet to show how the stack data structure works and how to perform its basic operations.

#include <stdio.h>

#include <stdlib.h>

#define MAX 10

int count = 0;

/* We will create a stack */

struct stack_ds {

int items[MAX];

int top;

};

typedef struct stack_ds sds;

void createEmptyStack(sds *stk) {

stk->top = -1;

}

/* Checking whether the stack is full or not */

int isfull(sds *stk) {

if (stk -> top == MAX - 1)

return 1;

else

return 0;

}

/* Checking whether the stack is empty or not */

int isempty(sds *stk) {

if (stk -> top == -1)

return 1;

else

return 0;

}

// Add elements into stack

void push(sds *stk, int newitem) {

if (isfull(stk)) {

printf("STACK IS FULL");

} else {

stk -> top++;

stk -> items[stk -> top] = newitem;

}

count++;

}

// Remove an element from stack

void pop(sds *stk) {

if (isempty(stk)) {

printf("\n STACK IS EMPTY \n");

} else {

printf(" Item popped = %d", stk -> items[stk -> top]);

stk -> top--;

}

count--;

printf("\n");

}

// Print elements of stack

void printStack(sds *stk) {

printf("Stack: ");

for (int i = 0; i < count; i++) {

printf("%d ", stk -> items[i]);

}

printf("\n");

}

// Driver code

int main() {

int ch;

sds *stk = (sds *)malloc(sizeof(sds));

createEmptyStack(stk);

push(stk, 1);

push(stk, 2);

push(stk, 3);

push(stk, 4);

printStack(stk);

pop(stk);

printf("\n After popping element.... \n");

printStack(stk);

}

Output:

What are the Various Ways we can Implement a Stack?

There are various ways we can implement a stack using two common data structures:

Array: While implementing the stack using an array, we must implement the homogenous data structure array. We can perform all the stack operations using this linear data structure. In an array, the top of the stack remains on the right side of the array. Here, all the insertion and deletion take place.
Linked List: A linked list is a sequence data structure connected through links, one after another, using pointers. Each node contains an item or data element along with one (pointing to the next node) or two (pointing to its next and previous node) pointers. We can perform the stack implementation of data structure using a Linked list.

Application of Stack Data Structure

There are various applications of stack data structure. Some of them are:

Undo and Redo operation: The undo (Ctrl+Z) and Redo (Ctrl+Y) operations we perform in almost all the applications leverage the stack data structure. It arranges the tasks in a stacked order. If anything gets wrong and we press Ctrl+Z, it pops that task from that stack. Again, if we want to bring it back, we use Ctrl+Y to push it back to the stack.
Expression evaluation or expression conversion: Another well-known use case of the stack data structure is when we evaluate or convert expressions like prefix, infix, or postfix.
1. 1. 1. In prefix expression, the operator is followed by two prefix strings. For example: +XY or + + G K - P Q
    2. In an infix expression, the operator remains surrounded by a single infix string on both sides. For example: X+Y or (G + K ) + (P - Q)
    3. In a postfix expression, the operator is preceded by two postfix strings in a postfix expression. For example: XY+ or G K + P Q - +
Backtracking: It is a recursive technique and algorithm that helps solve optimisation problems. N-queen problem and recursive function use the stack to perform backtracking.
Parenthesis checking: If you have seen your compiler or interpreter popping with a parenthesis missing compile-time error, it's the stack that helps in checking. The compiler or interpreter uses the stack for pairing and inspecting whether you have closed all the opened parentheses.
Syntax parsing and memory management: Compiler and interpreter designers also prefer stack data structure to perform various parsing of programming tokens and manage memory allocation, deallocation, and other management using the stack data structure.

Conclusion

We hope this article has given a complete idea of the stack data structure. To learn about other data structures and how to manage large data development projects, get certified through our Data Science Certification Program & boost your career with a 100 % job guarantee. Learn from experts having 15+ years of experience with multiple case studies, simulated projects, & assignments.

Share the blog