Stack implementation in C++

Key takeaways:
The Stack is a linear, last-in-first-out (LIFO) data structure where the last element added is the first one removed.
In C++, stacks can be implemented using arrays involving core operations like push() and pop().
The push() operation adds elements to the top of the stack, and the pop() operation removes elements from the top.
Edge cases, such as checking whether the stack is full (isFull()) or empty (isEmpty()), must be handled.
C++ stack implementation includes defining a maximum size for the stack, managing the top index, and providing stack operations through class functions.

Stack implementation in C++

A stack is a linear data structure that follows the last-in-first-out (LIFO) principle, meaning the last element added to the stack will be the first one removed. This structure is fundamental in solving many programming problems, especially in scenarios where data must be processed in reverse order.

Think of a stack like a stack of plates. You add plates to the top, and when you need to remove one, you take it from the top. The last plate added will always be the first one removed.

In programming, stacks can be implemented in three primary ways:
Constant array: Uses a fixed-size array to store stack elements, ensuring efficient space usage but limiting stack size.
Dynamic array: Resizes the array dynamically as elements are added, allowing flexibility in stack capacity but with potential performance costs.
Linked list-based stack: Uses a linked list to implement the stack, enabling dynamic resizing and efficient memory usage, though it may be slightly more complex to manage.
For this Answer, we’ll use a constant array to implement the stack. This approach is straightforward and efficient for scenarios with a known maximum stack size, making it ideal for learning the core stack operations like push, pop, and more.

Why use a stack?

Stacks are used in various applications like expression evaluation, undo/redo functionality, backtracking algorithms, and even function call management. Understanding stack implementation in C++ is essential for efficient problem-solving in competitive programming, software development, and systems programming.

Stack operations

There are two basic operations in a stack:

push(): Adds an element to the top of the stack.
pop(): Removes the element from the top of the stack.

Stack.cpp

Stack.h

#include "Stack.h"
#include <iostream>
// Constructor to initialize the stack
Stack::Stack() : top(-1) {
  
}
// Function to check if the stack is empty
bool Stack::isEmpty() const {
    return (top == -1);
}
// Function to check if the stack is full
bool Stack::isFull() const {
    return (top == MAX_SIZE - 1);
}
// Function to push an element onto the stack
void Stack::push(int element) {
    if (isFull()) {
        return;
    }
    arr[++top] = element;
}
// Function to pop an element from the stack
void Stack::pop() {
    if (isEmpty()) {
        return;
    }
    arr[top--];
}
// Function to get the top element of the stack without popping it
int Stack::topElement() const {
    if (isEmpty()) {
        return -1; // Assuming -1 as an invalid value for the top element in this context
    }
    return arr[top];
}
int main() {
    Stack myStack;
    // Push elements until the stack becomes full
    for (int i = 1; i <= 5; ++i) {
        myStack.push(i);
        std::cout << "Pushed element: " << i << " onto the stack.\n";
    }
    // Attempt to push more elements into the full stack
    myStack.push(6);
    // Pop all elements until the stack becomes empty
    while (!myStack.isEmpty()) {
        std::cout << "Popped element: " << myStack.topElement() << " from the stack.\n";
        myStack.pop();
    }
    return 0;
}

Code explanation

