Cómo implementar una pila usando la lista en C++ STL

En este artículo, discutiremos cómo implementar una pila usando una lista en C++ STL .

Stack es una estructura de datos lineal que sigue. LIFO (último en entrar, primero en salir) o FILO (primero en entrar, último en salir). Admite principalmente 4 operaciones principales:
1. Empujar : empuja un elemento a la pila.
2. Pop : elimina el elemento siguiendo el orden LIFO.
3. Superior: Devuelve el elemento presente en la parte superior de la pila.
4. Vacío: Devuelve si la pila está vacía o no.
 

A continuación se muestra la implementación del enfoque anterior:

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;
}
Producción

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

Complejidad de tiempo: O(1) para operaciones push y pop en la pila.
Espacio Auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por adityamutharia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *