Abu Zar Mishwani
In this article, we will explore the concept of stacks, their uses, and the various operations and implementations in C++, Java, Python, C, and C# associated with them.
What is Stack Data Structure?
A Stack Data Structure is a type of linear data structure that follows the Last In First Out (LIFO) principle. This means that when an element is added to the stack, it will be placed at the top of the stack, and when an element is removed from the stack, the element at the top of the stack will be the one that will be removed.
For example, consider a stack (pile) of plates in a cafeteria.
Plates are placed on top of each other, with the most recently added plate at the top. To add a new plate, you simply put it on top of the existing stack. To remove a plate, take the one at the top of the stack. This follows the Last In First Out (LIFO) principle of a stack data structure.
In other words, the plates are removed in the reverse order in which they were added.
Basic Operations of Stack Data Structure
The basic operations include the following:
- Push(): The Push operation is one of the most important operations of stack data structure. It is used to insert a new element at the top of the stack. The new element is added to the stack, and the size of the stack increases by one.
- Pop(): The Pop operation is used to remove an element from the top of the stack. It removes the topmost element and reduces the size of the stack by one.
- IsEmpty(): The IsEmpty operation is used to determine whether the stack is empty or not. It returns a boolean value, true if the stack is empty,
falseotherwise.
- IsFull(): The IsFull operation is used to determine whether the stack is full or not. It returns a boolean value, true if the stack is full,
falseotherwise.
- Peek(): The Peek operation is used to examine the topmost element of the stack without removing it. It returns the value of the topmost element without popping it from the stack.
These operations are essential for working with the Stack data structure and hence must be understood clearly.
Understanding Stack Data Structure With Example Animation
An animated illustration of a stack data structure:
The Last In First Out (LIFO) Principle works such that the last element added is the first one to be removed, as demonstrated in the above animation, where element 6 was the last to be added but the first to be removed.
How Does The Stack Data Structure Work?
It works using a pointer to keep track of the top element of the stack. The pointer is initialized to the base of the stack when the stack is created.
Before adding an element to the stack, you need to check if the stack is already full.
To add an element to the stack, the pointer is incremented by 1, and the new element is stored at the new location pointed to by the pointer.
To remove an element from the stack, the pointer is decremented by one, i.e., -1, and the element at the new location pointed to by the pointer is removed from the stack.
When an element is removed from the stack, the pointer is decremented by 1, and the element at the new location pointed to by the pointer is removed from the stack. This process is repeated until the pointer reaches the base of the stack.
When the stack is empty, the pointer is reset back to the base of the stack.
This is a simple and efficient way to store and retrieve elements in a specific order. It can be used in a variety of applications, such as memory management, process scheduling, and more.
Implementation of Stack Data Structure in C++, Java, Python, C, and C#
A stack is typically implemented using an array, STL Library, or a linked list. In an array, the last element added to the stack is stored at the highest index. In a linked list, the most recently added node is made the head of the list.
In either case, elements are added and removed from the stack using two operations: push and pop. Push adds an element to the top of the stack, and pop removes the element from the top of the stack. All elements underneath the top element remain in the stack.
//Stack Implementation in C++ using Array
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main() {
int n;
cout << "Enter the number of elements to be added to the stack: ";
cin >> n;
int arr[n]; // Create an array to store the elements
cout<<endl;
cout << "Please add (push) data in the stack: " << endl;
for (int i = 0; i < n; i++) {
int x;
if (!(cin >> x)) { // Check if the user inputs any other type of data other than an integer
cout << endl;
cout << "Error: Please enter an integer!" << endl;
return 0;
}
arr[i] = x; // Push the elements to the array
}
cout << "\nItem Pushed Successfully: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " "; // Print the elements from the array
}
cout << endl;
cout << "\nTop Element = " << arr[n-1] << endl; // Print the top element of the array
int remove_element;
cout << "\nEnter the element you want to remove (Pop): ";
cin >> remove_element;
// Check if the element exists in the array
bool element_exist = false;
for (int i = 0; i < n; i++) {
if (arr[i] == remove_element) { // Check if the element of the array is equal to the element to be removed
element_exist = true;
break;
}
}
if (!element_exist) { // If the element does not exist in the array
cout<<endl;
cout << "Error: the element you want to remove is not present in the stack!" << endl;
} else if (n == 0 || arr[n-1] != remove_element) { // If the array is empty or the top element is not equal to the element to be removed
cout<<endl;
cout << "Error: the element you want to pop is not the top element!" << endl;
} else {
n--; // Pop the top element of the array
cout<<endl;
cout << "Item Popped Successfully!" << endl;
cout << "Array After Popping: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " "; // Print the elementI of the array
}
cout << endl;
if (n > 0) {
cout << "\nNew Top Element = " << arr[n-1] << endl; // Print the new top element of the array
}
}
return 0;
}
//Stack Implementation in Java using Array
import java.util.Scanner;
public class StackArray {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print("Enter the number of elements to be added to the stack: ");
int n = input.nextInt();
int[] arr = new int[n]; // Create an array to store the elements
System.out.println();
System.out.println("Please add (push) data in the stack: ");
for (int i = 0; i < n; i++) {
int x;
if (!input.hasNextInt()) { // Check if the user inputs any other type of data other than an integer
System.out.println();
System.out.println("Error: Please enter an integer!");
return;
}
x = input.nextInt();
arr[i] = x; // Push the elements to the array
}
System.out.println("\nItem Pushed Successfully: ");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " "); // Print the elements from the array
}
System.out.println();
System.out.println("\nTop Element = " + arr[n-1]); // Print the top element of the array
System.out.print("\nEnter the element you want to remove (Pop): ");
int remove_element = input.nextInt();
// Check if the element exists in the array
boolean element_exist = false;
for (int i = 0; i < n; i++) {
if (arr[i] == remove_element) { // Check if the element of the array is equal to the element to be removed
element_exist = true;
break;
}
}
if (!element_exist) { // If the element does not exist in the array
System.out.println();
System.out.println("Error: the element you want to remove is not present in the stack!");
} else if (n == 0 || arr[n-1] != remove_element) { // If the array is empty or the top element is not equal to the element to be removed
System.out.println();
System.out.println("Error: the element you want to pop is not the top element!");
} else {
n--; // Pop the top element of the array
System.out.println();
System.out.println("Item Popped Successfully!");
System.out.print("Array After Popping: ");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " "); // Print the elements from the array
}
System.out.println();
if (n > 0) {
System.out.println("\nNew Top Element = " + arr[n-1]); // Print the new top element of the array
}
}
}
}
//Stack Implementation in C# using Array
using System;
namespace Stack_Implementation
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Enter the number of elements to be added to the stack: ");
int n = int.Parse(Console.ReadLine());
int[] arr = new int[n];
Console.WriteLine("\nPlease add (push) data in the stack: ");
for (int i = 0; i < n; i++)
{
int x;
if (!int.TryParse(Console.ReadLine(), out x))
{ // Check if the user inputs any other type of data other than an integer
Console.WriteLine("\nError: Please enter an integer!");
return;
}
arr[i] = x; // Push the elements to the array
}
Console.WriteLine("\nItem Pushed Successfully: ");
foreach (int i in arr)
{
Console.Write(i + " "); // Print the elements from the array
}
Console.WriteLine("\n\nTop Element = " + arr[n - 1]); // Print the top element of the array
Console.WriteLine("\nEnter the element you want to remove (Pop): ");
int remove_element = int.Parse(Console.ReadLine());
// Check if the element exists in the array
bool element_exist = false;
foreach (int i in arr)
{
if (i == remove_element)
{ // Check if the element of the array is equal to the element to be removed
element_exist = true;
break;
}
}
if (!element_exist)
{ // If the element does not exist in the array
Console.WriteLine("\nError: the element you want to remove is not present in the stack!");
}
else if (n == 0 || arr[n - 1] != remove_element)
{ // If the array is empty or the top element is not equal to the element to be removed
Console.WriteLine("\nError: the element you want to pop is not the top element!");
}
else
{
n--; // Pop the top element of the array
Console.WriteLine("\nItem Popped Successfully!");
Console.WriteLine("Array After Popping: ");
for (int i = 0; i < n; i++)
{
Console.Write(arr[i] + " "); // Print the elementI of the array
}
Console.WriteLine();
if (n > 0)
{
Console.WriteLine("\nNew Top Element = " + arr[n - 1]); // Print the new top element of the array
}
}
}
}
}
# Stack Implementation in Python using Array
def main():
n = int(input("Enter the number of elements to be added to the stack: "))
arr = [0] * n # Create an array to store the elements
print("\nPlease add (push) data in the stack: ")
for i in range(n):
try:
x = int(input()) # Try to input integer
except ValueError:
print("\nError: Please enter an integer!") # Handle the case when input is not an integer
return
arr[i] = x # Push the elements to the array
print("\nItem Pushed Successfully: ", end="")
print(*arr) # Print the elements from the array
print("\nTop Element = ", arr[-1]) # Print the top element of the array
remove_element = int(input("\nEnter the element you want to remove (Pop): "))
# Check if the element exists in the array
if remove_element not in arr: # If the element does not exist in the array
print("\nError: the element you want to remove is not present in the stack!")
elif arr[-1] != remove_element: # If the top element is not equal to the element to be removed
print("\nError: the element you want to pop is not the top element!")
else:
arr.pop() # Pop the top element of the array
print("\nItem Popped Successfully!")
print("Stack After Popping: ", end="")
print(*arr) # Print the elements of the array
if len(arr) > 0:
print("\nNew Top Element = ", arr[-1]) # Print the new top element of the array
if __name__ == "__main__":
main()
//Stack Implementation in C using Array
#include<stdio.h>
#include<stdlib.h>
int main()
{
int n;
printf("\nEnter the number of elements to be added to the stack: ");
scanf("%d", &n);
int arr[n]; // Create an array to store the elements
printf("\nPlease add (push) data in the stack: ");
for (int i = 0; i < n; i++) {
int x;
if (!(scanf("%d", &x))) { // Check if the user inputs any other type of data other than an integer
printf("\nError: Please enter an integer!");
return 0;
}
arr[i] = x; // Push the elements to the array
}
printf("\nItem Pushed Successfully: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]); // Print the elements from the array
}
printf("\n\nTop Element = %d\n", arr[n-1]); // Print the top element of the array
int remove_element;
printf("\nEnter the element you want to remove (Pop): ");
scanf("%d", &remove_element);
// Check if the element exists in the array
int element_exist = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == remove_element) { // Check if the element of the array is equal to the element to be removed
element_exist = 1;
break;
}
}
if (element_exist == 0) { // If the element does not exist in the array
printf("\nError: the element you want to remove is not present in the stack!");
} else if (n == 0 || arr[n-1] != remove_element) { // If the array is empty or the top element is not equal to the element to be removed
printf("\nError: the element you want to pop is not the top element!");
} else {
n--; // Pop the top element of the array
printf("\nItem Popped Successfully!\n");
printf("Array After Popping: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]); // Print the elementI of the array
}
printf("\n");
if (n > 0) {
printf("\nNew Top Element = %d\n", arr[n-1]); // Print the new top element of the array
}
}
return 0;
}
Time Complexity of Stack Data Structure
The time complexity of stack data structure operations depends on the implementation.
For example, the time complexity of push(), pop(), and peek() operations is typically O(1) if implemented using an array but can be O(n) if implemented using a linked list.
This is because stacks are based on a last-in-first-out (LIFO) principle, which means the most recently added element is always the first to be removed. Other operations, such as searching for an element in the stack, may have higher time complexity, such as O(n).
Applications of Stack Data Structure
Stack Data Structure is a linear data structure with only one end open for inserting and deleting elements. Some of the most popular applications of the stack data structure are:
1. Undo function in text editors: Stack data structure can be used to create an undo function in text editors where users can go back and forth to their previous changes.
2. Expression evaluation: Stacks can evaluate arithmetic expressions like postfixes, prefixes, or infixes.
3. Function parameters: Stacks can store the parameters used in a function call.
4. Recursive calls: Stack data structure can also be used to make recursive calls in programming languages.
5. Browser history: A stack data structure can also be used to store the browser history when moving from one page to another.
6. Balancing of symbols: Stacks can be used to check whether the symbols in a given expression are balanced.
7. Memory management: Stacks can also be used for dynamic memory allocation and deallocation.
8. Garbage collection: Stacks can be used for garbage collection in programming languages.
9. Tower of Hanoi: The Tower of Hanoi is a classic example of a problem that can be solved using stacks.
10. Maze Solving: Stacks are used in maze-solving algorithms such as depth-first search. The sequence of visited cells is stored in a stack.