std::stack (STL Stack class)

The STL (Standard Template Library) provides a generic and efficient implementation of the stack data structure through the std::stack class template. The std::stack is a container adapter, meaning it uses an underlying container (by default, std::deque) to implement the stack functionality.

The std::stack class provides a simple and convenient interface to work with stacks, and it includes the following important member functions:

push()

• Inserts a new element at the top of the stack.
• Time Complexity: O(1)

pop()

• Removes the top element from the stack.
• Time Complexity: O(1)

top()

• Returns a reference to the top element in the stack.
• Time Complexity: O(1)

empty()

• Checks whether the stack is empty.
• Time Complexity: O(1)

size()

• Returns the number of elements in the stack.
• Time Complexity: O(1)

Please note that the time complexities mentioned above are based on the average case for the underlying container. The default container for std::stack, which is std::deque, provides constant time complexity for all the mentioned operations. However, when using a different container, like std::vector or std::list, the time complexity might differ.

Here’s an example of using the std::stack class:

#include <iostream>
#include <stack>

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

    myStack.push(10);
    myStack.push(20);
    myStack.push(30);

    std::cout << "Top element: " << myStack.top() << std::endl; // Output: 30

    myStack.pop();
    std::cout << "Top element after pop: " << myStack.top() << std::endl; // Output: 20

    std::cout << "Stack size: " << myStack.size() << std::endl; // Output: 2

    std::cout << "Is stack empty? " << (myStack.empty() ? "Yes" : "No") << std::endl; // Output: No

    return 0;
}

In this example, we create a std::stack of integers named myStack. We use the member functions like push(), pop(), top(), empty(), and size() to manipulate and access the elements in the stack. The output of the program demonstrates the stack’s behavior, and we can see that the functions have constant time complexity due to the underlying container being std::deque.