Stack in C++ (STL)

In this lecture, we will discuss about stack container in C++ – Standard Template Library (STL)

Introduction to the Stack Data Structure

A stack is a kind of linear data structure that works on the Last In First Out (LIFO) principle.

It means, you can insert any number of elements in stack, but removal from stack will be in reverse order. Element added last in stack, will be removed first. Imagine a stack of plates; where you can add or remove plates from the top only. Stack Data Structure workd like that only.

A stack is practicaly used at many places like,

• Browser back buttons.
• Undo & Redo functionality in GUIs.
• Function call management in programming.
• etc…

A Stack is one of the most important data structure in computer applications.

Basic Operations on Stack

A stack has core operations that allow data management:

• push(): Adds an element at the top of stack.
• pop(): Removes an element from the top of stack.
• top(): Returns a reference to the top element of stack, without removing it.
• empty(): Returns True if stack is empty, othewise retruns false.
• size(): Returns the number of elements in stack.

STL Container Stack – A Container Adaptor in C++

In C++, the Standard Template Library (STL) provides various containers and algorithms. For stacks, it also provides a ready-to-use template class stack. It is also known as a container adapter, because it uses another container internally to provide the stack functionality.

To use the stack class in C++, we need to include a header file

#include <stack>

How to create a Stack object in C++?

Syntax to declare a stack object is as follows,

std::stack<data_type> stackObj;

Here, data_type is the type of elements that this stack object can hold.

For example, to create a stack of integers we need to provide int as the template parameter while creating a stack object i.e.

std::stack<int> numberStack;

If you want to create a stack of strings, then you need to pass std::string as template parameter while creating a stack object i.e.

std::stack<std::string> stackOfStrings;

Now, once a tscak is created, we can add elements at the top of stack and also remove elements from the top of stack only. Let’s see how to do that.

Add Elements into the Stack

To add elements to the top of the stack, the Stack class provides a push() function. Let’s see an example,

#include <iostream>
#include <stack>

int main() 
{
    // Create a Stack Object
    std::stack<int> numbersStack;

    // Push Value 11 in the stack
    numbersStack.push(11);

    // Push Value 12 in the stack
    numbersStack.push(12);

    // Push Value 15 in the stack
    numbersStack.push(15);

    return 0;
}

The push() function of stack, accepts an element as an argument and adds that element to the top of the stack. In the given example, we’ve created a stack of integers i.e. numbersStack and added three elements into it. The stack will appear as follows:

15 --> Top of Stack
12
11

The element at the top of this stack is the one that was added last, in this case, 15. It’s important to remember that the last element added to the stack will always be positioned at the top of the stack.

Access element at the top of a Stack

The Stack class provides a function called top(), that returns a reference to the element at the top of the stack. It does not remove the element, but rather, it just returns a reference to the element at the top. As in the earlier example, we created a stack and added three elements to it using the push() function. The element at the top of the stack is the one that was added last, which is 15. If we call the top() function on this stack now, it will return the element 15.

std::cout<< numbersStack.top() ;

Output:

15

We can also assign a new value to this returned reference to alter the top element of the stack. For example, by changing the value of the top element to 200, the content of the stack will be adjusted accordingly.

numbersStack.top() = 200;

std::cout<< numbersStack.top() ;

Output:

200

Now stack will look like this,

200 --> Top of Stack
12
11

An important point to note is that if we call the top() function on an empty stack, it can result in undefined behavior.

Check if stack is empty or not

To verify whether a stack is empty, the Stack class provides a empty() function. It returns true if the stack is empty and false otherwise. For instance, in the following example, we create an empty stack and then use the empty() function to check if the stack is indeed empty.

#include <iostream>
#include <stack>

int main() 
{
    // Create a Stack Object
    std::stack<int> numbersStack;

    // Check if stack is empty
    if (numbersStack.empty() )
    {
        std::cout<< "Stack is Empty" << std::endl;
    }
    else
    {
        std::cout<< "Stack is Not Empty" << std::endl;
    }

    return 0;
}

