Instituto Universitario de Administración Industrial

Carrera: Informática
Sección: 28 2 A1
Materia: Estructura de Datos
Profesora: Bettmar Ovalles

LISTAS, PILAS Y COLAS

Christian Quiñones
20.913.650.
Caracas, 28 de Junio de 2022
 INDICE

- INTRODUCCIÓN…………………………………………………………………1
- ¿QUÉ SON LAS LISTAS, PILAS Y COLAS?..............................................2
- ¿QUÉ ES UNA LISTA ENLAZADA DEL TIPO PILA?.................................3
- CARACTERÍSTICAS DE UN TDA DE TIPO PILA……………………………4
- EJEMPLO DE IMPLEMENTACIÓN DE UN TDA DE TIPO PILA EN C++ ..5
- IMPORTANCIA Y VENTAJAS DE UN TDA DE TIPO PILA…………………7
- ¿QUÉ ES UNA LISTA ENLAZADA DEL TIPO COLA?...............................8
- CARACTERÍSTICAS DE UN TDA DE TIPO COLA………………………….9
- EJEMPLO DE IMPLEMENTACIÓN DE UN TDA TIPO COLA EN C++…..10
- IMPORTANCIA Y VENTAJAS DE UN TDA DE TIPO COLA……………...12
- ¿QUÉ ES UNA LISTA ENLAZADA DEL TIPO LISTA?.............................13
- CARACTERÍSTICAS DE UN TDA DE TIPO LISTA………………………...14
- EJEMPLO DE IMPLEMENTACIÓN DE UN TDA TIPO LISTA EN C++….15
- IMPORTANCIA Y VENTAJAS DE UN TDA DE TIPO LISTA……………..19
- CONCLUSIONES……………………………………………………………….20
- BIBLIOGRAFÍA…………………………………………………………………21
 INTRODUCCION

En este trabajo se dará un breve repaso sobre las estructuras de datos del tipo
pila, cola y lista. Se identificará que tipos de vectores son y cómo funcionan,
indicando también en que consiste cada uno de estos tipos, cuales son sus
características e importancia y como podemos implementar cada uno de estos
tipos de estructuras a nuestros programas.

1
 ¿QUÉ SON LAS LISTAS, PILAS Y COLAS?

Estas son estructuras de datos definidas como Listas Enlazadas, las cuales
son Tipos de Datos Abstractos (TDA) que nos permite almacenar datos de una
forma organizada, al igual que los vectores, pero, a diferencia de estos, esta
estructura es dinámica, por lo que no tenemos que saber "a priori" los elementos
que puede contener.
En una lista enlazada, cada elemento apunta al siguiente excepto el último que
no tiene sucesor y el valor del enlace es null. Por ello los elementos son registros
que contienen el dato a almacenar y un enlace al siguiente elemento. Los
elementos de una lista, suelen recibir también el nombre de nodos de la lista.

Figura 1. Esquema de un nodo y una lista enlazada.

Para que esta estructura sea una lista enlazada, debe tener unos operadores
asociados que permitan la manipulación de los datos que contiene. Los
operadores básicos de una lista enlazada son:
- Insertar: Inserta un nodo con dato x en la lista, pudiendo realizarse esta
inserción al principio o final de la lista o bien en orden.
- Eliminar: Elimina un nodo de la lista, puede ser según la posición o por el
dato.
- Buscar: Busca un elemento en la lista.
- Localizar: Obtiene la posición del nodo en la lista.
- Vaciar: Borra todos los elementos de la lista

2
 ¿QUÉ ES UNA LISTA ENLAZADA DEL TIPO PILA?

Una pila es una estructura de datos en la cual los elementos almacenados en

la misma se agregan y se sacan del mismo lugar, llamado el tope de la pila. El
tope es el único lugar a partir del cual se pueden acceder a los elementos de la
estructura. Esta característica hace que el último elemento en ser insertado en la
pila es el primero en salir. Este tipo de estructuras se denominan LIFO (Last In
First Out).

Figura 2. Esquema de una Estructura de Datos de tipo Pila.

Para utilizar el Tipo de Dato Abstracto (TDA) Pila, el mismo nos proveerá de
una serie de procedimientos que nos permitirán acceder o agregar elementos. Los
siguientes son los procedimientos básicos que debe contener una pila:
- 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.
3
 Para la implementación de la pila, es necesario que el tipo de dato contenga
una referencia al nodo tope de la pila. Luego, cada nodo tendrá una referencia al
nodo que le siguiente. De esta manera se formará una cadena con inicio en el
nodo tope y que finaliza en el último elemento de la pila, cuyo nodo no referenciará
a ningún elemento.

