Guía rápida de creación de listas (III)

Artículos de la serie:

• Parte I
• Parte II
• Parte III

---

Pilas y colas

Una vez finalizada la plantilla de clase List<>, resulta inmediato implementar nuevas plantillas que proporcionen la funcionalidad de una pila o una cola.

Recordemos que una pila (stack en Inglés) es una estructura de datos que responde al esquema LIFO (Last-In, First-Out; último en entrar, primero en salir). La lista de funciones miembro que modifican dicha estructura se reduce, pues, a:

• top(): acceder al elemento en la cima de la pila.
• push(): insertar un elemento en la cima.
• pop(): eliminar el elemento en la cima.

A las que podemos añadir funciones adicionales tales como empty() o size() con el fin de averiguar si la pila está vacía o determinar el tamaño de la misma, respectivamente.

Esta nueva clase puede implementarse como un simple adaptador que almacene una lista como dato privado y dé acceso únicamente a un extremo de la misma (de acuerdo con el esquema explicado anteriormente) a través de su interfaz pública. En otras palabras, restringiremos la interfaz pública de la lista (mucho más amplia e inicialmente incompatible con la de la pila) para adaptarla a la deseada mediante un encapsulamiento apropiado. Así, resulta:

   template<typename T>    class Stack {         // estructura LIFO        List<T> list_;    public:       Stack() = default;       // acceso:        T const& top() const { return list_.front(); } // cima       T&       top()       { return list_.front(); }       // modificadores:        void push(T const& val) { list_.push_front(val); } // insertar sobre cima        void pop()              { list_.pop_front(); }     // eliminar cima       // capacidad:       bool        empty() const noexcept { return list_.empty(); }       std::size_t size()  const noexcept { return list_.size(); }    };

Aquí, las funciones miembro de la lista front(), push_front() y pop_front() (así como back(), en previsión de la codificación de la cola), no analizadas en posts anteriores de esta serie, pueden codificarse fácilmente como sigue:

   template<typename T>    class List {       // ...    public:       // ...        T&       front()       { return *begin(); }  // acceder al primer elemento       T const& front() const { return *begin(); }       T&       back()       { return *(--end()); } // acceder al último elemento       T const& back() const { return *(--end()); }       void push_front(T const& val) { insert(begin(),val); }       void pop_front()              { erase(begin()); }    };

De modo similar, una cola (queue en Inglés) es una estructura de datos que responde al esquema FIFO (First-In, First-Out; primero en entrar, primero en salir). Su interfaz pública básica se reduce, lógicamente, a:

• front(): acceder al elemento al frente de la cola.
• back(): acceder al elemento en el fondo.
• push(): insertar un elemento en el fondo.
• pop(): eliminar el elemento en el frente.

Un nuevo adaptador proporciona esta funcionalidad:

   template<typename T>    class Queue {         // estructura FIFO       List<T> list_;    public:       Queue() = default;       // acceso:        T const& front() const { return list_.front(); } // primer elemento       T&       front()       { return list_.front(); }       T const& back() const { return list_.back(); }  // último elemento       T&       back()       { return list_.back(); }       // modificadores:        void pop()              { list_.pop_front(); }     // eliminar el frente       void push(T const& val) { list_.push_back(val); }  // insertar al fondo       // capacidad:       bool        empty() const noexcept { return list_.empty(); }       std::size_t size()  const noexcept { return list_.size(); }    };