Pilas y Colas

Algoritmos y
Estructura de
Datos I

1
Pilas y colas
En esta lectura, se abordarán dos estructuras de datos: pilas y colas. Ambas
son muy usadas en el ámbito informático, por lo cual es importante lograr
comprenderlas.

Se desarrollarán los conceptos de pila y cola y se evidenciará que ambas

estructuras son colecciones de nodos con un puntero a uno de ellos y un
conjunto de operaciones definidas. Son estructuras dinámicas, por lo cual
permitirán almacenar un conjunto variable de nodos.

Se analizará cómo son implementadas las operaciones permitidas en cada

una de ellas y las aplicaciones.

Finalmente, se abordará un caso particular de cola: las colas de prioridad.

Estas permiten alterar el orden de extracción de sus elementos, en función
de un valor de prioridad.

Pilas
Las pilas o stacks (en inglés) son estructuras de datos lineales,
contenedores de nodos que presentan restricciones en la adición y en el
borrado de sus elementos: el último nodo añadido es el primero en salir.

Una pila es una estructura lineal que permite almacenar y recuperar elementos
solo por uno de sus extremos: la parte superior.

Esta estructura también es llamada LIFO, siglas de Last In, First Out, o
último en entrar, primero en salir. Dichas siglas explican cómo trabaja la
estructura: funciona de manera análoga a cualquier apilamiento que se
hiciera de objetos del mundo real. Los elementos se van “apilando uno
encima de otro”, por lo cual, cuando se desee agregar un nuevo elemento,
este se ubicará encima del último agregado y, cuando se desee sacar uno,
se sacará el último elemento agregado.

Si, por ejemplo, se tiene una pila con dos elementos A y B y se desea
agregar un nuevo elemento C, entonces este será apilado luego del
elemento B. Si se desea agregar otro elemento D, este será apilado luego
del elemento C.

2
Figura 1: Ejemplo de cómo se van apilando los elementos en una pila

Fuente: elaboración propia.

Luego, si se desea extraer un elemento, se extraerá el último elemento

agregado, es decir, el que está en la cima de la pila. En este caso, será el
elemento D.

Figura 2: Ejemplo de cómo se desapila un elemento en una pila

Fuente: elaboración propia.

Es evidente notar que esta estructura de datos tiene como único acceso al
elemento más reciente, por lo cual es útil cuando solo se necesita acceder

3
 al elemento superior. Los demás elementos serán inaccesibles. Para esos
casos existen otras estructuras más adecuadas.

Implementación

Las pilas son implementadas a nivel de software como listas enlazadas o

como vectores.

Las pilas son Los vectores son estructuras de datos estáticas, es decir, que se define su
implementadas a nivel tamaño en el momento de su creación; luego siempre tendrá ese tamaño.
de software como Genera un desperdicio de espacio, ya que, cuando se crea el vector, se
listas enlazadas o reserva el espacio de memoria para toda la estructura, aunque no esté
como vectores. Se
recomienda usar listas
toda ocupada. Sin embargo, ofrece otros beneficios, tales como el acceso
debido a que son más en un tiempo constante a sus elementos. Sin entrar en mayores detalles, el
eficientes. uso de los vectores en las pilas genera la problemática de conocer
previamente el tamaño esperable de la pila para reservarlo con
anticipación. Así, se intenta minimizar el desperdicio de la memoria. Si el
tamaño del vector que se define para la pila es menor a lo necesario,
deberá crearse una nueva pila con tamaño mayor, lo cual es muy costoso.

En cambio, al no tener que preocuparse por el tamaño y dado que esta

estructura solo necesita acceso al elemento más reciente, las listas
enlazadas resuelven esta problemática de manera eficiente.

Operaciones

Una pila consta, principalmente, de dos operaciones: meter o apilar un

elemento y sacar o desapilar un elemento. Estas operaciones son
Las operaciones conocidas en los lenguajes como push y pop. La operación de sacar un
principales en las pilas
elemento implica obtener dicho elemento y eliminarlo de la pila.
son push (meter un
elemento en la pila) y
pop (recuperar y Las operaciones básicas en una pila deberían consumir un tiempo
eliminar un elemento constante O(1), independientemente de la cantidad de elementos que
de la pila). Sin posea la pila. Es comprensible si se hace la analogía con los procesos
embargo, existen otras
cotidianos de apilamiento. Es muy común mencionar como ejemplo el
operaciones como la
obtención del tamaño apilamiento de platos. Si se toma un plato, se lo reposa sobre una
de la pila, leer al superficie y se apoya otro plato sobre él, se irá formando una pila de platos
último elemento sin a medida que se van poniendo más y más platos. Si se quiere agarrar un
eliminarlo o saber si la plato, se tardará lo mismo en desapilarlo, ya sea que tengamos 5 o 1000
pila está vacía.
platos.

