Pila (informática) | pila como tipo abstracto de datos

Pila como tipo abstracto de datos

A modo de resumen, 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 ya presentes en la pila. «Pop» devuelve y elimina el actual nodo superior de la pila. Una metáfora que se utiliza con frecuencia es la idea de una pila de platos dispuesta en una cafetería en un contenedor con un muelle que mantiene la pila a nivel. En esa serie, solo el primer plato es visible y accesible para el usuario, todos las demás permanecen ocultos. Como se añaden nuevos platos, cada nuevo plato se convierte en la parte superior de la pila, permaneciendo escondidos debajo los demás. A medida que el plato superior se extrae de la pila, el inmediatamente inferior pasa a ocupar la parte superior de la pila. Dos principios importantes son ilustrados por esta metáfora: únicamente se accede al plato que se encuentra en la parte superior (el último en depositarse), y el resto de platos de la pila permanecen ocultos. Para extraer un plato distinto al superior habrá que extraer antes los que se encuentran sobre él.

Operaciones

Habitualmente, junto a las dos operaciones básicas de apilar y desapilar (push, pop), las pilas puede implementar otra serie de funciones:

  • Crear (constructor): crea la pila vacía.
  • Tamaño (size): regresa el número de elementos de la pila.
  • Apilar (push): añade un elemento a la pila.
  • Desapilar (pop): lee y retira el elemento superior de la pila.
  • Leer último (top o peek): lee el elemento superior de la pila sin retirarlo.
  • Vacía (empty): devuelve cierto si la pila está sin elementos o falso en caso de que contenga alguno.

Una pila puede implementarse fácilmente ya sea mediante una matriz o una lista enlazada. Lo que identifica a una estructura de datos como una pila en cualquier caso no es su estructura sino su interfaz: al usuario sólo se le permite colocar y extraer datos en el modo que se espera de una pila y algunas otras operaciones auxiliares.

Otro tipo de estructura de datos es la cola (FIFO, del inglés First In First Out), «primero en entrar, primero en salir».