The stack in C++ programming

Stack data structures

A stack is a data structure that stores and retrieves items in a last-in-first-out manner. Like an array or a linked list, a stack is a data structure that holds a sequence of elements. Unlike arrays and lists, however, stacks are last-in-first-out (LIFO) structures.

This means that when a program retrieves elements from a stack, the last element inserted into the stack is the first one retrieved (and likewise, the first element inserted is the last one retrieved).

Stacks are useful data structures for algorithms that work first with the last saved element of a series. For example, computer systems use stacks while executing programs.

• When a function is called, they save the program’s return address on a stack. They also create local variables on a stack.
• When the function terminates, the local variables are removed from the stack and the return address is retrieved. Also, some calculators use a stack for performing mathematical operations.

Stack Operations

A stack has two primary operations: push and pop. The push operation causes a value to be stored, or pushed onto the stack. For example, suppose we have an empty integer stack that is capable of holding a maximum of three values.

With that stack we execute the following push operations.

• push(5);
• push(10);
• pop(15);

The pop operation retrieves (and hence, removes) a value from the stack.

The following examples demonstrates the stack adapter class. Header <stack> must be included to use class stack.

Function popElements pops the elements off each stack. stack function top to retrieve the top element of the stack for output.

Function pop (available in each adapter class) to remove the top element of the stack. Function pop does not return a value.

    #include <iostream>
    #include <vector> 
    #include <list> 
    using namespace std;
    
    // pushElements function-template prototype
    template< typename T > void pushElements( T &stackRef );
    
    // popElements function-template prototype
    template< typename T > void popElements( T &stackRef );
    int main() {
    stack< int > intDequeStack;
    stack< int, vector< int > > intVectorStack;
    stack< int, list< int > > intListStack;
    
    // push the values 0-9 onto each stack
    cout << "Pushing onto intDequeStack: ";
    pushElements( intDequeStack );
    cout << "\nPushing onto intVectorStack: ";
    pushElements( intVectorStack );
    cout << "\nPushing onto intListStack: ";
    pushElements( intListStack );
    cout << endl << endl;
    
    // display and remove elements from each stack
    cout << "Popping from intDequeStack: ";
    popElements( intDequeStack );
    cout << "\nPopping from intVectorStack: ";
    popElements( intVectorStack );
    cout << "\nPopping from intListStack: ";
    popElements( intListStack );
    cout << endl;
    } // end main
    
    // push elements onto stack object to which stackRef refers
    template< typename T > void pushElements( T &stackRef ){
    for ( int i = 0; i < 10; ++i ) {
    stackRef.push( i ); // push element onto stack
    cout << stackRef.top() << ' '; // view (and display) top element
    } // end for
    } // end function pushElements
    
    // pop elements from stack object to which stackRef refers
    template< typename T > void popElements( T &stackRef ){
    while(!stackRef.empty()) {
    cout << stackRef.top() << ' '; // view (and display) top element
    stackRef.pop(); // remove top element
    } // end while
    } // end function popElements

    Program Output :
    Pushing onto intDequeStack: 0 1 2 3 4 5 6 7 8 9
    Pushing onto intVectorStack: 0 1 2 3 4 5 6 7 8 9
    Pushing onto intListStack: 0 1 2 3 4 5 6 7 8 9
    Popping from intDequeStack: 9 8 7 6 5 4 3 2 1 0
    Popping from intVectorStack: 9 8 7 6 5 4 3 2 1 0
    Popping from intListStack: 9 8 7 6 5 4 3 2 1 0

A stack can be implemented with any of the sequence containers: vector, list and deque.

This example creates three integer stacks, using each of the sequence containers of the Standard Library as the underlying data structure to represent the stack.