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.
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.
There are two basic operations in a stack, push()
and pop().
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.
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";}}
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.
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++.
#include <iostream>const int MAX_SIZE = 5; // Maximum size of the stackclass Stack {private:int arr[MAX_SIZE];int top;public:Stack() {top = -1;} // Initialize top to -1 to indicate an empty stackbool 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 fullfor (int i = 1; i <= 5; ++i) {myStack.push(i);}// Attempt to push more elements into the full stackmyStack.push(6);// Pop all elements until the stack becomes emptywhile (!myStack.isEmpty()) {myStack.pop();}return 0;}
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.
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++.
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 stackclass Stack {private:char arr[MAX_SIZE]; // Change the data type to charint top;public:Stack() {top = -1;}bool isEmpty() {return (top == -1);}bool isFull() {return (top == MAX_SIZE - 1);}void push(char element) { // Accept char typeif (!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 chartop--;} 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;}