How to implement a Stack using list in C++ STL

0 0 2 minutes read

In this article, we will discuss how to implement a Stack using list in C++ STL.

Stack is a linear data structure which follows. LIFO(Last In First Out) or FILO(First In Last Out). It mainly supports 4 major operations:
1. Push: Push an element into the stack.
2. Pop: Removes the element by following the LIFO order.
3. Top: Returns the element present at the top of the stack.
4. Empty: Returns whether the stack is empty or not.

Below is the implementation of the above approach:

C++

// C++ implementation of stack 
// using list STL 
#include <bits/stdc++.h> 
using namespace std; 
  
template <typename T> 
// templating it so that any data type can be used 
  
class Stack { 
public: 
    list<T> l; 
    int cs = 0; 
    // current size of the stack 
  
    // pushing an element into the stack 
    void push(T d) 
    { 
        cs++; 
        // increasing the current size of the stack 
        l.push_front(d); 
    } 
  
    // popping an element from the stack 
    void pop() 
    { 
        if (cs <= 0) { 
            // cannot pop us stack does not contain an 
            // elements 
            cout << "Stack empty" << endl; 
        } 
        else { 
            // decreasing the current size of the stack 
            cs--; 
            l.pop_front(); 
        } 
    } 
  
    // if current size is 0 then stack is empty 
    bool empty() { return cs == 0; } 
  
    // getting the element present at the top of the stack 
    T top() { return l.front(); } 
    int size() 
    { 
        // getting the size of the stack 
        return cs; 
    } 
  
    // printing the elements of the stack 
    void print() 
    { 
        for (auto x: l) { 
            cout << x << endl; 
        } 
    } 
}; 
int main() 
{ 
    Stack<int> s; 
    s.push(10); // pushing into the stack 
    s.push(20); 
    s.push(30); 
    s.push(40); 
    cout << "Current size of the stack is " << s.size() 
         << endl; 
    cout << "The top element of the stack is " << s.top() 
         << endl; 
    s.pop(); // popping from the stack 
    cout << "The top element after 1 pop operation is "
         << s.top() 
         << endl; // printing the top of the stack 
    s.pop(); // popping 
    cout << "The top element after 2 pop operations is "
         << s.top() << endl; 
    cout << "Size of the stack after 2 pop operations is "
         << s.size() << endl; 
    return 0; 
}

Output

Current size of the stack is 4
The top element of the stack is 40
The top element after 1 pop operation is 30
The top element after 2 pop operations is 20
Size of the stack after 2 pop operations is 2

Time Complexity: O(1) for both push and pop operations in the stack.
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!