Stack – Introduction, Explanation and Implementation

A stack is a data structure used to store items that has defined way of Insertion and Deletion operation. It follows Last in First Out(LIFO) means items inserted last will be removed first.

A very common example of this is a Pile of Plates(or stack of plates). In this plates are arranged one above the other(as shown above) and people take a plate from the top one by one. We might have seen this many times at various places such as in a Buffet or in a Mess.
Following two operations are mainly carried on a stack:

• Push – It refers to inserting an item in the stack. Insertion is always done at the top of stack.
• Pop – It refers to removing an item from the stack. Item currently at the top is removed from the stack.

See the following two pictures. At the left,Item 10 is pushed on the top of the stack and at the right shown item 10 is popped. After 10 if any further pop operation is carried then it’ll be item 20.

Implementation

For implementing Stack there are two possible ways-

1. Using Array
2. Using Linked list

Note:-
If the stack is empty and pop operation is applied which is not possible then it is called Stack Underflow (like buffer underflow).
If the stack is full and push operation is applied which is not possible then it is called Stack Overflow (like buffer overflow).

1. Using Array

Under this, an array is defined and items are pushed to and popped from this array. Since an array is a static data structure, such a stack will be bounded by a fixed number of max allowed items. We can use dynamic array but, then the stack will no longer be persistent.

Implementation of Stack in C Using Array

In the following program array of size of 5 is declared i.e. Max 5 items can be stored in the stack. Pushing more than five items result in Stack Overflow.

#include<stdio.h>
#define MAX 5

int top = 0; //keep track of index of top of stack

int stack[MAX];

void push(int item){

	if(top == MAX){
		printf("Stack Overflow\n");
	return ;
	}

	stack[top] = item;
	top++;
	printf("Item %d pushed\n", item);	
	}

void pop(){

	if(top == 0){
		printf("Stack Underflow\n");
		return ;
		}
		
	printf("Item %d popped\n", stack[top-1]);
	top--;
	
	}	
int main(void){

/* Inserting the Item */
	push(1);
	push(2);
	push(3);

/* deleting the Item */

	pop();
	pop();
	pop();

	pop(); // will cause stack underflow
	return 0;
	}

Output:-

Item 1 pushed
Item 2 pushed
Item 3 pushed
Item 3 popped
Item 2 popped
Item 1 popped
Stack Underflow

Note:-
There is another drawback of using array also,

2.Using Linked list

While implementing Stack using linked list, a linked list is defined and items are pushed to and popped from the start of the linked list. Using Linked list implementation we can create Stack of the desirable size which is bounded in array implementation, this also removes Stack Overflow problem until the memory is full. That’s the advantage of using linked list over an array.

Implementation of Stack in C Linked List

#include<stdio.h>
#include<stdlib.h>

typedef struct node{
	int data;
	struct node *next;
	}Node;

Node *head = NULL;

/* no stack overflow situation */
void push(int item){

	Node *list = head;
	Node *temp = (Node*)malloc(sizeof(Node));

	temp->data = item;
	temp->next = NULL;

	if(!list)
		head = temp;
	else{
		temp->next = list;
		head = temp;
		}

	printf("Item %d pushed\n", temp->data);

	}

void pop(){
	
	Node *list = head;

	if(!list){
		printf("Stack underflow\n");
		return ;
	}

	Node *temp = list;
	head = list->next;
	printf("Item %d popped\n", temp->data);

	free(temp);
	}
	
int main(void){
	/* Inserting the item  */
	push(1);
	push(2);
	push(3);

	/* Deleting the item */
	pop();
	pop();
	pop();

	pop(); // will cause stack underflow

	return 0;
	}

Output:-

Item 1 pushed
Item 2 pushed
Item 3 pushed
Item 3 popped
Item 2 popped
Item 1 popped
Stack Underflow

Uses of stack in computer science:

• Undo action in any word processor
• Tree and Graph traversal
• Browsing pages
• Parsing (matching parenthesis, tags etc.)
• Infix to postfix conversion
• Implementing the recursion
• Function and corresponding variables in a program loaded in a stack way(leaving static/global variable).

Thus we can see stack is widely used.
Knowledge is most useful when liberated and shared. Share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.
Keep Learning… Happy Learning.. 🙂

Recommended -