A stack in C++ is a data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. Think of it like a stack of plates: you add new plates to the top of the stack, and when you need a plate, you take the top one off.
Key Operations of Stack:
- Push: Adds an element to the top of the stack.
- Pop: Removes the top element from the stack.
- Peek/Top: Returns the top element without removing it.
- isEmpty: Checks if the stack is empty.
Stack Implementation in C++:
You can implement a stack in C++ using an array, a linked list, or the built-in std::stack container from the C++ Standard Library.
Manual Implementation
If you prefer to implement your own stack using an array, here’s a simple example using an array:
#include <iostream>
using namespace std;
#define MAX 1000
class Stack {
int top;
public:
int arr[MAX]; // Maximum size of Stack
Stack() { top = -1; }
bool push(int x);
int pop();
int peek();
bool isEmpty();
};
// Function to add an element x to the stack
bool Stack::push(int x) {
if (top >= (MAX - 1)) {
cout << "Stack Overflow" << endl;
return false;
} else {
arr[++top] = x;
cout << x << " pushed into stack" << endl;
return true;
}
}
// Function to remove the top element from the stack
int Stack::pop() {
if (top < 0) {
cout << "Stack Underflow" << endl;
return 0;
} else {
int x = arr[top--];
return x;
}
}
// Function to return the top element of the stack
int Stack::peek() {
if (top < 0) {
cout << "Stack is Empty" << endl;
return 0;
} else {
int x = arr[top];
return x;
}
}
// Function to check if the stack is empty
bool Stack::isEmpty() {
return (top < 0);
}
// Main function to test the stack implementation
int main() {
Stack stack;
stack.push(10);
stack.push(20);
stack.push(30);
cout << stack.pop() << " popped from stack" << endl;
cout << "Top element is " << stack.peek() << endl;
cout << "Stack empty: " << (stack.isEmpty() ? "true" : "false") << endl;
return 0;
}
This code demonstrates how to manually implement a stack using an array in C++, providing functions for push, pop, peek, and check if the stack is empty.
Using std::stack from the Standard Library
The C++ Standard Library provides a stack container that simplifies stack operations. Here’s an example of using std::stack:
#include <iostream>
#include <stack>
int main() {
std::stack<int> stack;
// Push elements onto the stack
stack.push(10);
stack.push(20);
stack.push(30);
// Display the top element
std::cout << "Top element is " << stack.top() << std::endl;
// Pop an element from the stack
stack.pop();
std::cout << "Top element after pop is " << stack.top() << std::endl;
// Check if the stack is empty
if (stack.empty()) {
std::cout << "Stack is empty" << std::endl;
} else {
std::cout << "Stack is not empty" << std::endl;
}
return 0;
}
Explanation:
Include Header:
#include<stack> The #include directive includes the stack library.
Create Stack:
std::stack stack;
This creates a stack of integers.
Push Elements:
stack.push(10);
stack.push(20);
stack.push(30);
These lines push the integers 10, 20, and 30 onto the stack.
Access Top Element:
std::cout << “Top element is ” << stack.top() << std::endl;
This line prints the top element of the stack (which is 30).
Pop Element:
stack.pop();
std::cout << “Top element after pop is ” << stack.top() << std::endl;
The stack.pop() call removes the top element (30), and the subsequent line prints the new top element (20).
Check if Stack is Empty:
if (stack.empty()) {
std::cout << “Stack is empty” << std::endl;
} else {
std::cout << “Stack is not empty” << std::endl;
}
This checks whether the stack is empty and prints the appropriate message.