Stack Data Structure in C++ Programming (using arrays) | All Stack Operations | Part - 2

Introduction

This tutorial provides a comprehensive guide to implementing a stack data structure using arrays in C++. You will learn about the standard operations associated with stacks, such as pushing and popping items, checking if the stack is full or empty, and more. Understanding stack operations is essential for managing data in programming effectively.

Step 1: Setting Up the Stack

To begin, you need to set up a stack using an array. Here’s how to do it:

1. Define the Stack Structure: Create a structure that holds the stack data, its maximum size, and the current top index.

   #define MAX 100
   
   struct Stack {
       int arr[MAX];
       int top;
   };
   

2. Initialize the Stack: Create a function to initialize the stack.

   void initStack(Stack &s) {
       s.top = -1; // Indicates that the stack is empty
   }
   

Step 2: Implementing Push Operation

The push() operation adds an item to the top of the stack.

1. Check for Overflow: Before adding an item, ensure the stack is not full.

   bool isFull(Stack &s) {
       return s.top == MAX - 1;
   }
   

2. Add Item: If the stack is not full, increment the top index and add the item.

   void push(Stack &s, int item) {
       if (isFull(s)) {
           cout << "Stack Overflow" << endl;
           return;
       }
       s.arr[++s.top] = item;
   }
   

Step 3: Implementing Pop Operation

The pop() operation removes the item from the top of the stack.

1. Check for Underflow: Ensure the stack is not empty before popping.

   bool isEmpty(Stack &s) {
       return s.top == -1;
   }
   

2. Remove Item: If the stack is not empty, return the item at the top and decrement the top index.

   int pop(Stack &s) {
       if (isEmpty(s)) {
           cout << "Stack Underflow" << endl;
           return -1; // Return an error code
       }
       return s.arr[s.top--];
   }
   

Step 4: Additional Stack Operations

Beyond push and pop, implement the following operations:

1. Peek: Access the item at the top of the stack without removing it.

   int peek(Stack &s) {
       if (isEmpty(s)) {
           cout << "Stack is empty" << endl;
           return -1; // Return an error code
       }
       return s.arr[s.top];
   }
   

2. Count Items: Get the number of items currently in the stack.

   int count(Stack &s) {
       return s.top + 1; // Since top is zero-based
   }
   

3. Change Item: Modify an item at a specific position.

   void change(Stack &s, int index, int newValue) {
       if (index < 0 || index > s.top) {
           cout << "Invalid index" << endl;
           return;
       }
       s.arr[index] = newValue;
   }
   

4. Display Stack: Show all items in the stack.

   void display(Stack &s) {
       if (isEmpty(s)) {
           cout << "Stack is empty" << endl;
           return;
       }
       for (int i = s.top; i >= 0; i--) {
           cout << s.arr[i] << " ";
       }
       cout << endl;
   }
   

Conclusion

You have now implemented a stack data structure in C++ using arrays, along with all standard operations. The stack is a fundamental data structure that can be applied in various programming scenarios, such as expression evaluation and backtracking algorithms.

To further explore stacks, consider experimenting with linked lists for stack implementation or exploring how stacks are used in recursion.