INSTITUTO TECNOLOGICO DE GUSTAVO A.

MADEROII

ESTRUCTURAS LINEALES

INTEGRANTES:
Arturo Escobar Rodriguez

GRUPO: 3T1

EQUIPO: 5

FECHA DE ENTREGA: 09/03/2024

Página 1 de 16
Introducción
Las estructuras lineales de datos se caracterizan porque sus elementos están en
secuencia, relacionados en forma lineal, uno luego del otro. Cada elemento de la
estructura puede estar conformado por uno o varios subelementos o campos que
pueden pertenecer a cualquier tipo de dato, pero que normalmente son tipos
básicos. Entre las múltiples aplicaciones que tienen estas estructuras podemos
mencionar:

* El desarrollo de compiladores de lenguajes de programación que están

conformados por varios subprogramas con finalidades más específicas,
como, por ejemplo: el analizador de léxico que genera la tabla de símbolos.

* La simulación discreta de sistemas a través del computador, donde la

mayoría de los paquetes de simulación digital ofrecen lenguajes de
simulación que soportan las primitivas para el manejo de colas y sus
diferentes versiones.

Una estructura lineal de datos o lista está conformada por ninguno, uno o varios
elementos que tienen una relación de adyacencia ordenada donde existe un
primer elemento, seguido de un segundo elemento y así sucesivamente hasta
llegar al último. El tipo de dato de los elementos puede ser cualquiera, pero debe
ser el mismo tipo para todos. El valor contenido en los elementos puede ser el
mismo o diferente. En estas estructuras se realizan operaciones de agregar y/o
eliminar elementos a la lista según un criterio particular. Sobre la base de la forma
y el lugar de la realización de estas operaciones en la misma, las listas se
clasifican en listas de acceso restringido y listas de acceso no restringido. Las
listas de acceso restringido son las pilas, colas y dipolos.
En las pilas, las operaciones de acceso se realizan por un único extremo de la
lista, al cual normalmente se denomina tope de la pila. En las colas, estas
operaciones se realizan por ambos extremos de la lista llamados generalmente,
inicio y fin de la cola. Finalmente, en los dipolos que son colas dobles, las
operaciones se realizan también por ambos extremos de la lista, en este caso
todas las operaciones se pueden hacer por ambos extremos, es decir se puede
insertar o eliminar elementos por el tope o por el fin, a diferencia de la cola donde
se inserta siempre por el fin y se elimina por el tope. Se puede entonces
considerar al dipolo como una clase general de la clase cola. Las listas de acceso
no restringido, denominadas listas, son el tipo más general, al cual se considera
como la superclase de las otras clases de listas, en específico de las pilas, colas y
dipolos. Haciendo la jerarquía de clases adecuada para estas estructuras, se tiene
que la lista es la clase raíz de la jerarquía que tiene como subclases la pila, la cola
y el dipolo, este último a su vez tiene como subclases el dipolo de entrada
restringida y el dipolo de salida restringida.

Página 2 de 16
Índice

Tabla de contenido
CARATULA
...........................................................................................................................................................................1

INTRODUCCIÓN ..........................................................................................................................................................................2
índice .............................................................................................................................................................................. 3

Listas ....................................................................................................................4

Pilas ............................................................................................................................................................ 5
Colas ................................................................................................................................................................................... 6

Aplicaciones .................................................................................................................................................................. 7

conclusión ............................................................................................................................................................... 8

Referencias.................................................................................................................................................... 9

Página 3 de 16
 Listas