Line 1: The #include "Stack.h" directive includes the Stack class header file, which contains the class definition and function declarations.
Line 2: The #include <iostream> directive includes the iostream library, providing functionalities like std::cout for output.
Line 5–7: This block defines the constructor Stack::Stack() to initialize the stack. The constructor sets the top variable to -1, indicating the stack is empty.
Line 10–12: This block defines the isEmpty() function, which checks if the stack is empty. It returns true if top is -1; otherwise, it returns false.
Line 15–17: This block defines the isFull() function, which checks if the stack is full. It returns true if top is equal to MAX_SIZE - 1; otherwise, it returns false.
Line 20–25: This block defines the push() function, which adds an element to the stack. If the stack is full (isFull()returns true), a message is printed indicating the stack is full and the element cannot be pushed. If the stack is not full, the top index is incremented, the element is added to arr[top], and a message is printed showing the pushed element.
Line 28–33: This block defines the pop() function, which removes the top element from the stack. If the stack is empty (isEmpty() returns true), a message is printed indicating the stack is empty, and no element can be popped. Otherwise, the function decrements top, effectively removing the top element, and a message is printed showing the popped element.
Line 36–41: This block defines the topElement() function, which retrieves the top element of the stack without removing it. If the stack is empty (isEmpty() returns true), a message is printed indicating the stack is empty, and the function returns -1 as an invalid value. If the stack is not empty, the function returns arr[top], the value at the top index.
Line 43–60: This main function tests the stack class. It creates an instance of Stack named myStack, then pushes elements 1 to 5 onto the stack. When the stack is full, it attempts to push element 6, but the push() function indicates the stack is full. Next, it pops all elements from the stack until it is empty, with each pop operation printing the removed element.

If you're prepping for technical interviews, understanding these Data Structures can be a game changer. For enhancing your knowledge, check out our course on Data Structures for Coding Interviews.

Test your knowledge!

Write a C++ program that takes a string and reverses it using a stack data structure. Your program should implement the following functionality:

Implement a function to reverse the input string using a stack.

Note: We have already implemented the stack for you in the widget below. You just need to add a reverseString function and click the "Run" button.

main.cpp

Stack.h

#include "Stack.h"
#include <iostream>
using namespace std;
// Constructor to initialize the stack
Stack::Stack() : top(-1) {
  
}
// Function to check if the stack is empty
bool Stack::isEmpty() const {
    return (top == -1);
}
// Function to check if the stack is full
bool Stack::isFull() const {
    return (top == MAX_SIZE - 1);
}
// Function to push an element onto the stack
void Stack::push(int element) {
    if (isFull()) {
        return;
    }
    arr[++top] = element;
}
// Function to pop an element from the stack
void Stack::pop() {
    if (isEmpty()) {
        return;
    }
    arr[top--];
}
// Function to get the top element of the stack without popping it
int Stack::topElement() const {
    if (isEmpty()) {
        return -1; // Assuming -1 as an invalid value for the top element in this context
    }
    return arr[top];
}
string reverseString(const string& input) {
    // WRITE YOUR CODE HERE
    return "";
}
int main() {
    Stack myStack;
    string input = "Educative";
    cout << "Original string: " << input << endl;
    string reversed = reverseString(input);
    cout << "Reversed string: " << reversed << endl;
    return 0;
}

To further enhance your knowledge and skills in coding interviews, we recommend specially designed path, Educative-99, which offers interactive lessons that gives hands-on experience with coding problems and opportunities to test and refine your solutions.

Conclusion

Overall, a stack is a fundamental and versatile data structure, and understanding its implementation in C++ will help you leverage its power in solving various programming problems efficiently. Also, remember to consider edge cases, handle exceptions, and choose appropriate underlying data structures based on your specific requirements when implementing a stack in C++.

Frequently asked questions

Haven’t found what you were looking for? Contact Us

How do you implement a stack in C++ using arrays?

To implement a stack in C++, create an array and use an index variable (top) to track the top element. Functions like push() and pop() manage the stack’s operations.

What is the difference between isEmpty() and isFull() in a stack?

isEmpty() checks if there are no elements in the stack, while isFull() checks if the stack has reached its maximum capacity.

Can stacks be dynamically allocated in C++?

Yes, stacks can also be implemented using linked lists in C++, which allows dynamic memory allocation, avoiding the fixed-size limitation of array-based stacks. We can also use dynamically allocated arrays for dynamic stacks.

What is the time complexity of stack operations in C++?

Both the push() and pop() operations in a stack have a time complexity of O(1) since they involve only a few operations regardless of the size of the stack.

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

Stack implementation in C++