Pilas en C++

Una pila (stack en inglés) es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Esta estructura se aplica en multitud de ocasiones en el área de informática debido a su simplicidad y ordenación implícita de la propia estructura.

Para el manejo de los datos se cuenta con dos operaciones básicas: apilar (push), que coloca un objeto en la pila, y su operación inversa, retirar (o desapilar, pop), que retira el último elemento apilado.

En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, Top of Stack en inglés). La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS.

Por analogía con objetos cotidianos, una operación apilar equivaldría a colocar un plato sobre una pila de platos, y una operación retirar a retirarlo.

Las pilas suelen emplearse en los siguientes contextos:

·                      Evaluación de expresiones en notación postfija (notación polaca inversa).

·                      Reconocedores sintácticos de lenguajes independientes del contexto

·                      Implementación de recursividad.

El método de pila para la evaluación de expresiones fue propuesto en 1955 y dos años después patentado por Fiedrich L.Bauer, quién recibió en 1988 el premio "IEEE Computer Society Pioneer Award" por su trabajo en el desarrollo de dicha estructura de datos.

Pila como tipo abstracto de datos

A modo de resumen tipo de datos, la pila es un contenedor de nodos y tiene dos operaciones básicas: push (o apilar) y pop (o desapilar). 'Push' añade un nodo a la parte superior de la pila, dejando por debajo el resto de los nodos. 'Pop' elimina y devuelve el actual nodo superior de la pila. Una metáfora que se utiliza con frecuencia es la idea de una pila de platos en una cafetería con muelle de pila. En esa serie, sólo la primera placa es visible y accesible para el usuario, todas las demás placas permanecen ocultas. Como se añaden las nuevas placas, cada nueva placa se convierte en la parte superior de la pila, escondidos debajo de cada plato, empujando a la pila de placas. A medida que la placa superior se elimina de la pila, la segunda placa se convierte en la parte superior de la pila. Dos principios importantes son ilustrados por esta metáfora: En primer lugar la última salida es un principio, la segunda es que el contenido de la pila está oculto. Sólo la placa de la parte superior es visible, por lo que para ver lo que hay en la tercera placa, el primer y segundo platos tendrán que ser retirados.

Operaciones

 Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.

·                      Crear: se crea la pila vacía. (constructor)

·                      Tamaño: regresa el número de elementos de la pila. (size)

·                      Apilar: se añade un elemento a la pila.(push)

·                      Desapilar: se elimina el elemento frontal de la pila.(pop)

·                      Cima: devuelve el elemento que está en la cima de la pila. (top o peek)

·                      Vacía: devuelve cierto si la pila está vacía o falso en caso contrario (empty).

Implementación

Un requisito típico de almacenamiento de una pila de n elementos es O(n). El requisito típico de tiempo de O(1) las operaciones también son fáciles de satisfacer con un array o con listas enlazadas simples.

La biblioteca de plantillas de C++ estándar proporciona una "pila" clase templated que se limita a sólo apilar/desapilar operaciones. Java contiene una biblioteca de la clase Pila que es una especialización de Vector. Esto podría ser considerado como un defecto, porque el diseño heredado get () de Vector método LIFO ignora la limitación de la Pila.

Estos son ejemplos sencillos de una pila con las operaciones descritas anteriormente (pero no hay comprobación de errores).

Implementación en Python

class Stack(object):

    def __init__(self):

        self.stack_pointer = None

    def push(self, element):

        self.stack_pointer = Node(element, self.stack_pointer)

    def pop(self):

        e = self.stack_pointer.element

        self.stack_pointer = self.stack_pointer.next

        return e

    def peek(self):

        return self.stack_pointer.element

    def __len__(self):

        i = 0

        sp = self.stack_pointer

        while sp:

            i += 1

            sp = sp.next

        return i

class Node(object):

    def __init__(self, element=None, next=None):

        self.element = element

        self.next = next

if __name__ == '__main__':

    # small use example

    s = Stack()

    for i in range(10):s.push(i)

    for i in range(len(s)):print(s.pop())

Implementación en Visual Basic

Public Class Stack

    Private p_index As Integer

    Private list As New ArrayList

    Public Sub New()

        p_index = -1

    End Sub

    ReadOnly Property count

        Get

            Return list.Count

        End Get

    End Property

    Public Sub push(ByVal value As Object)

        list.Add(value)

        p_index += 1

    End Sub

    Public Function pop() As Object

        Dim obj As Object = list.Item(p_index)

        list.RemoveAt(p_index)

        p_index -= 1

        Return obj

    End Function

    Public Sub clear()

        list.Clear()

        p_index = -1

    End Sub

    Public Function peek() As Object

        Return list.Item(p_index)

    End Function

