WikiGalaxy
C++ Stacks
Introduction to Stacks:
A stack is a collection of elements with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element. The order in which elements come off a stack gives rise to its alternative name, LIFO (last in, first out).
#include <iostream>
#include <stack>
int main() {
std::stack<int> s;
s.push(10);
s.push(20);
s.push(30);
std::cout << "Top element: " << s.top() << std::endl;
s.pop();
std::cout << "Top element after pop: " << s.top() << std::endl;
return 0;
}
Console Output:
Top element: 30
Top element after pop: 20
Stack Operations
Push and Pop:
The push operation adds an element to the top of the stack, while the pop operation removes the element from the top. These operations are fundamental to stack manipulation.
#include <iostream>
#include <stack>
int main() {
std::stack<std::string> s;
s.push("Hello");
s.push("World");
std::cout << "Top element: " << s.top() << std::endl;
s.pop();
std::cout << "Top element after pop: " << s.top() << std::endl;
return 0;
}
Console Output:
Top element: World
Top element after pop: Hello
Checking Stack Size
Size Method:
The size method returns the number of elements in the stack. This can be used to check if the stack is empty or how many elements it contains.
#include <iostream>
#include <stack>
int main() {
std::stack<int> s;
s.push(100);
s.push(200);
std::cout << "Stack size: " << s.size() << std::endl;
s.pop();
std::cout << "Stack size after pop: " << s.size() << std::endl;
return 0;
}
Console Output:
Stack size: 2
Stack size after pop: 1
Checking if Stack is Empty
Empty Method:
The empty method checks whether the stack is empty. It returns true if the stack has no elements, otherwise false.
#include <iostream>
#include <stack>
int main() {
std::stack<int> s;
std::cout << "Is stack empty? " << (s.empty() ? "Yes" : "No") << std::endl;
s.push(50);
std::cout << "Is stack empty after push? " << (s.empty() ? "Yes" : "No") << std::endl;
return 0;
}
Console Output:
Is stack empty? Yes
Is stack empty after push? No
Using Stack with Custom Objects
Custom Object Stacks:
Stacks can be used with custom objects by defining a class and using the stack with that class type. This allows for more complex data structures within the stack.
#include <iostream>
#include <stack>
class Book {
public:
std::string title;
Book(std::string t) : title(t) {}
};
int main() {
std::stack<Book> books;
books.push(Book("C++ Programming"));
books.push(Book("Data Structures"));
std::cout << "Top book: " << books.top().title << std::endl;
return 0;
}
Console Output:
Top book: Data Structures
Iterating Over a Stack
Stack Iteration:
Although stacks do not provide direct iterators, elements can be accessed by popping them one by one. This requires careful management to preserve the stack's state.
#include <iostream>
#include <stack>
int main() {
std::stack<int> s;
s.push(1);
s.push(2);
s.push(3);
while (!s.empty()) {
std::cout << s.top() << " ";
s.pop();
}
std::cout << std::endl;
return 0;
}
Console Output:
3 2 1
Copying Stacks
Stack Copy Constructor:
Stacks can be copied using the copy constructor. This creates a new stack with the same elements as the original.
#include <iostream>
#include <stack>
int main() {
std::stack<int> original;
original.push(10);
original.push(20);
std::stack<int> copy = original;
copy.push(30);
std::cout << "Original top: " << original.top() << std::endl;
std::cout << "Copy top: " << copy.top() << std::endl;
return 0;
}
Console Output:
Original top: 20
Copy top: 30
Swapping Stacks
Swap Function:
The swap function exchanges the contents of two stacks. This is useful for efficiently exchanging data between two stacks.
#include <iostream>
#include <stack>
int main() {
std::stack<int> stack1;
stack1.push(1);
stack1.push(2);
std::stack<int> stack2;
stack2.push(3);
stack2.push(4);
stack1.swap(stack2);
std::cout << "Top of stack1 after swap: " << stack1.top() << std::endl;
std::cout << "Top of stack2 after swap: " << stack2.top() << std::endl;
return 0;
}
Console Output:
Top of stack1 after swap: 4
Top of stack2 after swap: 2
Stack with Different Data Types
Template Stacks:
Stacks in C++ are implemented as template classes, allowing them to store any data type. This flexibility is a key advantage of using stacks in C++.
#include <iostream>
#include <stack>
int main() {
std::stack<double> s;
s.push(3.14);
s.push(2.71);
std::cout << "Top element: " << s.top() << std::endl;
return 0;
}
Console Output:
Top element: 2.71
Advanced Stack Use Cases
Complex Operations:
Stacks are used in various complex algorithms such as depth-first search, expression evaluation, and backtracking algorithms due to their LIFO nature.
// Example of using stack for expression evaluation
#include <iostream>
#include <stack>
#include <string>
int main() {
std::stack<char> s;
std::string expression = "(a+b)*(c+d)";
for (char ch : expression) {
if (ch == '(') {
s.push(ch);
} else if (ch == ')') {
if (!s.empty() && s.top() == '(') {
s.pop();
}
}
}
std::cout << "Expression is " << (s.empty() ? "balanced" : "not balanced") << std::endl;
return 0;
}
Console Output:
Expression is balanced
