Understand Stack and Their Implementation Using Array [06]

1. Introduction

A stack is a fundamental data structure in computer science, essential for managing and organizing data in a specific order. The stack follows a Last In, First Out (LIFO) principle, meaning that the last element added to the stack is the first one to be removed. This behavior is similar to a stack of plates, where the last plate placed on top is the first one to be taken off.

1. Key Characteristics of a Stack:

• LIFO (Last In, First Out): The last element added is always the first one to be removed.
• Push and Pop Operations: Elements are added to (push) or removed from (pop) the top of the stack.
• Limited Access: Only the top element is accessible for viewing or modification, not the other elements beneath it.

2. Visualizing a Stack:

Imagine a stack of books. When you add a new book, it goes on top of the stack. If you want to remove a book, you have to take the top one. The same rule applies in programming with stacks.

3. Applications of Stacks:

Stacks are used in a variety of computer science problems. Here are a few examples:

1. Undo/Redo Functionality: Stacks are used to keep track of changes in applications, enabling users to undo or redo actions.
2. Expression Evaluation: In mathematics and programming, stacks are used to evaluate expressions like postfix or infix.
3. Function Call Management: When functions are called, the system pushes them onto the call stack, and once the function finishes, it is popped off.

2. Stack Operations

Stacks support a few essential operations that allow efficient management of the data. These operations are designed to work according to the LIFO (Last In, First Out) principle.

1. Push: Adding an Element to the Stack

The Push operation adds an element to the top of the stack. If there’s space in the stack (in case of a fixed-size stack), the new element is inserted on top of the current top element.

Pseudocode:

text
1.
Push(stack, element):
2.
    if stack is not full:
3.
        increment top index
4.
        stack[top] = element
5.
    else:
6.
        print "Stack Overflow"

2. Pop: Removing the Top Element

The Pop operation removes the top element from the stack and returns it. After removal, the top pointer is decremented to point to the next element in the stack.

Pseudocode:

text
1.
Pop(stack):
2.
    if stack is not empty:
3.
        element = stack[top]
4.
        decrement top index
5.
        return element
6.
    else:
7.
        print "Stack Underflow"

3. Peek/Top: Viewing the Top Element

The Peek or Top operation allows you to view the top element of the stack without removing it. This is useful when you want to see what the current top element is but do not want to modify the stack.

Pseudocode:

text
1.
Peek(stack):
2.
    if stack is not empty:
3.
        return stack[top]
4.
    else:
5.
        print "Stack is Empty"

4. isEmpty: Checking if the Stack is Empty

The isEmpty operation checks whether the stack is empty. If the top index is -1 (or an equivalent value depending on the implementation), the stack is considered empty.

Pseudocode:

text
1.
isEmpty(stack):
2.
    if top == -1:
3.
        return true
4.
    else:
5.
        return false

5. isFull: Checking if the Stack is Full

The isFull operation checks if the stack has reached its maximum capacity. This is particularly relevant in stack implementations using arrays, where a fixed-size array is used to hold elements.

Pseudocode:

text
1.
isFull(stack):
2.
    if top == maxSize - 1:
3.
        return true
4.
    else:
5.
        return false

These operations form the core functionality of a stack and are crucial for its proper management and utilization in various algorithms and data structures.

3. Advantages and Limitations of Stacks

1. Advantages:

• Simple Data Management: Efficient LIFO structure, with fast operations like push, pop, and peek.
• Memory Efficiency: Low overhead, using memory proportional to the number of elements.
• Versatile Use Cases: Essential in function call management, undo/redo, expression parsing, and data reversal.
• Easy to Implement: Simple to implement with arrays or linked lists, with O(1) time complexity for main operations.

2. Limitations:

• Fixed Size (Array Implementation): Limited capacity, leading to stack overflow if full.
• Limited Element Access: Can only access the top element, requiring pops to access deeper elements.
• Memory Wastage: Fixed-size stacks may waste memory if not fully utilized.
• Limited to LIFO: Not ideal for tasks requiring other access patterns (e.g., FIFO).

4. Implementing a Stack Using Arrays

Here’s a full implementation of a stack using arrays in C++.

1. Define the Stack Class

We start by defining the stack class and initializing it with a maximum size of 3 for the stack.

cpp
1.
#include <iostream>
2.
using namespace std;
3.

4.
#define MAX_SIZE 3  // Limiting the stack size to 3 for simplicity
5.

6.
class Stack {
7.
private:
8.
    int stack[MAX_SIZE];  // Array to store stack elements
9.
    int top;              // Index of the top element
10.

11.
public:
12.
    // Constructor to initialize the stack
13.
    Stack() {
14.
        top = -1;  // Initialize the top index to -1 (indicating the stack is empty)
15.
    }
16.
};

2. Code for the Push Operation

Next, we define the push function that adds an element to the stack. If the stack is full, it prints a "Stack Overflow" message.

cpp
1.
// Push operation: Adds an element to the stack
2.
void push(int element) {
3.
    if (top < MAX_SIZE - 1) {
4.
        top++;
5.
        stack[top] = element;
6.
        cout << "Pushed " << element << " to stack." << endl;
7.
    } else {
8.
        cout << "Stack Overflow" << endl;
9.
    }
10.
}

3. Code for the Pop Operation

The pop function removes the top element from the stack. If the stack is empty, it prints a "Stack Underflow" message.

