C++ Stacks

In C++, a stack is a container adapter that provides a Last-In-First-Out (LIFO) data structure. It allows for adding elements to the top of the stack and removing elements from the top, with no direct access to other elements. Stacks are particularly useful for problems involving recursion, backtracking, or where you need to process elements in reverse order.

Key Features of `std::stack`

LIFO Order: The last element added is the first one to be removed.
Simple Interface: Limited to basic operations such as push, pop, and access to the top element.
Underlying Container: By default, std::stack uses std::deque as its underlying container, but other containers like std::vector can also be used.

Basic Syntax

To use std::stack, include the header and use the std::stack template class:

cpp
#include

Basic Operations

1. Declaration

cpp
std::stack<int> s;  // Creates an empty stack of integers

2. Adding Elements

Push: Adds an element to the top of the stack using push().

cpp
s.push(10); // Add 10 to the top of the stack
s.push(20); // Add 20 to the top of the stack

3. Removing Elements

Pop: Removes the top element from the stack using pop(). Note that pop() does not return the removed element; it simply removes it.

cpp
s.pop(); // Removes the top element (20) from the stack

4. Accessing Elements

Top: Accesses the top element of the stack using top().

cpp
int topElement = s.top(); // Access the top element (10)

5. Size and Capacity

Size: Returns the number of elements in the stack using size().
Empty: Checks if the stack is empty using empty().

cpp
std::size_t size = s.size(); // Get the number of elements
bool isEmpty = s.empty();   // Check if the stack is empty

Example Code

Here’s a complete example demonstrating these operations:

cpp
#include 
#include 

int main() {
    std::stack<int> s;

    // Adding elements
    s.push(10);
    s.push(20);
    s.push(30);

    // Accessing and removing elements
    std::cout << "Top element: " << s.top() << std::endl; // 30

    s.pop(); // Removes 30
    std::cout << "New top element: " << s.top() << std::endl; // 20

    // Checking size and empty status
    std::cout << "Stack size: " << s.size() << std::endl; // 2
    std::cout << "Is stack empty? " << (s.empty() ? "Yes" : "No") << std::endl; // No

    // Removing remaining elements
    s.pop(); // Removes 20
    s.pop(); // Removes 10
    std::cout << "Stack size after popping all elements: " << s.size() << std::endl; // 0

    return 0;
}

Underlying Container

By default, std::stack uses std::deque as its underlying container, but you can specify a different container that supports the required operations. The underlying container must support the following operations:

push_back()
pop_back()
back()
empty()
size()

Custom Container Example

Using std::vector as the underlying container:

cpp
#include 
#include 
#include 

int main() {
    std::stack<int, std::vector<int>> s;

    // Adding elements
    s.push(10);
    s.push(20);
    s.push(30);

    // Accessing and removing elements
    std::cout << "Top element: " << s.top() << std::endl; // 30
    s.pop(); // Removes 30

    std::cout << "New top element: " << s.top() << std::endl; // 20

    return 0;
}

Key Points

LIFO Order: Elements are accessed and removed in reverse order of their addition.
Limited Operations: Provides a restricted set of operations focused on stack functionality.
Custom Containers: You can use different underlying containers by specifying them as template parameters.

std::stack is a simple yet powerful data structure ideal for scenarios requiring a stack-like behavior.

techmore.in