Output:

Stack is Empty

Get the number of elements in Stack

To determine the size of a stack, C++ provides a size() function. This function returns the number of elements in the stack. In the upcoming example, we create a stack and add five elements to it using the ‘push()’ function. Next, we call the ‘size’ function on the stack to obtain the number of elements in it. In this case, it should return 3.

#include <iostream>
#include <stack>

int main() 
{
    // Create a Stack Object
    std::stack<int> numbersStack;

    numbersStack.push(11);
    numbersStack.push(12);
    numbersStack.push(15);

    std::cout<<"Number of elements in Stack: "<< numbersStack.size() <<std::endl;

    return 0;
}

Output:

Number of elements in Stack: 3

How to remove element from the Top of Stack

To remove elements from a stack, C++ provides a pop() function. The stack operates on the Last-In-First-Out (LIFO) principle, which means that the element added last will be removed first. The pop() function removes the element from the top of the stack. For instance, in the above example, we create a stack and push three elements into it: 11, 12, and 15. The stack will look like this:

15 --> Top of Stack
12
11

The element added last, 15 in this case, will be at the top. If we call the pop() function, it will remove the top element from the stack, that is, 15.

numbersStack.pop();

Now stack will have 2 elements only i.e.

12 --> Top of Stack
11

The element from the top of stack got deleted i.e. value 15 got removed from the stack in this case. It’s crucial to note that the pop() function does not return anything; it just removes the top element.

If the stack is empty, calling pop() can result in undefined behavior. Therefore, it’s always advisable to first verify if the stack is empty before removing the top element using the pop() function.

Iterate over all elements of stack

A stack does not support random access, meaning we can only access the top element of the stack using the ‘top’ function. To access or print all the elements in a stack, we can iterate in a loop until the stack is not empty. In each iteration, we will call the ‘top’ function to access the top element of the stack, and then call the ‘pop’ function to remove that element.

In the subsequent iteration, we’ll call the ‘top’ function again to access the new top element, and then remove that too using the ‘pop’ function. By doing this in a loop until the stack is empty, we can iterate over all the elements in the stack and print them to the console.

#include <iostream>
#include <stack>

int main() 
{
    // Create a Stack Object
    std::stack<int> numbersStack;

    numbersStack.push(11);
    numbersStack.push(12);
    numbersStack.push(15);
    numbersStack.push(20);

    while(!numbersStack.empty())
    {
        // Get element from the top of stack
        int elem = numbersStack.top();
        std::cout << elem << ", ";

        // Remove element from the top of stack
        numbersStack.pop();

    }
    std::cout<< std::endl;
    return 0;
}

Output:

20, 15, 12, 11, 

Here, we are accessing all the elements in the stack and printing them to the console. However, it’s important to note that after this iteration, the stack is left empty.

Stack customization

A stack is a container adapter in C++. This means that it internally uses another STL (Standard Template Library) container to implement its Last-In-First-Out (LIFO) functionality. By default, the stack uses the ‘deque’ container to implement its internal functionality.

If you want to change the internal container while creating a stack object, you can do so by providing it as a second template parameter while declaring the stack object. For instance, if you want your stack object to use a ‘vector’ as its internal data structure, you can provide it as the second template parameter.

std::stack<int, std::vector<int> > numbersStack;

Similarly, if you wish to use ‘list’ as the internal data structure while creating a stack object, you will need to provide ‘list’ as the second template parameter.

std::stack<int, std::list<int> > numbersStack;

However, an important point to note here is that whatever data structure is used for the implementation of the stack and passed as the second template parameter, it should support random access operation.

There are some crucial points to remember when using a stack. If you are calling the top() function on an empty stack, it can result in undefined behavior. Similarly, calling the ‘pop’ function on an empty stack can also result in undefined behavior. Therefore, it’s always best to first check if the stack is empty or not before calling the top() or pop() function.

Summary

A stack is one of the important Data Structure in C++, and today we learned about the stack class in C++.