Stack in C/C++ – Master the LIFO Concepts in Less Than 4 Mins.

After getting well-versed with linked lists and arrays in C/C++, you are now ready to explore a new concept, that is stack in C/C++. Both stacks and queues are data structures that can be implemented using either arrays or linked lists.

Newbies to programming often find it cumbersome to implement stacks as it requires a thorough knowledge of all the concepts of in C and C++ that we have covered so far. So, we will understand each and every important concept involved in a stack in C/C++ in detail so that you would develop a clear understanding of the topic.

If we want to learn this concept then we have to go deep inside it. That’s why we are going to discuss its key topics, which will be helping us to grasp the concept in an efficient way. So let’s start.

1. Stack in C/C++

A stack is nothing but a linear data structure that follows the LIFO rule (Last In First Out). In a stack, both insertion and deletion take place from just one end, that is, from the top.

Stack in C and C++

In order to better understand it, consider the following scenario: Imagine you have 5 plates that you have to keep on top of each other of distinct colors: Red, Green, Blue, White, and Orange.

You start by placing the red plate on the table. This is the first element of the stack. Then, you place the green plate on top of the red plate. This is the second element of the stack. Similarly, you place the blue plate followed by white and then finally orange. Note that the first plate you inserted into the stack was the red one. Now, you want to remove the red plate. But, before that, you need to remove the rest of the plates that are on top of the red one.

Variables in C and C++ A Complete Guide for Beginners

From this discussion, it is pretty obvious that the first plate (first data element) to be inserted is removed at the last. And, the last plate to be inserted is removed at first, that is, it follows the “Last In First Out” rule. Also, we infer that placing and removing the plate is done from the top, that is, insertion and deletion are done from the top

Insertion and Deletion of Element in C Stack

We can implement a stack in C and C++ in 2 ways:

  1. Statically: Array implementation of stacks allows the static memory allocation of its data elements. It is important to note that in this method, the stack acquires all the features of an array.
  2. Dynamically: Linked list implementation of stacks follow the dynamic memory allocation of its data elements. It is important to note that in this method, the stack inherits all the characteristics of a linked list in C/C++.

2. Array Implementation of Stack in C and C++

As we already discussed, arrays support the static memory allocation of the data elements of the stack. Therefore, it is important to determine the size of the stack prior to the program run.

The stack functions basically include:

2.1 Insertion

In a stack, the operation of inserting an element into the stack is referred to as pushing an element in the stack. The elements are inserted into the stack from the top and hence would compel the elements to shift.

Enhance your Fundamental Skills with Different types of Operators in C/C++

Here is a diagrammatic representation of how elements are pushed into a stack:

Insertion in C Stack

Insert elements into a stack in C
#define LIMIT 100
void push()
{
int stack[LIMIT], top, element;
if(top == LIMIT- 1)
{
printf("Stack Overflow\n");
}
else
{
printf("Enter the element to be inserted:");
scanf("%d", &element);
top++;
stack[top]=element;
}
}
Insert elements into a stack in C++
#define LIMIT 100
void push()
{
int stack[LIMIT], top, element;
if(top == LIMIT- 1)
{
cout<<"Stack overflow"<<endl;
}
else
{
cout<<"Enter the element to be inserted:"<<endl;
cin>>element;
top++;
stack[top]=element;
}
}

2.2 Deletion

In a stack, the operation of deleting an element into the stack is referred to as popping an element in the stack. The deletion of a data element from the stack is done from the top.

Here is a diagrammatic representation of how elements are pushed into a stack:

Deletion in Stack in C

Delete an element from a stack in C
#define LIMIT 100
void pop()
{
int stack[LIMIT], top, element;
if(top == -1)
{
printf("Stack underflow\n");
}
else
{
element=stack[top];
printf("The deleted item is %d\n",stack[top]);
top--; // The element below the topmost element is deleted
}
}
Delete an element from a stack in C++
#define LIMIT 100
void pop()
{
int stack[LIMIT], top, element;
if(top == -1)
{
cout<<"Stack underflow”<<endl;
}
else
{
element=stack[top];
cout<<"The deleted item is: "<< stack[top];
top--; // The element below the topmost element is deleted
}
}

2.3 Display

The stack data elements are displayed in the stack according to the LIFO rule.

Display a stack in C
#define LIMIT 100
void display()
{
int stack[LIMIT], top, i;
if(top == -1)
{
printf("Stack underflow\n"); // Stack is empty
}
else if(top > 0)
{
printf("The elements of the stack are:\n");
for(i = top; i >= 0; i--) // top to bottom traversal
{
printf("%d\n",stack[i]);
}
}
}
Display a stack in C++
#define LIMIT 100	
void display()
{
int stack[LIMIT], top, i;
if(top == -1)
{
cout<<"Stack underflow”<<endl;; // Stack is empty
}
else if(top > 0)
{
cout<<"The elements of the stack are:”<<endl;
for(i = top; i >= 0; i--) // top to bottom traversal
{
cout<<stack[i];
}
}
}

Apart from these 3 main functions, it is necessary to check the overflow and underflow conditions to avoid unfavorable situations.

2.4 Stack Overflow

Here we are talking about the static memory allocation of data elements of a stack. Therefore, if the stack is filled completely, that is, no more elements can be inserted in the stack, then the condition would be called STACK-FULL condition. It is also referred to as stack overflow.

2.5 Stack Underflow

In case we wish to display the data elements of the stack or perform the deletion operation, but no elements have been inserted into the stack yet, this condition is called STACK-EMPTY. It is also referred to as stack underflow.

Before discussing the example, let’s revise the concept of Variables in C

Example of Array Implementation of Stack in C

Here is a program in C that illustrates the array implementation of stacks:

#include <stdio.h>
#include <stdlib.h>
#define LIMIT 100 // Specifying the maximum limit of the stack

/* Global declaration of variables */

int stack[LIMIT]; // Array implementation of stack
int top; // To insert and delete the data elements in the stack
int i; // To traverse the loop to while displaying the stack
int choice; // To choose either of the 3 stack operations

void push(); // Function used to insert the element into the stack
void pop(); // Function used to delete the element from the stack
void display(); // Function used to display all the elements in the stack according to LIFO rule

int main()
{

printf("Welcome to DataFlair tutorials!\n\n");

printf ("ARRAY IMPLEMENTATION USING STACKS\n\n");
top = -1; // Initializing top to -1 indicates that it is empty
do
{

printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n\n");
printf("Enter your choice:");
scanf("%d",&choice);

switch(choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, invalid choice!\n");
break;
}
} while(choice!=4);
return 0;
}

void push()
{
int element;
if(top == LIMIT- 1)
{
printf("Stack underflow\n");
}
else
{
printf("Enter the element to be inserted:");
scanf("%d", &element);
top++;
stack[top]=element;
}
}

void pop()
{
int element;
if(top == -1)
{
printf("Stack underflow\n");
}
else
{
element=stack[top];
printf("The deleted item is %d\n",stack[top]);
top--; // The element below the topmost element is deleted
}
}

void display()
{
if(top == -1)
{
printf("Stack underflow\n"); // Stack is empty
}
else if(top > 0)
{
printf("The elements of the stack are:\n");
for(i = top; i >= 0; i--) // top to bottom traversal
{
printf("%d\n",stack[i]);
}
}
}

Output-

Output of array implementation of stacks in C

Implementation of stacks in C with Output

Example of Array Implementation of Stack in C++

#include <iostream>
#include <stdlib.h> 
#define LIMIT 100 // Specifying the maximum limit of the stack
using namespace std;
 
/* Global declaration of variables */

int stack[LIMIT]; // Array implementation of stack
int top; // To insert and delete the data elements in the stack
int i; // To traverse the loop to while displaying the stack
int choice; // To choose either of the 3 stack operations

void push(); // Function used to insert the element into the stack
void pop(); // Function used to delete the element from the stack
void display(); // Function used to display all the elements in the stack according to LIFO rule
 
int main()
{

cout<<"Welcome to DataFlair tutorials!"<<endl<<endl;

cout<< "ARRAY IMPLEMENTATION USING STACKS"<<endl<<endl;
top = -1; // Initializing top to -1 indicates that it is empty
do
{

cout<<"1. Insert\n2. Delete\n3. Display\n4. Exit\n\n";
cout<<"Enter your choice:";
cin>>choice;
 
switch(choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, invalid choice!\n");
break;
}
} while(choice!=4);
return 0; 
}