End Class

En C++

#ifndef PILA

#define PILA // define la pila

template <class T>

class Pila {

private:

    struct Nodo {

        T elemento;

        Nodo* siguiente;  // coloca el nodo en la segunda posicion

    }* ultimo;

    unsigned int elementos;

public:

    Pila() {

        elementos = 0;

    }

    ~Pila() {

        while (elementos != 0) pop();

    }

    void push(const T& elem) {

        Nodo* aux = new Nodo;

        aux->elemento = elem;

        aux->siguiente = ultimo;

        ultimo = aux;

        ++elementos;

    }

    void pop() {

        Nodo* aux = ultimo;

        ultimo = ultimo->siguiente;

        delete aux;

        --elementos;

    }

    T cima() const {

        return ultimo->elemento;

    }

    bool vacia() const {

        return elementos == 0;

    }

    unsigned int altura() const {

        return elementos;

    }

};

#endif

Estructuras de datos relacionadas

El tipo base de la estructura FIFO (el primero en entrar es el primero en salir)es la cola, y la combinación de las operaciones de la pila y la cola es proporcionado por el deque. Por ejemplo, el cambio de una pila en una cola en un algoritmo de búsqueda puede cambiar el algoritmo de búsqueda en primera profundidad (en inglés, DFS) por una búsqueda en amplitud (en inglés, BFS). Una pila acotada es una pila limitada a un tamaño máximo impuesto en su especificación.

Arquitectura básica de una pila

Una pila típica es un área de la memoria de los computadores con un origen fijo y un tamaño variable. Al principio, el tamaño de la pila es cero. Un puntero de pila, por lo general en forma de un registro de hardware, apunta a la más reciente localización en la pila; cuando la pila tiene un tamaño de cero, el puntero de pila de puntos en el origen de la pila.

Las dos operaciones aplicables a todas las pilas son:

Una operación apilar, en el que un elemento de datos se coloca en el lugar apuntado por el puntero de pila, y la dirección en el puntero de pila se ajusta por el tamaño de los datos de partida.

Una operación desapilar: un elemento de datos en la ubicación actual apuntado por el puntero de pila es eliminado, y el puntero de pila se ajusta por el tamaño de los datos de partida.

Hay muchas variaciones en el principio básico de las operaciones de pila. Cada pila tiene un lugar fijo en la memoria en la que comienza. Como los datos se añadirán a la pila, el puntero de pila es desplazado para indicar el estado actual de la pila, que se expande lejos del origen (ya sea hacia arriba o hacia abajo, dependiendo de la aplicación concreta).

Por ejemplo, una pila puede comenzar en una posición de la memoria de mil, y ampliar por debajo de las direcciones, en cuyo caso, los nuevos datos se almacenan en lugares que van por debajo de 1000, y el puntero de pila se decrementa cada vez que un nuevo elemento se agrega. Cuando un tema es eliminado de la pila, el puntero de pila se incrementa.

Los punteros de pila pueden apuntar al origen de una pila o de un número limitado de direcciones, ya sea por encima o por debajo del origen (dependiendo de la dirección en que crece la pila), sin embargo el puntero de pila no puede cruzar el origen de la pila. En otras palabras, si el origen de la pila está en la dirección 1000 y la pila crece hacia abajo (hacia las direcciones 999, 998, y así sucesivamente), el puntero de pila nunca debe ser incrementado más allá de 1000 (para 1001, 1002, etc.) Si un desapilar operación en la pila hace que el puntero de pila se deje atrás el origen de la pila, una pila se produce desbordamiento. Si una operación de apilar hace que el puntero de pila incremente o decremente más allá del máximo de la pila, en una pila se produce desbordamiento.

La pila es visualizada ya sea creciente de abajo hacia arriba (como pilas del mundo real), o, con el máximo elemento de la pila en una posición fija, o creciente, de izquierda a derecha, por lo que el máximo elemento se convierte en el máximo a "la derecha". Esta visualización puede ser independiente de la estructura real de la pila en la memoria. Esto significa que rotar a la derecha es mover el primer elemento a la tercera posición, la segunda a la primera y la tercera a la segunda.