Concepto-de-pilas - Definicion de pilas en estructura de datos PDF

Preview

Summary

Definicion de pilas en estructura de datos...

Description

Concepto de pilas Una pila es una estructura de datos ordenadas tales que solo se pueden introducir y eliminar por un extremo llamado cima.

A estas pilas se les llama estructuras LIFO. Las operaciones usuales en la pila son insertar (push) y quitar (pop). URL de video Algoritmo de Pilas https://www.youtube.com/watch?v=BGMG3P1cc84

Estas estructuras son utilizadas, por ejemplo cuando seq quiere recordar una secuencia de acciones u objetos en el orden inverso de lo ocurrido. Ejemplo: las ventanas de Windows, en los compiladores , el sos sistemas para registrar llamadas a subprogramas y recuperar datos anteriores , o recuperar parámetros, convertir notación infija a postfija, en los editores de texto para cancelar operaciones de edición recientes y recuperar el estado actual del documento, historial de páginas web visitadas.

Una pila tiene la siguiente forma

Dato

*siguiente

Nodo: El nodo contiene un dato y un puntero

Dato

*siguiente Dato

*siguiente El puntero señala hacia la posición de debajo de la pila

NULL

Instrucción para crear el nodo Struct Nodo { int dato; Nodo *siguiente; }

Como insertar elementos a una pila Son 4 pasos: 1. 2. 3. 4.

Crear el espacio en memoria para almacenar un nodo Cargar el valor dentro del nodo (dato) Cargar el puntero pila dentro del nodo *siguiente Asignar el nuevo nodo a pila

Explicación de cada paso: 1) Crear el espacio en memoria para almacenar un nodo Nodo *pila= null; (inicializamos pila en null para decirle que el puntero pila esta vacío) nuevo_nodo

Nodo *nuevo_nodo= new Nodo( );

La función va quedando así: Void AgregarPila (Nodo *&pila, int n) { Nodo *nuevo_nodo= new Nodo( );

}

2) Cargar el valor dentro del nodo (dato) nuevo_nodo

10

nuevo_nodo -> dato=10

La función va quedando así: Void AgregarPila (Nodo *&pila, int n) { Nodo *nuevo_nodo= new Nodo( ); nuevo_nodo -> dato=n;

} 3) Cargar el puntero pila dentro del nodo *siguiente

nuevo_nodo

10 nuevo_nodo-> siguiente =pila

La función va quedando así: Void AgregarPila (Nodo *&pila, int n) { Nodo *nuevo_nodo= new Nodo( ); nuevo_nodo -> dato=n; nuevo_nodo-> siguiente =pila

}

Null

4) Asignar el nuevo nodo a pila Esto se hace por que la variable puntero pila debe estar siempre señalando a la cima de la pila A este momento pila no esta señalándonos a nada. Lo que hay que hacer es que pila señale al nuevo nodo. De esta forma va adquiriendo una forma vertical.

pila=nuevo_nodo pila

Null 10 La función va quedando así: Void AgregarPila (Nodo *&pila, int n) { Nodo *nuevo_nodo= new Nodo( ); nuevo_nodo -> dato=n; nuevo_nodo-> siguiente =pila; pila=nuevo_nodo;

}

Quitar elementos de una pila 20

*siguiente 5

*siguiente 10

*siguiente

NULL

Hay 4 pasos: 1) Crear una variable *aux de tipo Nodo Nodo *aux=pila

pila 5

10

NULL

aux Esto es pedirle a aux que señale hasta donde está señalando pila. Ya asi ambas señalarían a la cima de la pila

La función va quedando así: Void sacarPila (Nodo *&pila, int & n) { Nodo *aux=pila;

} 2) Igualar el n a aux -> dato pila 5

10

aux

n=aux->dato con esto le decimos que a n le pónga el valor del dato que tiene el nodo

La función va quedando así: Void sacarPila (Nodo *&pila, int & n) { Nodo *aux=pila; n=aux->dato

}

NULL

3) Pasar pila a siguiente nodo Pila=aux->siguiente;

5

10

NULL

aux pila por eso necesitamos una variable de tipo auxiliar para poder tener una referencia a ese nodo que quiero eliminar

La función va quedando así: Void sacarPila (Nodo *&pila, int & n) { Nodo *aux=pila; n=aux->dato ; Pila=aux->siguiente;

} 4) Eliminar aux Delete aux

5

10

aux pila

NULL

nos queda de la siguiente forma

10 pila

La función va quedando así: Void sacarPila (Nodo *&pila, int & n) { Nodo *aux=pila; n=aux->dato ; Pila=aux->siguiente; delete aux;

}

NULL

Código completo para crear un nodo, agregar datos y sacar datos de una pila #include #include #include using namespace std; struct Nodo { int dato; Nodo *siguiente; }; void AgregarPila (Nodo *&, int ); void sacarPila (Nodo *&, int & ); int main() { Nodo *pila= NULL; int dato; cout>dato; AgregarPila (pila, dato); cout...