void push()
{
int element;
if(top == LIMIT- 1)
{
cout<<"Stack underflow\n";
}
else
{
cout<<"Enter the element to be inserted:";
cin>>element;
top++;
stack[top]=element;
}
}

void pop()
{
int element;
if(top == -1)
{
cout<<"Stack underflow\n";
}
else
{
element=stack[top];
cout<<"The deleted item is "<< stack[top] <<endl;
top--; // The element below the topmost element is deleted
}
}

void display()
{
if(top == -1)
{
cout<<"Stack underflow\n"; // Stack is empty
}
else if(top > 0)
{
cout<<"The elements of the stack are:\n";
for(i = top; i >= 0; i--) // top to bottom traversal
{
cout<< stack[i] <<endl;
}
}
}

Output-

Output of Array Implementation of Stacks in C++

Array Implementation of Stacks in C++

3. Linked List Implementation of Stack in C/C++

As we already discussed, linked lists support the dynamic memory allocation of the data elements of the stack. Therefore, the size of the stack is allocated during the program run and needn’t be specified beforehand.

The 3 basic operations of Insertion, Deletion, and Display follow a similar trend as we saw in the array implementation of stacks.

Functions in C – An Important Concept for beginners

The stack functions basically include:

3.1 Insertion

Insert an element into the stack in C
void push ()
{
int data;
struct node *pointer = (struct node*)malloc(sizeof(struct node));
if(pointer == NULL)
{
printf("Stack overflow");
}
else
{
printf("Enter the element to be inserted: ");
scanf("%d",&data);
if(temp == NULL)
{
pointer -> data = data;
pointer -> next = NULL;
temp = pointer;
}
else
{
pointer -> data = data;
pointer -> next = temp;
temp = pointer;
}
}
}
Insert an element into the stack in C++

Here we have used classes to implement linked lists in C++

// Structure definition
struct node
{
int data;
node *next;
};
// Class definition
class Stack
{
node *top;
public :
Stack()
{
top = NULL;
}
void push();
};
// Member function definition
void Stack::push()
{
node *temp;
temp = new node;
cout<<"Enter the element to be inserted: ";
cin>> temp -> data;
temp -> next = top;
top = temp;
}

3.2 Deletion

Delete an element into the stack in C

This is how we can delete elements from a stack in C:

void pop()
{
int item;
struct node *pointer;
if (temp == NULL)
{
printf("Stack Underflow\n");
}
else
{
item = temp -> data;
pointer = temp;
temp = temp -> next;
free(pointer);
printf("The deleted item is %d\n",item);
}
}
Delete an element into the stack in C++
// Structure definition
struct node
{
int data;
node *next;
};
// Class definition
class Stack
{
node *top;
public :
Stack()
{
top = NULL;
}
void pop();
};
// Member function definition
void Stack::pop()
{
if(top != NULL)
{
node *temp = top;
top = top -> next;
cout<< “The deleted element is: ” << temp -> data <<endl;
delete temp;
}
else
cout<<"Stack underflow"<<endl;
}

3.3 Display

Display a Stack in C

This is how we display the elements of a stack:

void display()
{
int i;
struct node *pointer;
pointer = temp;
if(pointer == NULL)
{
printf("Stack underflow\n");
}
else
{
printf("The elements of the stack are:\n");
while(pointer!= NULL)
{
printf("%d\n",pointer -> data);
pointer = pointer -> next;
}
}
}
Display a Stack in C
// Structure definition
struct node
{
int data;
node *next;
};
// Class definition
class Stack
{
node *top;
public :
Stack()
{
top = NULL;
}
void display();
};
// Member function definition
void Stack::display()
{
node *temp = top;
while(temp != NULL)
{
cout<< temp -> data <<"  ";
temp = temp -> next;
}
}

Example of Linked List Implementation of Stack in C

Here is a code in C that illustrates the linked list implementation of arrays:

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

void push(); // Function used to insert the element into the stack
void pop(); // Function used to delete the elememt from the stack
void display(); // Function used to display all the elements in the stack according to LIFO rule

