C++ Stack

In C++, a stack represents a sequential data organization that follows the Last In First Out (LIFO) concept. This signifies that the most recently added item will be the first one to be removed, while the initial item added will be the last to be eliminated. In C++, the Standard Template Library (STL) provides a stack container adapter for effective execution of LIFO procedures. This adapter encompasses various typical functions such as push, pop, size, top, empty, and more.

Elements within a stack cannot be directly accessed using index numbers. Due to the nature of a stack where elements are added and removed from the top, only the element at the top of the stack is accessible at any given time.

Syntax

It has the following syntax:

template<class T, class Container = deque<T> > class stack;

In this format,

• ✅ T: This parameter defines the data type of the element that the container adapter will contain.
• ✅ Container: This argument indicates the internal structure within the container that stores the stack elements.

C++ Stack Example

Let's consider an example to demonstrate the stack in C++ STL.

Example

#include <iostream>     

#include <stack>        //using the stack container from STL

using namespace std;    // Using standard namespace

int main() {            // Main function

    stack<int> st;      // Declare a integer stack

    // Push elements into the stack (LIFO order)

    st.push(15);  

    st.push(20);

    st.push(25);

    // Display the top element of the stack

    cout << "Top element of the list: " << st.top() << endl; 

    // Pop the top element from the stack

    st.pop();

    // Display the new top element

    cout << "After pop, top element: " << st.top() << endl;

    // Display the size of the stack

    cout << "Size of Stack: " << st.size() << endl;

    // Check if the stack is empty

    cout << "Is stack empty? " << (st.empty() ? "Yes" : "No") << endl;

    return 0;

}

Output:

Top element of the list: 25

After pop, top element: 20

Size of Stack: 2

Is stack empty? No

Explanation

In this illustration, we showcase the fundamental functionality of the STL stack container. We add three integer values to the stack, utilize top to retrieve the most recently added element (25), then eliminate it with pop. Subsequently, the code displays the new top element, confirms the stack's size, and checks if the stack is empty.

Basic Operations of C++ Stack

The basic functions that can be performed on a stack include:

Inserting Elements

In a C++ stack, we can effortlessly add new elements at the stack's top by utilizing the push function. It is not feasible to insert an element at any other position within the stack.

Syntax

It has the following syntax:

st.push(data _type)

C++ Inserting Elements Example

Let's consider an instance to demonstrate the process of adding elements to a C++ Stack.

Example

#include <iostream>

#include <stack>

using namespace std;   //using standard namespace

int main() {    //main function

    std::stack<std::string> myStack;

    myStack.push("Apple");

    myStack.push("Banana");

    myStack.push("Cherry");

    while (!myStack.empty()) {

        std::cout << myStack.top() << " ";

        myStack.pop();

    }

    return 0;

}

Output:

Cherry Banana Apple

Explanation

In this illustration, we create a string stack and insert "Apple", "Banana", and "Cherry". Subsequently, it displays and removes each item from the stack's top until it becomes empty. The result will show Cherry Banana Apple, showcasing the stack's last-in-first-out characteristic.

Accessing Elements

In C++ Stack, the top method allows us to exclusively access the element positioned at the top of the stack. Accessing any element in the middle of the stack is not supported.

Syntax

It has the following syntax:

int topElement = st.top();

C++ Accessing Elements Example

Let's consider a scenario to demonstrate the process of accessing elements in a C++ Stack.

Example

#include <iostream>

#include <stack>

using namespace std;   //using standard namespace

int main() {    //Main Function

    stack<int> myStack;

    myStack.push(10);

    myStack.push(20);

    myStack.push(30);

    cout << "Top element: " << myStack.top() <<endl;  

    return 0;

}

Output:

Top element: 30

Explanation

In this instance, we include all necessary headers and define a stack named myStack to hold integer values. The integers 10, 20, and 30 are sequentially added to the stack. Since the stack follows the Last In, First Out (LIFO) principle, the most recent value added is 30. The top method is called to access this top element without eliminating it, and the console displays it as the Top element: 30.

Deleting Elements

In a single action, solely the final item in the stack can be eliminated by employing the pop function. To eliminate any different item, it is necessary to first clear all the items that have been appended subsequent to that specific element.

Syntax

It has the following syntax:

st.pop();

C++ Deleting Elements Example

Let's consider an illustration to showcase the process of removing elements in a C++ Stack.

Example

#include <iostream>

#include <stack>

using namespace std;  //using standard namespace

int main() {    //main function

    stack<int> myStack;

    myStack.push(100);

    myStack.push(200);

    myStack.push(300);

    cout << "Top Element Before Deletion: " << myStack.top() <<endl;

    myStack.pop(); 

    cout << "Top Element After Deletion: " << myStack.top() <<endl;

    return 0;

}

Output:

Top Element Before Deletion: 300

Top Element After Deletion: 200

Explanation

In this instance, we push 100, 200, and 300 onto the stack. Subsequently, the top element, 300, is removed by executing the pop method, revealing the new top element as 200.

Pseudo Traversal

Since elements below the top cannot be accessed in a stack, they are not traversable. Nevertheless, by duplicating the stack, accessing the top element, and then removing it iteratively until the duplicate stack is empty, we can effectively traverse the stack without altering the original one.

Syntax

It has the following syntax:

stack<int> temp = st;

while (!temp.empty()) {

    cout << temp.top() << " ";

    temp.pop();

}

C++ Pseudo Traversal Example

Let's consider an example to demonstrate the pseudocode traversal in a C++ Stack.

Example

#include <iostream>

#include <stack>

using namespace std;   //using standard namespace

int main() {   //main function

    stack<int> st;

    st.push(35);

    st.push(19);

    st.push(46);

    st.push(23);

    stack<int> temp(st);

    while(!temp.empty()) {

        cout << temp.top() << " ";

        temp.pop();

    }

    return 0;

}

Output:

23 46 19 35

Explanation

In this instance, we initialize a stack and add four integers to it using the push operation. Subsequently, it duplicates the stack into a temporary variable to preserve the original stack. Lastly, a while loop is employed to retrieve and display each top element from the temporary stack, resulting in the output: 23 46 19 35, reflecting the stack's contents in a top-to-bottom order.

Check if the Stack Is Empty

In C++, within the Stack data structure, we make use of the empty function to check if the stack is devoid of elements. The empty function gives back:

• ✅ 1 (true) - if the stack contains no elements
• ✅ 0 (false) - in case the stack has elements present

Syntax

It has the following syntax:

if (st.empty()) { /* stack is empty */ }

C++ Example to check if the Stack is Empty

Let's consider an example to demonstrate how we can verify the emptiness of the stack in a C++ Stack data structure.

Example

#include <iostream>

#include <stack>

using namespace std;   //using standard namespace

int main() {   //main function

    stack<int> st;

    if (st.empty()) {

        cout << "Stack is empty." << endl;

    } else {

        cout << "Stack is not empty." << endl;

    }

    st.push(10);  

    if (st.empty()) {

        cout << "Stack is empty." << endl;

    } else {

        cout << "Stack is not empty." << endl;

    }

    return 0;

}

Output:

Stack is empty.

Stack is not empty.

Explanation

In this instance, we create a stack with no elements and check its status using the empty function to output a corresponding message. Subsequently, we add the value 10 to the stack and perform another check. Initially, the message "Stack is empty." is displayed, and upon pushing, it changes to "Stack is not empty."

Example: A simple program to show the use of basic stack functions

Let's consider another instance to demonstrate the fundamental stack operation in the C++ Stack data structure.

Example

#include <iostream>  

#include <stack>  

using namespace std;   //using standard  namespace

void newstack(stack <int> ss)  

{  

    stack <int> sg = ss;  

    while (!sg.empty())  

    {  

        cout << '\t' << sg.top();  

        sg.pop();  

    }  

    cout << '\n';  

}  

int main ()    //main function

{  

    stack <int> newst;  

    newst.push(55);  

    newst.push(44);  

    newst.push(33);  

    newst.push(22);  

    newst.push(11);  

  

    cout << "The stack newst is : ";  

    newstack(newst);  

    cout << "\n newst.size() : " << newst.size();  

    cout << "\n newst.top() : " << newst.top();  

    cout << "\n newst.pop() : ";  

    newst.pop();  

    newstack(newst);   

    return 0;  

}

Output:

The stack newst is : 11 22 33 44 55

newst.size() : 5

newst.top() : 11

newst.pop() : 22 33 44 55

Explanation

In this illustration, we define a function named newstack to exhibit a stack without modifying the original stack. Within the main function, it adds five integers to the most recent stack, showcases its elements, size, and the top element, and proceeds to remove the top element before displaying the updated stack. The resulting display showcases the stack in a bottom-to-top order: 11 22 33 44 55 initially, and after the removal operation: 22 33 44 55.

Time Complexity

The following table displays the time complexity of stack operations:

Member Types

Listed here is a compilation of various stack member categories along with brief explanations for each.

Functions

By leveraging functions, manipulation of an object or variable is achievable within the realm of programming. Stacks offer an array of functions that are available for utilization or integration into programs. Below is a compilation of these functions:

Conclusion

In summary, C++ stacks serve as a flexible data structure that operates on the Last In First Out (LIFO) concept. Through the utilization of the std::stack container adapter, elements can only be inserted or deleted from the top position.

The push function adds an element to the top of the stack, pop removes the top element, top retrieves the top element without removing it, empty checks if the stack is empty, and size returns the number of elements in the stack. While direct iteration is not supported, a pseudo-iteration method involving copying elements can be used for display purposes. Stacks play a crucial role in recursive functions, evaluating expressions, and solving backtracking issues by offering managed element access.

C++ stack MCQs

1) What is the underlying principle of a stack?

• ✅ FIFO (First In First Out)
• ✅ FILO (First In Last Out)
• ✅ LIFO (Last In First Out)
• ✅ Random Access

2) Which of the following function is used to add an element to the top of the stack?

• ✅ insert
• ✅ push
• ✅ add
• ✅ top

3) What will the top function return in a stack?

• ✅ Bottom element
• ✅ All elements
• ✅ Middle element
• ✅ Element at the top

4) Which of the following function removes the top element from the stack?

• ✅ remove
• ✅ delete
• ✅ pop
• ✅ extract

5) What does the empty function do?

• ✅ Checks if the stack is empty
• ✅ Checks if the stack is full
• ✅ Deletes all elements
• ✅ Returns the top element