cpp
1.
// Pop operation: Removes the top element from the stack
2.
int pop() {
3.
    if (top != -1) {
4.
        int element = stack[top];
5.
        top--;
6.
        return element;
7.
    } else {
8.
        cout << "Stack Underflow" << endl;
9.
        return -1;  // Return a sentinel value indicating underflow
10.
    }
11.
}

4. Code for the Peek Operation

The peek function returns the top element without removing it from the stack. If the stack is empty, it prints "Stack is Empty".

cpp
1.
// Peek operation: Views the top element without removing it
2.
int peek() {
3.
    if (top != -1) {
4.
        return stack[top];
5.
    } else {
6.
        cout << "Stack is Empty" << endl;
7.
        return -1;  // Return a sentinel value indicating empty stack
8.
    }
9.
}

5. Code for the isEmpty Operation

The isEmpty function checks whether the stack is empty by verifying if top is -1.

cpp
1.
// isEmpty operation: Checks if the stack is empty
2.
bool isEmpty() {
3.
    return top == -1;
4.
}

6. Code for the isFull Operation

The isFull function checks whether the stack has reached its maximum size.

cpp
1.
// isFull operation: Checks if the stack is full
2.
bool isFull() {
3.
    return top == MAX_SIZE - 1;
4.
}

7. Full Code Implementation

Now, let's combine all the functions together and provide the complete implementation. We'll use a stack with a maximum size of 3 and demonstrate all operations.

cpp
1.
#include <iostream>
2.
using namespace std;
3.

4.
#define MAX_SIZE 3  // Limiting the stack size to 3 for simplicity
5.

6.
class Stack {
7.
private:
8.
    int stack[MAX_SIZE];  // Array to store stack elements
9.
    int top;              // Index of the top element
10.

11.
public:
12.
    // Constructor to initialize the stack
13.
    Stack() {
14.
        top = -1;  // Initialize the top index to -1 (indicating the stack is empty)
15.
    }
16.

17.
    // Push operation: Adds an element to the stack
18.
    void push(int element) {
19.
        if (top < MAX_SIZE - 1) {
20.
            top++;
21.
            stack[top] = element;
22.
            cout << "Pushed " << element << " to stack." << endl;
23.
        } else {
24.
            cout << "Stack Overflow" << endl;
25.
        }
26.
    }
27.

28.
    // Pop operation: Removes the top element from the stack
29.
    int pop() {
30.
        if (top != -1) {
31.
            int element = stack[top];
32.
            top--;
33.
            return element;
34.
        } else {
35.
            cout << "Stack Underflow" << endl;
36.
            return -1;  // Return a sentinel value indicating underflow
37.
        }
38.
    }
39.

40.
    // Peek operation: Views the top element without removing it
41.
    int peek() {
42.
        if (top != -1) {
43.
            return stack[top];
44.
        } else {
45.
            cout << "Stack is Empty" << endl;
46.
            return -1;  // Return a sentinel value indicating empty stack
47.
        }
48.
    }
49.

50.
    // isEmpty operation: Checks if the stack is empty
51.
    bool isEmpty() {
52.
        return top == -1;
53.
    }
54.

55.
    // isFull operation: Checks if the stack is full
56.
    bool isFull() {
57.
        return top == MAX_SIZE - 1;
58.
    }
59.
};
60.

61.
int main() {
62.
    Stack s;
63.

64.
    s.pop();  // Attempting to pop when the stack is empty
65.

66.
    // Pushing elements onto the stack
67.
    s.push(10);
68.
    s.push(20);
69.
    s.push(30);
70.

71.
    // Attempting to push when the stack is full
72.
    s.push(40);  // This should trigger a stack overflow
73.

74.
    // Peeking the top element
75.
    cout << "Top element is: " << s.peek() << endl;
76.

77.
    // Popping elements from the stack
78.
    cout << "Popped element: " << s.pop() << endl;
79.
    cout << "Popped element: " << s.pop() << endl;
80.

81.
    // Pushing more elements after popping
82.
    s.push(40);
83.
    s.push(50);
84.

85.
    // Final peek to show the current top element
86.
    cout << "Top element is: " << s.peek() << endl;
87.

88.
    return 0;
89.
}

8. Example Walkthrough and Explanation:

1. Attempt to Pop When Empty:

   • s.pop() → Stack Underflow (since the stack is empty).

2. Push Operations:

   • s.push(10) → Stack: [10]
   • s.push(20) → Stack: [10, 20]
   • s.push(30) → Stack: [10, 20, 30]

3. Attempt to Push When Full:

   • s.push(40) → Stack Overflow (since the stack size is limited to 3).

4. Peek Operation:

   • peek() → Returns the top element (30), and prints "Top element is: 30".

5. Pop Operations:

   • pop() → Removes 30 (top element), now Stack: [10, 20].
   • pop() → Removes 20 (next top element), now Stack: [10].

6. Push More Elements:

   • s.push(40) → Stack: [10, 40]
   • s.push(50) → Stack: [10, 40, 50]

7. Final Peek:

   • peek() → Returns the top element (50), and prints "Top element is: 50".

5. Conclusion:

In this blog, we've explored the fundamentals of stacks, their key operations like push, pop, and peek, and how to implement a stack using arrays in C++. Understanding stacks is crucial as they are a fundamental data structure used in various algorithms and problem-solving tasks, such as function call management and expression evaluation. 📚

By mastering these basic concepts, you'll be well on your way to tackling more advanced topics in data structures and algorithms. Keep practicing, experimenting with different implementations, and stay curious—there’s always more to learn in the world of programming! 💡🚀

Happy coding! 🎉