Listas Pilas Y Colas En C++

Capítulo

34

Listas, pilas
y colas en C++
Contenido
• Tipo abstracto de datos lista
• Operaciones de listas enlazadas, clase lista
• Inserción en una lista
• Buscar un elemento y recorrer una lista enlazada
• Borrado de un nodo
• Lista doblemente enlazada
• Clase ListaDoble
• Listas enlazadas genéricas
• Tipo abstracto de datos pila
• Clase pila con arreglo (array)
•Pila genérica con listas enlazadas
• Tipo abstracto de datos cola
• Cola con un arreglo (array) circular
• Cola genérica con una lista enlazada
• Bicolas: colas de doble entrada
• Resumen
• Ejercicios
• Problemas

Introducción
Este capítulo estudia tres tipos abstractos de datos fundamentales, las listas enlazadas, las pilas y las
colas. Cada una de ellas se implementa en C++utilizando clases. La estructura lista enlazada (ligada o
encadenada, “linked list”) es una colección de elementos (denominados nodos) dispuestos uno a continuación de otro, cada uno de ellos conectado al siguiente elemento por un “enlace” o “referencia”. En
el capítulo se define una clase que agrupa la representación de una lista y las operaciones que se apli-

1048

Listas, pilas y colas enC++

Capítulo 34

can: insertar, buscar, borrar elementos y recorrer la lista. De igual modo se muestra el tipo abstracto
de datos (TAD) que representa a las listas enlazadas.
La Pila es una estructura de datos que almacena y recupera sus elementos atendiendo a un estricto
orden; las pilas se conocen también como estructuras LIFO (last-in/first-out, último en entrar/primero
en salir). Laspilas se utilizan en compiladores, sistemas operativos y programas de aplicaciones.
El tipo abstracto de datos cola almacena y recupera sus elementos atendiendo a un estricto orden.
Las colas se conocen como estructuras FIFO (first-in/first-out, primero en entrar/primero en salir),
debido a la forma y orden de inserción y de extracción de elementos de la cola. Las colas tienen numerosasaplicaciones en el mundo de la computación: colas de mensajes, colas de tareas a realizar por
una impresora, colas de prioridades.

Conceptos clave
•
•
•
•
•

Cola
Enlace
Estructura enlazada
Lista
Lista doblemente enlazada

•
•
•
•

Nodo
Pila
template

Tipo abstracto de datos

Tipo abstracto de datos lista
Una lista almacena información del mismo tipo, con lacaracterística de que puede contener un número indeterminado de elementos, y que estos elementos mantienen un orden explícito. Este ordenamiento explícito se manifiesta en que, en sí mismo, cada elemento contiene la dirección del siguiente
elemento. Cada elemento es un nodo de la lista.

dato

siguiente

dato

siguiente

cabeza

dato

siguiente

actual

dato

cola

Figura 34.1Representación gráfica de una lista enlazada.

Una lista es una estructura de datos dinámica. El número de nodos puede variar rápidamente en
un proceso, aumentando los nodos por inserciones, o bien, disminuyendo por eliminación de nodos.
Las inserciones se pueden realizar por cualquier punto de la lista. Por la cabeza (inicio), por el final (cola), a partir o antes de un nodo determinado de lalista. Las eliminaciones también se pueden
realizar en cualquier punto de la lista; además, se eliminan nodos dependiendo del campo de información o dato que se desea suprimir de la lista.

Especificación formal del TAD lista
Matemáticamente, una lista es una secuencia de cero o más elementos de un determinado tipo.
(a1, a2, a3, ... , an) siendo n >= 0,
si n = 0 la lista es vacía.

Loselementos de la lista tienen la propiedad de que están ordenados de forma lineal, según las
posiciones que ocupan en la misma. Se dice que ai precede a ai+1 para i = 1 ..., n−1; y que ai
sucede a ai−1 para i = 2 ... n.
Para formalizar el tipo de dato abstracto lista a partir de la noción matemática, se define un conjunto de operaciones básicas con objetos de tipo Lista. Las operaciones:...