Initialize Stack in C++ STL

Reading time: 20 minutes | Coding time: 5 minutes

The std::stack is a type of container adapter, specifically designed to operate in a LIFO fashion (last-in, first-out), elements can be inserted or removed from only one end which is called top of stack.

The std:stack is an adapter because it uses another container for the underlying storage, and links the functions push, pop, emplace etc. to the relevant functions in the underlying container.

Use stack in your program by using this header file:

#include <stack>

Stack is defined as:

std::stack<T> my_stack;

// or

std::stack<T, container> my_stack (container_instance);

• T is the datatype of elements in the stack like int, float
• container is the data structure used to initialize your stack. This is optionally and by default, it will be deque<T> and can be set to other values like vector<T>.
• container_instance is the instance of container type

The container used must have implementations for the following:

1. back()
2. push_back()
3. pop_back()

like

my_stack.push_back(1);

By default, std::stack uses std::deque as underlying container. But we can specify to use std::vector or std::list also.

Ways To Initialize Stack Based On Container

1. Default Initialization (std::deque)

In this case, we can use an existing deque to initialize our stack like:

std::stack<int> second (mydeque);

Complete code:

#include <stack>
#include <deque>
#include <iostream>

int main (int argc, char const *argv[]) {

    std::deque<int> mydeque (3,100);          // deque with 3 elements {100, 100, 100}

    std::stack<int> first;                    // empty stack
    std::stack<int> second (mydeque);         // stack initialized to copy of deque
    std::stack<int> third(second);            // stack initialized to copy of another stack
    
    std::cout << "Size of first stack:  " << first.size() << endl;
    std::cout << "Size of second stack: " << second.size() << endl;
    std::cout << "Size of third stack:  " << third.size() << endl;

    return 0;
}

2. Initializing with std::vector

In this method, we can use an existing vector to initialize our stack like:

std::stack<int, vector<int>> second (myvector);

Complete code:

#include <stack>
#include <vector>
#include <iostream>

int main (int argc, char const *argv[]) {

    std::vector<int> myvector (3,100);                      // vector with 3 elements {100, 100, 100}

    std::stack<int, vector<int>> first;                     // empty stack
    std::stack<int, vector<int>> second (myvector);         // stack initialized to copy of vector
    
    std::cout << "Size of first stack:  " << first.size() << endl;
    std::cout << "Size of second stack: " << second.size() << endl;

    return EXIT_SUCCESS;
}

3. Initializing with std::list

In this method, we use a list to initialize a stack like:

std::stack<int, list<int>> second (mylist);

Complete code:

#include <stack>
#include <list>
#include <iostream>

int main (int argc, char const *argv[]) {

    std::list<int> mylist (3,100);                      // list with 3 elements {100, 100, 100}

    std::stack<int, list<int>> first;                   // empty stack initialized
    std::stack<int, list<int>> second (mylist);         // stack initialized to copy of list
    
    std::cout << "Size of first stack:  " << first.size() << endl;
    std::cout << "Size of second stack: " << second.size() << endl;

    return EXIT_SUCCESS;
}

Complexity

The time and space complexity is same as the corresponding operation on the wrapped container.
Generally

• Time complexity: Θ(N)
• Space complexity: Θ(N)

Applications

1. Helps in managing Undo function in softwares.
2. Expression Evaluation for prefix, postfix and infix expressions.
3. Parenthesis Checking in an expression.
4. Can be used to implement Recursion.
5. Many compilers use stack for Syntax Parsing.