Si bien las operaciones más importantes son pop y push, se pueden

encontrar otras:

 Construcción: operación de creación de la pila vacía.

4
 Obtención del tamaño: operación que retorna la cantidad de elementos
que tiene la pila.
 Leer el último elemento: operación que permite obtener al último
elemento de la pila, sin eliminarlo de esta.
 Vacía: es una operación que devuelve dos valores: true (verdadero) o
false (falso), correspondientes a los valores booleanos, que indican si la
lista está vacía o no, respectivamente.

Se analizará más detalladamente cómo funcionan las operaciones push y

pop.

Push

No se debe olvidar que una pila es una lista, por lo cual, inicialmente, se
tendrá la lista vacía.

Figura 3: Pila vacía

Fuente: elaboración propia.

Si se incorpora un nuevo elemento, por ejemplo, el elemento A:

Figura 4: Pila con un elemento

Fuente: elaboración propia.

Si se agrega otro elemento B, entonces:

5
Figura 5: Pila con dos elementos

Fuente: elaboración propia.

Se puede notar que agregar un elemento a la pila implica hacer una

inserción al principio de la lista.

Pop

Esta operación implica recuperar el último elemento de la pila y eliminarlo

de esta. Por ejemplo, si se tiene una pila a la cual se le añaden los
elementos A, B y C, en ese orden, entonces, se tendrá lo siguiente:

Figura 6: Pila con tres elementos: A, B y C

Fuente: elaboración propia.

Si se desea sacar un elemento, el único que es posible retirar es el

elemento C, por lo cual la estructura quedará de la siguiente manera:

Figura 7: Pila a la que se le eliminó el elemento C

Fuente: elaboración propia.

Esto mismo sucederá si se saca al elemento B y A. En el caso del último

elemento, al extraerlo, la pila quedará vacía.

6
Aplicaciones

Las pilas son de gran utilidad e importancia en el ámbito informático. Se

encuentran en la evaluación de las expresiones en notación postfija, en
reconocedores sintácticos de lenguajes independientes del contexto, en
implementaciones de recursividad, en el diseño de compiladores, etcétera.

Aplicación de las pilas en los lenguajes de programación

Los analizadores sintácticos de los lenguajes de programación son

programas que inspeccionan el código programado como una cadena de
símbolos y verifican que cumplan con una gramática formal definida. De
esta manera, es posible detectar situaciones como, por ejemplo, que no se
haya cerrado un paréntesis que se abrió. Esto es conocido como balanceo
de tokens, y no solo sirve para los paréntesis, sino también para otros
tokens, como por ejemplo, los corchetes, las llaves, los caracteres usados
para indicar el inicio y el fin de un comentario, etcétera.