Un conjunto de nodos enlazados entre sí. Las listas permiten modelar diversas
entidades del mundo real como, por ejemplo, los datos de los alumnos de un grupo
académico, los datos del personal de una empresa, los programas informáticos
almacenados en un disco magnético, etc.
Tal vez resulte conveniente identificar a los diferentes elementos de la lista (que
normalmente estarán configurados como una estructura de registro) mediante uno
de sus campos (clave) y en su caso, se almacenará la lista respetando un criterio
de ordenación (ascendente o descendente) respecto al campo clave.
Una definición formal de lista es la siguiente:
“Una lista es una secuencia de elementos del mismo tipo, de cada uno de los
cuales se puede decir cuál es su siguiente (en caso de existir).”
Existen dos criterios generales de calificación de listas:
Por la forma de acceder a sus elementos.
Listas densas: Cuando la estructura que contiene la lista es la que determina la
posición del siguiente elemento. La localización de un elemento de la lista es la
siguiente:
Está en la posición 1 si no existe elemento anterior.
Está en la posición N si la localización del elemento anteriores (N-1).
Listas enlazadas: La localización de un elemento es:
Estará en la dirección k, si es el primer elemento, siendo k conocido.
Si no es el primer elemento de la lista, estará en una dirección, j, que está
contenida en el elemento anterior.
Por la información utilizada para acceder a sus elementos:
Listas ordinales: La posición de los elementos en la estructura la determina su
orden de llegada. Listas calificadas: Se accede a un elemento por un valor que
coincide con el de un determinado campo, conocido como clave. Este tipo de listas
se pueden clasificar a su vez en ordenadas o no ordenadas por el campo clave.

Página 4 de 16
LISTAS.
Una lista enlazada es una colección lineal de elementos donde el orden de los
mismos se establece mediante punteros.
Por tanto, una lista enlazada no está limitada a contener un número máximo de
componentes; puede expandir o contraer su tamaño mientras se ejecuta el
programa.
Para implementar las listas enlazadas se debe trabajar con dos tipos diferentes de variables:
variables punteras, es decir, variables cuyos valores apuntan a otras
variables, y variables referenciadas, o sea, variables que son apuntadas.

* LISTAS DOBLEMENTE ENLAZADAS.

En algunas aplicaciones podemos desear recorrer la lista hacia adelante y hacia
atrás, o dado un elemento, podemos desear conocer rápidamente los elementos
anterior y siguiente. En tales situaciones podríamos desear darle a cada celda
sobre una lista un puntero a las celdas siguiente y anterior en la lista tal y como se
muestra en la figura.
Otra ventaja de las listas doblemente enlazadas es que podemos usar un puntero
a la celda que contiene el i-ésimo elemento de una lista para representar la
posición i, mejor que usar el puntero a la celda anterior, aunque lógicamente,
también es posible la implementación similar a la expuesta en las listas simples
haciendo uso de la cabecera. El único precio que pagamos por estas
características es la presencia de un puntero adicional en cada celda y
consecuentemente procedimientos algo más largos para algunas de las
operaciones básicas de listas. Si usamos punteros (mejor que cursores) podemos
declarar celdas que consisten en un elemento y dos punteros.

* LISTAS CIRCULARES
Una lista circular es una lista lineal en la que el último nodo a punta al primero.
Las listas circulares evitan excepciones en las operaciones que se realicen sobre
ellas. No existen casos especiales, cada nodo siempre tiene uno anterior y uno
siguiente.
Página 5 de 16
En algunas listas circulares se añade un nodo especial de cabecera, de ese modo
se evita la única excepción posible, la de que la lista esté vacía.
El nodo típico es el mismo que para construir listas abiertas
Apuntador toma el valor de índice [Inicio], después ve si la condición cumple para efectuar un
Ciclo mientras Apuntador sea diferente de Inicio, si cumple lo que hace
es que despliega la Info [Apuntador], después Apuntador toma el valor de
índice [Apuntador] (El cual nos indica el siguiente nodo que sigue en la lista) y hace
esto hasta que Apuntador sea igual a Inicio (Cuando llega a este punto a llegado al
fin de la Lista).
Algoritmo:
Recorrido (Inicio, Info, índice)
Apuntador → índice [Inicio]
Repetir mientras Apuntador ≠ Inicio
Imprimir Info[Apuntador]
Apuntador → índice [Apuntador]
Fin del ciclo
Salir