struct node
{
int data;
struct node *next;
};
struct node *temp;

int main()
{

printf("Welcome to DataFlair tutorials!\n\n");

int choice;
printf ("LINKED LIST IMPLEMENTATION USING STACKS\n\n");
do
{

printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n\n");
printf("Enter your choice:");
scanf("%d",&choice);

switch(choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, invalid choice!\n");
break;
}
} while(choice!=4);
return 0;
}

void push ()
{
int data;
struct node *pointer = (struct node*)malloc(sizeof(struct node));
if(pointer == NULL)
{
printf("Stack overflow");
}
else
{
printf("Enter the element to be inserted: ");
scanf("%d",&data);
if(temp == NULL)
{
pointer -> data = data;
pointer -> next = NULL;
temp = pointer;
}
else
{
pointer -> data = data;
pointer -> next = temp;
temp = pointer;
}
}
}

void pop()
{
int item;
struct node *pointer;
if (temp == NULL)
{
printf("Stack Underflow\n");
}
else
{
item = temp -> data;
pointer = temp;
temp = temp -> next;
free(pointer);
printf("The deleted item is %d\n",item);
}
}
void display()
{
int i;
struct node *pointer;
pointer = temp;
if(pointer == NULL)
{
printf("Stack underflow\n");
}
else
{
printf("The elements of the stack are:\n");
while(pointer!= NULL)
{
printf("%d\n",pointer -> data);
pointer = pointer -> next;
}
}
}

Output-

Output of linked list implementation of arrays in C

Linked list implementation of arrays in C with Output

Example of Linked List Implementation of Stack in C++

#include<iostream>
using namespace std;

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

class Stack
{
node *top;
public :
Stack()
{
top = NULL;
}
void push(); // Function used to insert the element into the stack
void pop(); // Function used to delete an element from the stack
void display(); // Function used to display all the elements in the stack according to LIFO rule
};

void Stack::push()
{
node *temp;
temp = new node;
cout<<"Enter the element to be inserted: ";
cin>>temp -> data;
temp -> next = top;
top = temp;
}

void Stack::pop()
{
if(top != NULL)
{
node *temp = top;
top = top -> next;
cout<< "The deleted element is: " << temp -> data <<endl;
delete temp;
}
else
cout<<"Stack underflow!";
}

void Stack::display()
{
node *temp = top;
while(temp != NULL)
{
cout<< temp -> data <<endl;
temp = temp -> next;
}
}

int main()
{

cout<<"Welcome to DataFlair tutorials!"<<endl<<endl;
Stack s;
int choice;
cout<<"IMPLEMENTATION OF STACKS USING LINKED LISTS"<<endl<<endl;
do
{

cout<<"1. Insert\n2. Delete\n3. Display\n4. Exit\n\n";
cout<<"Enter your choice: ";
cin>>choice;

switch(choice)
{
case 1:
s.push();
break;
case 2:
s.pop();
break;
case 3:
s.display();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, invalid choice!\n");
break;
}
} while(choice!=4);
return 0;
}

Output-

Linked List Implementation of Stacks in C++ with Output

Linked List Implementation of Stacks in C++

4. Application of Stack in C/C++

The principle LIFO followed by stacks gives birth to the various applications of stacks. Some of the most popular applications of stacks in C/C++ are:

  • Number reversal: A stack helps you reverse a number or a word entered as a sequence of digits or characters respectively.
  • Undo operation: Implementation of a stack helps you perform the “undo” operation in text editors or word processors. Here, all the changes take place are stored in a stack.
  • Infix to postfix conversion: Using stacks, you can perform the conversion of an infix expression to a postfix expression.
  • Backtracking: Stacks finding applications in puzzle or maze problem-solving.
  • Depth-first search (DFS): Stacks allow you to perform a searching algorithm called the depth-first search.

5. Summary

Stacks in C/C++ are the fundamental and important concept for every beginner. It is a linear data structure which will help you to collect elements and perform many operations on it.  We can use stacks to reverse a word/number, infix to postfix conversion, backtracking tec.

Hope you liked our explanation. The concept of Stack is incomplete without queues. In our next article, we will discuss Queues in C/C++.

Leave a Reply

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

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.