Figura 3. Esquema de los nodos en una pila y cómo se enlazan.

CARACTERÍSTICAS

- Acceso limitado al último elemento insertado

- Operaciones básicas: apilar, desapilar y cima.
- Desapilar o cima en una pila vacía es un error en el TDA pila.
- Quedarse sin espacio al apilar es un error de implementación.
- Cada operación debería tardar una cantidad constante de tiempo en
ejecutarse. Con independencia del número de elementos apiladas.

4
 EJEMPLO
Figura 4.1 Esquema de la Implementación del TDA pila utilizando punteros
en C++

5
Figura 4.2

6
 Figura 4.3

IMPORTANCIA Y VENTAJAS DEL TDA PILA

Una serie de lenguajes de programación están orientadas a la pila, lo que
significa que la mayoría definen operaciones básicas (añadir dos números, la
impresión de un carácter) cogiendo sus argumentos de la pila, y realizando de
nuevo los valores de retorno en la pila. Muchas máquinas virtuales también están
orientadas hacia la pila, incluida la p-código máquina y la máquina virtual Java.
Casi todos los entornos de computación de tiempo de ejecución de memoria
utilizan una pila especial para tener información sobre la llamada de un
procedimiento o función y de la anidación con el fin de cambiar al contexto de la
llamada a restaurar cuando la llamada termina.
Algunos lenguajes de programación utilizan la pila para almacenar datos que
son locales a un procedimiento. El espacio para los datos locales se asigna a los
temas de la pila cuando el procedimiento se introduce, y son borradas cuando el
procedimiento termina. El lenguaje de programación C es generalmente aplicado
de esta manera.
La búsqueda de la solución de un problema, es independientemente de si el
enfoque es exhaustivo u óptimo, necesita espacio en la pila. Ejemplos de
búsqueda exhaustiva métodos son fuerza bruta y backtraking. Ejemplos de
búsqueda óptima a explorar métodos, son branch and bound y soluciones
heurísticas. Todos estos algoritmos utilizan pilas para recordar la búsqueda de
nodos que se han observado, pero no explorados aún. La única alternativa al uso
de una pila es utilizar la recursividad y dejar que el compilador sea recursivo (pero
en este caso el compilador todavía está utilizando una pila interna). El uso de pilas
es frecuente en muchos problemas, que van desde almacenar la profundidad de
los árboles hasta resolver crucigramas o jugar al ajedrez por ordenador. Algunos
de estos problemas pueden ser resueltos por otras estructuras de datos como una
cola.
7
 ¿QUÉ ES UNA LISTA ENLAZADA DEL TIPO COLA?

Una cola es una estructura de datos en la cual los elementos almacenados en

la misma se agregan al final y se sacan del principio de la cola. Esta característica
hace que el primer elemento insertado en la cola es el primero en salir, como en
cualquier cola de la realidad (en un banco, en el cine, en el colectivo). Este tipo de
estructuras se denominan FIFO (First In First Out).

Figura 5. Esquema de una Estructura de Datos de tipo Cola.

Para utilizar el Tipo de Dato Abstracto (TDA) Pila, el mismo nos proveerá de
una serie de procedimientos que nos permitirán acceder o agregar elementos. Los
siguientes son los procedimientos básicos que debe contener una pila:
- Crear: se crea la cola vacía.
- Encolar: se añade un elemento a la cola. Se añade al final de esta.
- Desencolar: (sacar, salir, eliminar): se elimina el elemento frontal de la
cola, es decir, el primer elemento que entró.
- Frente: (consultar, front): se devuelve el elemento frontal de la cola, es
decir, el primer elemento que entró.
8
 Para implementar una cola será necesario que la estructura contenga una
referencia al primer nodo de la cola y otra al último nodo. Luego, desde el primer
nodo de la cola, se irán encadenando los demás nodos, hasta el último.

Figura 6. Esquema de los nodos en una cola y como se enlazan.

CARACTERÍSTICAS

- Operaciones básicas: insertar, quitarPrimero y primero.

- Cada rutina debería ejecutarse en tiempo constante.

9
 EJEMPLO

Figura 6.1 Esquema de la Implementación del TDA cola utilizando punteros

en C++

10
Figura 6.2

11
 Figura 6.3

IMPORTANCIA Y VENTAJAS DEL TDA COLA

Las colas se utilizan en sistemas informáticos, transportes y operaciones de

investigación (entre otros), donde los objetos, personas o eventos son tomados
como datos que se almacenan y se guardan mediante colas para su posterior
procesamiento. Este tipo de estructura de datos abstracta se implementa en
lenguajes orientados a objetos mediante clases.

