Stack implementation in C++

A stack is a linear data structure that follows the last-in-first-out (LIFO) principle, which means that the last element added to the stack will be the first one to be removed.

A stack can be understood by the analogy of a stack of plates. You add a plate to the top of the stack, and when you need to remove a plate, you take it from the top as well. The last plate you add will also be the first one you remove.

Stack implementation in C++

A stack can be implemented in c++ using arrays. Implementing a stack using arrays is a straightforward process. we will define an array of fixed size to hold the elements of the stack and keep track of the top of the stack using an index variable.

Let's understand some important operations required to implement a stack.

Stack operations

There are two basic operations in a stack, push() and pop().

Push() in stack

  • The push operation adds an element to the top of the stack.

  • It takes an element as an argument and places it on top of the stack.

  • The newly pushed element becomes the new top of the stack.

  • The push() operation check the condition isFull(). If the stack is already full, it prints the message telling the user that the stack is full. Otherwise, it adds an element to the top of the stack.

Let's see a visualization of how the push() operation works in a stack.

1 of 5

Now that we overviewed the push() operation, let's code it in C++.

bool isFull() {
return (top == MAX_SIZE - 1);}
void push(int element) {
if (!isFull()) {
top++;
arr[top] = element;
std::cout << "Pushed element: " << element << " onto the stack.\n";
} else {
std::cout << "Stack is full. Cannot push element " << element << ".\n";
}
}

Pop() in stack

  • The pop operation removes the top element from the stack.

  • After the pop operation, the second-top element (if present) becomes the new top.

  • The removed element is no longer accessible unless it was copied or saved before the pop operation.

  • The pop() operation check the isEmpty() condition. If the stack becomes empty, it prints the message telling the user that the stack is empty, or else, it removes the element from the top of the stack.

pop operation in stack
1 of 6

Now that we overviewed the pop() operation, let's code it in C++.

bool isEmpty() {
return (top == -1);}
void pop() {
if (!isEmpty()) {
int poppedElement = arr[top];
top--;
std::cout << "Popped element: " << poppedElement << " from the stack.\n";
} else {
std::cout << "Stack is empty. Cannot pop from an empty stack.\n";
}
}

Let's proceed and combine the codes to implement the complete stack in C++.

Complete code

#include <iostream>
const int MAX_SIZE = 5; // Maximum size of the stack
class Stack {
private:
int arr[MAX_SIZE];
int top;
public:
Stack() {
top = -1;} // Initialize top to -1 to indicate an empty stack
bool isEmpty() {
return (top == -1);}
bool isFull() {
return (top == MAX_SIZE - 1);}
void push(int element) {
if (!isFull()) {
top++;
arr[top] = element;
std::cout << "Pushed element: " << element << " onto the stack.\n";
} else {
std::cout << "Stack is full. Cannot push element " << element << ".\n";
}
}
void pop() {
if (!isEmpty()) {
int poppedElement = arr[top];
top--;
std::cout << "Popped element: " << poppedElement << " from the stack.\n";
} else {
std::cout << "Stack is empty. Cannot pop from an empty stack.\n";
}
}
int topElement() {
if (!isEmpty()) {
return arr[top];
} else {
std::cout << "Stack is empty.\n";
return -1; // In this example, we consider -1 as an invalid value.
}
}
};
int main() {
Stack myStack;
// Push elements until the stack becomes full
for (int i = 1; i <= 5; ++i) {
myStack.push(i);
}
// Attempt to push more elements into the full stack
myStack.push(6);
// Pop all elements until the stack becomes empty
while (!myStack.isEmpty()) {
myStack.pop();
}
return 0;}

Code explanation

  • Line 1: The #include <iostream> header provides input and output stream functionalities, such as std::cout (for output) and std::cin (for input).

  • Line 2: This line defines a constant variable, MAX_SIZE, with a value of 5, which represents the max-size of the stack.

  • Line 4–7: We create a Stack class with the data. The arr[max] size and an integer variable, top, hold the topmost value of the stack.

  • Line 9–12: Here, we implement a constructor of the Stack class. It initializes the private member top to -1, which indicates an empty stack.

  • Line 13–15: Here, we implement a member function of the Stack class that returns a Boolean value indicating whether the stack is empty or not. It checks if the value of the top is -1, and if so, it returns true; otherwise, it returns false.

  • Line 16–18: Here, we implement a member function of the Stack class that returns a Boolean value, indicating whether the stack is full or not. It checks if the value of the top is equal to MAX_SIZE - 1, and if so, it returns true; otherwise, it returns false.

  • Line 19–27: Here, we implement the push() operation of the stack. It takes an integer element as an argument and attempts to add it to the top of the stack. If the stack is not full (isFull() returns false), it increments the top, adds the element to the arr, and prints a message indicating the element is pushed onto the stack. If the stack is full (isFull() returns true), it prints a message indicating that the stack is full and the element cannot be pushed.

  • Line 29–37: Here, we implement the pop() operation of the stack. It removes the top element if the stack is not empty (isEmpty() returns false). If the stack is not empty, it decrements the top, effectively removing the top element and prints a message indicating the popped element. If the stack is empty (isEmpty() returns true), it prints a message indicating that the stack is empty and no element can be popped.

  • Line 39–45: The topElement() function checks if the stack is not empty (isEmpty() returns false). If the stack is not empty, it returns the value of the element at the index top in the arr. If the stack is empty (isEmpty() returns true), it prints a message indicating that the stack is empty and returns an invalid value (-1 in this example).

  • Line 49–60: This main function tests the stack implementation by first creating an instance of the Stack class, myStack.Then, It pushes elements 1, 2, 3, 4, and 5 into the stack using the push operation until the stack becomes full. It then attempts to push the element 6, but the stack is already full, so the push operation does not succeed. It pops all the elements from the stack using the pop operation until the stack becomes empty.

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++.

Test your knowledge!

Problem statement

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.

#include <iostream>
#include <string>
using namespace std;
const int MAX_SIZE = 100; // Maximum size of the stack
class Stack {
private:
char arr[MAX_SIZE]; // Change the data type to char
int top;
public:
Stack() {
top = -1;
}
bool isEmpty() {
return (top == -1);
}
bool isFull() {
return (top == MAX_SIZE - 1);
}
void push(char element) { // Accept char type
if (!isFull()) {
top++;
arr[top] = element;
} else {
cout << "Stack is full. Cannot push element " << element << ".\n";
}
}
void pop() {
if (!isEmpty()) {
char poppedElement = arr[top]; // Change the data type to char
top--;
} else {
cout << "Stack is empty. Cannot pop from an empty stack.\n";
}
}
char topElement() {
if (!isEmpty()) {
return arr[top];
} else {
cout << "Stack is empty.\n";
return '\0'; // Return null character for empty stack
}
}
string reverseString(const string& input) { // Change return type to string
// WRITE YOUR CODE HERE
};
int main() {
Stack myStack;
string input = "Educative";
cout << "Original string: " << input << endl;
string reversed = myStack.reverseString(input);
cout << "Reversed string: " << reversed << endl;
return 0;
}
Copyright ©2024 Educative, Inc. All rights reserved