* LISTAS CIRCULARES DOBLEMENTE ENLAZADAS

En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares
a los de la lista doblemente enlazada, excepto que el enlace anterior del primer
nodo apunta al último y el enlace siguiente del último nodo, apunta al primero.
Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden
ser hechas desde cualquier punto con acceso a algún nodo cercano. Aunque
estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin,
un puntero de acceso externo puede establecer el nodo apuntado que está en la
cabeza o al nodo cola, y así mantener el orden tan bien como en una lista
doblemente enlazada.

Página 6 de 16
 Pilas

Una pila es un subtipo de las listas donde el acceso está restringido a un solo
extremos de la lista, en este caso al tope de esta.
Las operaciones básicas sobre una pila son: crearla, destruirla, agregar un nuevo
elemento, suprimir un elemento, consultar el elemento del tope y verificar si está
vacía. Sobre la base de estas operaciones se especifica el TDA Pila. Esta
especificación incluye operaciones que pueden ser extendidas en la
implementación para soportar otras operaciones útiles de acuerdo con las
aplicaciones que la puedan utilizar.
En particular, toda implementación debe contener las operaciones básicas
definidas para el tipo y puede ser ampliada con otras adicionales.
Las pilas no son estructuras fundamentales de datos; es decir no están definidas
como tales en los lenguajes de programación. Para su representación requieren
de otras EDs, como:
* Arreglos
* Listas
Es importante definir el tamaño del máximo de la pila, así como una variable
auxiliar que se denomina TOPE. Está variable se utiliza para indicar el último
elemento que se insertó en la pila.
Al utilizar arreglos para implementar pilas se tiene la limitación de que se debe
reservar el espacio en memoria con anticipación. Una vez dado un máximo de
capacidad a la pila no es posible insertar un número de elementos mayor que el
máximo establecido. Si esto ocurre, en otras palabras, si la pila está llena y se
intenta insertar un nuevo elemento, se producirá un error conocido como
desbordamiento –overflow.
Una posible solución a este tipo de inconvenientes consiste en definir pilas de gran
tamaño, pero esto resultará ineficiente y costoso si solo se utilizarán algunos
elementos. No siempre es viable saber con exactitud el número de elementos a
tratar, y siempre existe la posibilidad de que ocurra un error de desbordamiento.
Otro error que se puede presentar es tratar de eliminar un elemento de una pila

Página 7 de 16
vacía. Este tipo de error se le conoce como subdesbordamiento –underflow
Las pilas son un EDs muy usadas en la solución de diversos tipos de problemas,
en el área de computación. Algunos de los casos más representativos de
aplicación de estas son:
* Llamadas a subprogramas
* Recursividad
* Tratamiento de expresiones aritméticas
* Ordenación

Finalmente podemos concluir que las pilas son necesarias en este tipo de
aplicaciones por lo siguiente:

* Permiten guardar la dirección del programa, o subprograma, desde donde

se hizo la llamada a otros subprogramas, para regresar posteriormente y
seguir ejecutándolo a partir de la instrucción inmediata a la llamada.
* Permiten guardar el estado de las variables en el momento en que se hace
la llamada, para seguir ocupándolas al regresar del subprograma.

PilaArray (int MAX): Crea una pila vacía ingresando el tamaño máximo.
GetTOPE (): Devuelve el elemento que se encuentra actualmente en el tope de la
pila. Si la pila está vacía devuelve muestra un mensaje en pantalla.
VaciarPila (): Elimina todos los elementos de la Pila
estaLlena (): Regresa Verdadero si la pila está llena.
estaVacia (): Regresa Verdadero si la pila está vacía.
Agregarenpila (): Ingresa un nuevo elemento a la pila por el tope de esta
Eliminardepila (): Elimina el elemento que está actualmente en el tope de la pila. Si
la pila está vacía no hace ninguna eliminación y manda un mensaje.
MostrarPila (): Muestra todos los elementos de la pila