12
 ¿QUÉ ES UNA LISTA ENLAZADA DEL TIPO LISTA?

Una lista es una estructura de datos en la cual los elementos almacenados en

la misma pueden ser agregados, borrados y accedidos sin restricciones, en
cualquier punto de la estructura. A diferencia de las pilas y las colas, en las listas
se pueden ver todos los elementos de la estructura, permitiendo realizar recorridos
y consultas de los datos. De la estructura de una lista se distinguen dos
elementos: el principio, a partir del cual se inician las búsquedas y recorridos; y el
corriente, elemento de referencia en la lista, a partir del cual se realizan borrados,
inserciones y modificaciones.

Figura 7. Esquema de una Estructura de Datos de tipo Lista.

La implementación de la estructura de dato de lista puede conllevar a algunas

de las operaciones siguientes:
- Un constructor para crear una lista vacía;
- Una operación para probar si una lista está vacía;
- Una operación para agregar una entidad al inicio de una lista
- Una operación para agregar una entidad al final de una lista
- Una operación para determinar el primer elemento (o la "cabeza") de una
lista
- Una operación para referirse a la lista que consta de todos los componentes
de una lista excepto su primero (esto es llamado "cola" de la lista.)
13
 El tipo de dato abstracto lista, contendrá dos referencias a nodos de la lista. La
primera corresponderá al primer nodo de la lista. La otra hará referencia al
elemento actual o corriente de la lista. Luego, los nodos de la lista se irán
encadenando uno a uno hasta el último elemento. Hay que tener en cuenta que el
elemento corriente puede ser cualquiera de la lista, y que ira variando según la
primitiva que se utilice.

Figura 8. Esquema de los nodos en una lista y como se enlazan.

CARACTERÍSTICAS

- Cada nodo apunta al siguiente y al anterior.

- Duplica el uso de la memoria necesaria para los punteros.
- Duplica el coste de manejo de punteros al insertar y eliminar.
- La eliminación se simplifica.
- No es necesario buscar el elemento anterior.

14
 EJEMPLO

Figura 9.1 Esquema de la Implementación del TDA lista utilizando punteros

en C++

15
Figura 9.2

16
Figura 9.3

17
Figura 9.4

18
 IMPORTANCIA Y VENTAJAS DEL TDA LISTA

Como el nombre indica, las listas pueden ser usadas para almacenar una lista
de registros.
Debido a que, en la informática, las listas son más fáciles de realizar que los
Conjuntos, un conjunto finito en sentido matemático se puede implementar como
una lista con restricciones adicionales, es decir, duplicar los elementos no está
permitido y su orden es irrelevante. Si la lista está ordenada, esto acelera la
determinación de si un elemento está en el conjunto, pero, a fin de garantizar el
orden, se requiere más tiempo para añadir nueva entrada a la lista. En
implementaciones eficientes, sin embargo, los conjuntos se implementan
utilizando árboles binarios de búsqueda balanceados o tablas hash, en lugar de
una list. Las listas pueden ser manipuladas utilizando iteración o recursión. La
primera forma es a menudo preferida en lenguajes de programación imperativos,
mientras la última es la norma en lenguajes funcionales.

19
 CONCLUSIONES

Con el presente trabajo se concluye que las TDA(Tipos de Datos Abstractos)

pilas, colas y listas funcionan como listas enlazadas las cuales todas están
conectadas desde un nodo homogéneo que contiene información hacía el que le
sigue dentro de la lista a través de los apuntadores que contiene cada nodo, y
cada uno de estos tipo de estructura tiene diferentes formas de manipular la
información y de modificar los datos dentro de estas, lo cual hace que cada una
sirva para distintos procesos dentro de los programas que creamos.

20
 BIBLIOGRAFÍA

Referencias Bibliográficas:
- Lic. Gustavo Carolo. (2005). Algoritmos y Programación II. Guía de
Estudio – Lista, Pilas y Colas.
- Universidade Da Coruña. Estructura de Datos: Pilas, Colas, Listas.
Facultad de Informática, Universidad A Coruña.

Fuentes Electrónicas:
- https://es.wikipedia.org/wiki/Pila_(inform%C3%A1tica)
- https://es.wikipedia.org/wiki/Lista_(tipo_de_dato_abstracto)
- https://es.wikipedia.org/wiki/Cola_(inform%C3%A1tica)
- https://algo2.files.wordpress.com/2008/08/ayp2_listas_pilas_y_colas.p
df
- https://calcifer.org/documentos/librognome/glib-lists-queues.html

21