MATERIAL DE ESTUDIO 5 ESTRUCTURA DE DATOS
Enviado por jorgeHDZCDNS • 5 de Agosto de 2018 • Biografías • 1.182 Palabras (5 Páginas) • 242 Visitas
[pic 1]
Material de estudio 5
Tema: 7 “Estructuras de datos lineales”-PILAS
Tema: 8 “Estructuras de datos lineales”-COLAS
INTRODUCCIÓN
Las pilas y colas son tipos especiales de listas y también son estructuras lineales debido al orden consecutivo de sus elementos. Analizaremos en éste material la manera en que se construyen y las operaciones básicas para su manejo, el seguimiento que debemos hacer al código de ejemplo es muy similar a la explicación del tema anterior LISTAS.
PILAS
Una pila es un tipo especial de lista abierta en la que sólo se pueden insertar y eliminar nodos en uno de los extremos de la lista. Estas operaciones se conocen como "push" y "pop", las escrituras de datos siempre son inserciones de nodos (push), y las lecturas siempre eliminan el nodo leído (pop).
Se dice que es una estructura con comportamiento LIFO (Last In First Out), el último en entrar es el primero en salir.
El ejemplo representativo del que deriva el nombre de la estructura es una pila de platos. Sólo es posible añadir platos en la parte superior de la pila, y sólo pueden tomarse del mismo extremo.
Revise en éste link el tema Declaraciones de tipos para manejar pilas en C:
http://c.conclase.net/edd/?cap=002#inicio
Comenzaremos analizando éste ejemplo:
int main() {[pic 2]
Pila pila = NULL;//inicializamos la cabecera a null
Push(&pila, 20);//insertar el numero 20
Push(&pila, 10);//insertar el elemento 10
En éste programa declaramos un apuntador “cabecera” llamado pila que nos servirá para saber dónde empieza la estructura. Observamos que la operación Push inserta los elementos 20 y 10 en ése orden por lo que podemos imaginar la pila como un conjunto de nodos sobrepuestos en forma vertical como en la Figura 1:
Como puede observar el primer elemento en entrar fue el 20 por lo que queda en la parte inferior. El último elemento en entrar es el 10 por lo que queda en la parte superior. |
10 |
20 |
Push[pic 3]
Figura 1
Si agregamos la siguiente instrucción al código:
[pic 4]
cout<< Pop(&pila)<
Observaremos que la función POP está pensada para que se pueda desplegar en pantalla el valor de la pila que se encuentra arriba (el 10).Al mismo tiempo la operación POP elimina el nodo. Por lo que en la pila solo queda el valor 20. |
Pop 10[pic 5]
20 |
Figura 2
De esta manera podremos agregar elementos las veces que sea necesario con la función PUSH y si deseamos desplegar y borrar los nodos podremos recurrir a la función POP, siempre y cuando tomemos en cuenta que ambas operaciones solo pueden realizarse por un extremo (el superior) de la estructura.
Revise en éste link el procedimiento para realizar las operaciones básicas en una pila:
http://c.conclase.net/edd/?cap=002b#2_5
PRÁCTICA 9: pilas
Analicemos el Programa14_pilas:
- Inicialice un nuevo proyecto en DEV-C++.
- Copie el “Programa14_pilas”. Analice los comentarios agregados a cada línea y realice una prueba de escritorio en su cuaderno de la salida del programa asegurándose de entender cada comando.
- Revise la explicación de cada instrucción, observe la implementación del algoritmo de las funciones PUSH y POP:
http://c.conclase.net/edd/?cap=002c#2_6
- Depure y ejecute el código para comprobar que su prueba de escritorio es correcta. Cabe resaltar que la salida de este programa consiste en los elementos o nodos que gracias a la operación POP son sacados de la pila, desplegados en pantalla y borrados (con el comando free).
COLAS
Una cola es un tipo especial de lista abierta en la que sólo se pueden insertar nodos en uno de los extremos de la lista y sólo se pueden eliminar nodos en el otro. Además, como sucede con las pilas, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.
...