Página 8 de 16
 Colas
Una cola es una estructura de datos, caracterizada por ser una secuencia de
elementos en la que la operación de inserción push se realiza por un extremo y la
operación de extracción pop por el otro. También se le llama estructura FIFO (del
inglés First In First Out), debido a que el primer elemento en entrar será también el
Primero en salir.

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

de investigación (entre otros), dónde 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, en forma de listas enlazadas.
Una cola es una estructura de datos, caracterizada por ser una secuencia de
elementos en la que la operación de inserción push se realiza por un extremo y la
operación de extracción pop por el otro. También se le llama estructura FIFO (del
inglés First In First Out), debido a que el primer elemento en entrar será también el
primero en salir.

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

de investigación (entre otros), dónde 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, en forma de listas enlazadas.

Página 9 de 16
Operaciones Básicas:
* Crear
* Encolar (añadir, entrar, insertar)
* Desencolar (sacar, salir, eliminar)
* Frente (consultar, front)
Cola (Max): se crea la cola vacía.
inserta (Elemento x): se añade un elemento a la cola. Se añade al final de esta.
Elimina (): se elimina el elemento frontal de la cola, es decir, el primer elemento
que entró.
CFrente (): se devuelve el elemento frontal de la cola, es decir, el primer elemento
que entró.
estaLlena (): Regresa Verdadero si la Cola está llena.
estaVacia (): Regresa Verdadero si la Cola está vacía.
MostrarCola (): Muestra todos los elementos de la cola

Página 10 de 16
 Aplicaciones

Las diferentes aplicaciones de la lista enlazada son las siguientes:

• Las listas enlazadas se utilizan para implementar pilas, colas, gráficos, etc.
• Las listas enlazadas se utilizan para realizar operaciones aritméticas con números enteros
largos.
• Se utiliza para la representación de arrays dispersas.
• Se utiliza en la asignación vinculada de archivos.
• Ayuda en la gestión de la memoria.
• Se utiliza en la representación de Manipulación polinomial donde cada término polinomial
representa un Node en la lista enlazada.
• Las listas enlazadas se utilizan para mostrar contenedores de imágenes. Los usuarios
pueden visitar imágenes pasadas, actuales y siguientes.
• Se utilizan para almacenar el historial de la página visitada.
• Se utilizan para realizar operaciones de deshacer.
• Los enlaces se utilizan en el desarrollo de software donde indican la sintaxis correcta de
una etiqueta.
• Las listas vinculadas se utilizan para mostrar fuentes de redes sociales

Aplicaciones de la vida real de una lista enlazada:

• Se utiliza una lista enlazada en la programación Round-Robin para realizar un seguimiento

del turno en los juegos de varios jugadores.
• Se utiliza en el visor de imágenes. Las imágenes anterior y siguiente están vinculadas, por
lo que se puede acceder a ellas mediante los botones anterior y siguiente.
• En una lista de reproducción de música, las canciones están vinculadas a las canciones
anteriores y siguientes.

Página 11 de 16
 Aplicaciones de la pila:

Las diferentes aplicaciones de Stack son las siguientes:

• La estructura de datos de pila se utiliza en la evaluación y conversión de expresiones

aritméticas.
• La pila se usa en recursividad.
• Se utiliza para comprobar paréntesis.
• Al invertir una string, también se usa stack.
• Stack se utiliza en la gestión de la memoria.
• También se utiliza para el procesamiento de llamadas a funciones.
• La pila se usa para convertir expresiones de infijo a sufijo.
• La pila se utiliza para realizar operaciones de deshacer y rehacer en procesadores de
texto.
• La pila se usa en máquinas virtuales como JVM.
• La pila se utiliza en los reproductores multimedia. Útil para reproducir la canción siguiente
y anterior.
• La pila se utiliza en la operación de recursión.

Aplicaciones de la vida real de Stack:

• Un ejemplo de la vida real de una pila es la capa de platos para comer dispuestos uno
encima del otro. Cuando quitas un plato de la pila, puedes tomar el plato en la parte
superior de la pila. Pero este es exactamente el plato que se agregó más recientemente a
la pila. Si desea que el plato esté en la parte inferior de la pila, debe quitar todos los platos
de encima para alcanzarlo.
• Los navegadores utilizan la estructura de datos de pila para realizar un seguimiento de los
sitios visitados anteriormente.
• El registro de llamadas en dispositivos móviles también utiliza una estructura de datos de
pila.

Página 12 de 16
 Aplicaciones de cola:

Las diferentes aplicaciones de Queue son las siguientes:

• La cola se utiliza para manejar el tráfico del sitio web.

• Ayuda a mantener la lista de reproducción en los reproductores multimedia.
• La cola se usa en los sistemas operativos para manejar interrupciones.
• Ayuda a atender requests en un solo recurso compartido, como una impresora,
programación de tareas de CPU, etc.
• Se utiliza en la transferencia asíncrona de datos para, por ejemplo, tuberías, archivo IO,
sockets.
• Las colas se utilizan para la programación de trabajos en el sistema operativo.
• En las redes sociales se utiliza la cola para subir múltiples fotos o videos.
• Para enviar una estructura de datos de cola de correo electrónico se utiliza.
• Para manejar el tráfico del sitio web en un momento se utilizan colas.
• En el sistema operativo de Windows, para cambiar de aplicación múltiple.

Página 13 de 16
Conclusión

Página 14 de 16
 REFERENCIAS
1. Diego. (2023, diciembre 13). El funcionamiento de una pila en estructuras de datos: todo

lo que necesitas saber. JMJ INFORMÁTICO. https://jmjinformatico.es/como-funciona-

una-pila-en-estructura-de-datos/

2. Estructuras de datos: pila y cola. (2285, March 5). CodeGym.

https://codegym.cc/es/groups/posts/es.291.estructuras-de-datos-pila-y-cola
3. Pila (Estructura de datos) - EcuRed. (n.d.). Www.ecured.cu.
https://www.ecured.cu/Pila_(Estructura_de_datos)
4. Redes, L., Servicios, Y., & Cómputo, D. (n.d.). ESTRUCTURAS DE DATOS. Retrieved April
24, 2008, from https://www.uv.mx/personal/ermeneses/files/2021/08/Clase6-
ColasFinal.pdf&lt#:~:text=Una%20cola%20es%20una%20estructura%20de%20datos%
20que
5. A. CONCEPTO DE COLA B. OPERACIONES DE LA COLA C. IMPLEMENTACION DE LA COLA
D. APLICACIONES DE LA COLA E. PROYECTO. (n.d.). Retrieved April 1, 2017, from
https://www.fcca.umich.mx/descargas/apuntes/Academia%20de%20Informatica/Estr
uctura%20de%20Datos%20%20%20%20G.a.G.C/Unidad%203.pdf
6. A. CONCEPTO DE COLA B. OPERACIONES DE LA COLA C. IMPLEMENTACION DE LA COLA
D. APLICACIONES DE LA COLA E. PROYECTO. (n.d.). Retrieved April 19, 2021, from
https://www.fcca.umich.mx/descargas/apuntes/Academia%20de%20Informatica/Estr
uctura%20de%20Datos%20%20%20%20G.a.G.C/Unidad%203.pdf
7. Listas estructura de datos. (2020). Studocu; Studocu. https://www.studocu.com/es-
ar/document/universidad-jose-maria-vargas/teoria-de-sistemas/listas-estructura-de-
datos/16314324
8. TEMA 3 Listas. 3.1. CONCEPTOS GENERALES. (n.d.). Retrieved April 1, 2022, from
https://www.sites.upiicsa.ipn.mx/estudiantes/academia_de_informatica/estructura_y
_rd/docs/u2/RECURSOS/Listas.pdf
Página 15 de 16
Página 16 de 16