Para realizar este control del balanceo de tokens, se usan pilas. En la pila se
agregan los tokens de apertura que se van usando (“(“, “[“, “{“, etc.).
Cuando se encuentra un token de cierre (“)”, “]”, “}”, etc.), se valida que el
elemento superior de la pila sea el token de apertura de este. Por ejemplo,
si se usan los siguientes tokens: “(“, “[“, “{“, “(“, significa que si se ingresa
“)” se está cerrando al último “(“ de la pila, correspondiente a una
secuencia correcta: “(“, “[“, “{“, “(“, “)”. En ese caso, se lo elimina. Ahora
bien, puede suceder que se ingrese “]”, lo cual no coincide con el último
token de la pila, para lo cual se informará que hay un error. Esta secuencia
sería: “(“, “[“, “{“, “(“, ”]”, lo cual evidencia que es incorrecto. Lo mismo
sucede si se ingresa un token de cierre cuando la pila está vacía. En ese
caso, la secuencia sería: “)”, cuando en realidad debería ser, al menos: “(“,
“)”.

Una pila resulta útil para comprobar si existen símbolos no

equilibrados, porque sabemos que al encontrarnos con un
símbolo de cierre como ), éste deberá corresponderse con el
símbolo de apertura ( más reciente que todavía no esté
cerrado. Por tanto, introduciendo los símbolos de apertura
en una pila, podremos comprobar fácilmente si un símbolo
de cierre tiene sentido. Específicamente, tendremos el
siguiente algoritmo:

1) Crear una pila vacía.

2) Leer los símbolos hasta el final del archivo.

7
 a) Si el elemento sintáctico es un símbolo de
apertura, introducirlo en la pila.
b) Si se trata de un símbolo de cierre y la pila está
vacía, informar de que se ha producido un error.
c) En caso contrario, sacar un elemento de la pila. Si
el símbolo extraído no es el símbolo de apertura
correspondiente, informar de un error.
3) Al final del archivo, si la pila no está vacía, informar de
un error. (Weiss, 2013, p. 255).

Colas
Las colas o queues son estructuras de datos lineales de nodos que
presentan restricciones en la adición y en el borrado de sus elementos: el
primer nodo añadido es el primero en salir.

Una cola es una estructura lineal que permite almacenar elementos por el
extremo final y recuperar elementos por el otro extremo (por el principio).

Esta estructura es también llamada FIFO, correspondiente a las siglas de

First In, First Out, o primero en entrar, primero en salir. Esta sigla explica
cómo trabaja la estructura, es decir, funciona de manera análoga a una
cola de supermercado: las personas se van ubicando en una cola, acorde al
orden de llegada y, el primero que llegó, será el primero en ser atendido.
Por lo cual, los elementos se van “encolando uno detrás del otro” y,
cuando se desee agregar un nuevo elemento, este se ubicará detrás del
último elemento agregado y, cuando se desee sacar un elemento, se sacará
el elemento más viejo o el primero. En resumen, la operación de añadir un
elemento se hace por un extremo y la operación de sacar un elemento se
realiza por el otro extremo.

Si, por ejemplo, tenemos una cola con dos elementos A y B, y se desea
agregar un nuevo elemento C, entonces este será encolado luego del
elemento B. Si se desea agregar otro elemento D, este será encolado luego
del elemento C. Si se desea sacar un elemento, el único elemento posible
de sacar es el A. Luego, se podrá sacar el B y, finalmente, se podrá eliminar
al C. De este modo, quedará la cola vacía. Es importante notar que una cola
no permite un acceso aleatorio a un elemento específico, sino que solo es
posible acceder al elemento más reciente.

8
 Implementación

Las colas son implementadas a nivel de software con un tipo particular de

lista enlazada, conocidas como listas enlazadas circulares.
Las colas son
implementadas como Las listas circulares son listas enlazadas en las que el último nodo, en vez de
listas circulares. tener una referencia al siguiente elemento con valor nulo, tiene una
referencia al primer elemento de la lista.

Figura 8: Ejemplo de una lista circular

Fuente: elaboración propia.

Operaciones

Una cola consta, principalmente, de dos operaciones: meter o encolar un

Las operaciones
elemento y sacar o desencolar un elemento. Estas operaciones son
principales en las pilas
son enqueue (meter conocidas en los lenguajes como enqueue y dequeue, respectivamente. La
un elemento en la operación de sacar un elemento implica obtenerlo y eliminarlo de la pila.
cola) y dequeue
(recuperar y eliminar Las operaciones básicas en una cola, al igual que en una pila, también
un elemento de la
deberían consumir un tiempo constante O(1), independientemente de la
cola). Sin embargo,
existen otras cantidad de elementos que posea la pila.
operaciones como leer
al primer elemento sin Si bien las operaciones más importantes son enqueue y dequeue, se
eliminarlo. pueden encontrar otras:

 Construcción: operación de creación de la cola vacía.

 Frente o getFront: se obtiene el primer elemento que entró a la cola,
ubicado en el frente de esta.

Enqueue

Esta operación permite añadir un elemento al final de la cola. Se debe

recordar que una cola es una lista circular.

9
Ya se sabe qué son las listas circulares; sin embargo, se hará una
modificación. Debido a que en una lista circular el último elemento apunta
al primero, es evidente que es más apropiado tener a q apuntando al
último elemento, lo cual permite acceder al primero. De esta manera, se
tiene un puntero al último elemento, a través de q y un puntero al primer
elemento, a través de q.siguiente.

Si se tiene la lista vacía, entonces esta será como se la conoce:

Figura 9: Lista circular vacía

Fuente: elaboración propia.

Si se incorpora un nuevo elemento, por ejemplo, el elemento A:

Figura 10: Lista circular con un elemento

Fuente: elaboración propia.

Si se agrega otro elemento B, entonces:

Figura 11: Lista circular con dos elementos

10
Fuente: elaboración propia.

Se puede notar que agregar un elemento a la cola implica hacer una

inserción al final de la lista.

Dequeue

Esta operación implica recuperar el primer elemento de la cola y eliminarlo

de esta. Por ejemplo, si se tiene una cola a la cual se le añadieron los
elementos A, B y C, en ese orden, entonces, se tendrá una cola de la
siguiente forma:

Figura 12: Ejemplo de una cola con tres elementos: A, B y C

Fuente: elaboración propia.

Si se dese sacar un elemento, el único que se puede retirar es el A. Es

posible realizarlo haciendo que la referencia al siguiente elemento de C
indique el siguiente elemento de A; es decir, B. Por lo cual, la estructura
quedará de la siguiente manera:

11
 Figura 13: Cola a la que se le eliminó el elemento A

Fuente: elaboración propia.

Esto mismo sucederá si se saca al elemento B y C. En el caso del último

elemento, al extraerlo, la cola quedará vacía.

En general, para hacer el desencolamiento, se usa una variable auxiliar.

Dicha variable apunta al siguiente elemento de q: aux=q.siguiente.
Entonces, para eliminar a un elemento de la cola, se hace que el siguiente
elemento de q apunte al siguiente elemento de la variable auxiliar:
q.siguiente = aux.siguiente. Se libera, luego, a la variable auxiliar.

Colas de prioridad

En una cola de Si se continúa con el ejemplo de la cola de supermercado, se puede ver

prioridad los que, a veces, la cola no se respeta debido a que existen prioridades, tales
elementos son
desencolados usando
como las embarazadas, los ancianos, entre otras. En esos casos, un cajero
sus valores de de supermercado atenderá primero al que tiene prioridad y luego
prioridad, por lo cual continuará con las demás personas que estaban en la cola, según orden de
un elemento que se llegada.
desencole en un
momento
determinado será de
Esto es implementado a través del uso de las colas de prioridad. Estas
mayor o igual están formadas por nodos o elementos que, además, poseen un valor que
prioridad que el resto define una prioridad o jerarquía. Por esto, el desencolamiento se realizará
de los elementos de la en función del valor de prioridad. En caso de que se posean dos elementos
cola. de la misma prioridad, se desencolará aquel que sea más antiguo (el que
llegó primero), es decir, se seguirá el orden de la cola.

Una cola de prioridad es una cola donde el desencolamiento de los elementos

se realiza en función del valor de prioridad.

12
En el próximo apartado, se hablará de una aplicación de colas de prioridad
en la planificación de los procesos del sistema operativo.

Aplicaciones

Las colas también son de gran utilidad e importancia en el ámbito

informático. Una de las aplicaciones más importantes corresponde a la
planificación del uso del microprocesador.

Aplicación de las colas en la planificación de los procesos

Una aplicación importante es el uso de las colas para la planificación del

procesador. El sistema operativo tendrá una o varias colas de procesos que
necesitarán ser asignados al procesador para ejecutarse. Esta problemática
surge debido a que el procesador no puede ejecutar todos los procesos a la
vez, sino que se van alternando distintos quantums de tiempo (períodos de
tiempo fijo) en cada uno.

Los procesos, entonces, son encolados y el sistema operativo podrá aplicar

distintos algoritmos para saber qué proceso será el siguiente en ejecutarse.

Si se está usando una cola simple, el sistema operativo elegirá al primer

proceso de la cola para ser ejecutado. Lo ejecutará hasta finalizar su cuota
de tiempo y lo volverá a colocar al final de la cola. Luego tomará al
siguiente proceso que esté primero en la cola, para repetir lo mismo. Sin
embargo, no siempre esa metodología es la más eficiente de emplear.
Puede ocurrir que existan procesos que sean más importantes y que no se
desee que estén esperando en la cola para ser ejecutados. Es por esto que,
quizás, es necesario usar una cola de prioridad, de manera que los
procesos más importantes se ejecuten antes.

Esta problemática es analizada y estudiada en el ámbito de la planificación

de los procesos de los sistemas operativos. Existen muchos algoritmos,
cada uno con distintas características que servirán en distintas
circunstancias.

13
Referencias
Cormen, T., Leiserson, C., Rivest, R., y Stein, C. (2009). Elementary Data
Structures. Introduction to Algorithms (pp. 236-241). Massachusetts, USA: The
MIT Press.

Sznajdleder, P. A. (2012). Estructuras de datos dinámicas lineales. En Fernández,

D. (Ed.). Algoritmos a fondo con implementación en C y JAVA (pp. 267-286).
Buenos Aires, AR: Alfaomega.

Weiss, M. A. (2013). La API de Colecciones. En Martín-Romo, M. (Ed.). Estructuras

de datos en Java (pp. 225-227). Madrid, ES: Pearson.

14