View
118
Download
0
Category
Preview:
Citation preview
Pilas
Una pila es una colección ordenada de elementos en la cual se pueden insertar nuevos elementos por un extremo y se pueden retirar otros por el mismo extremo; ese extremo se llama “la parte superior” de la pila.
El elemento F es el más alto de todos los elementos que están en la pila. El elemento D es el más alto de los elementos A,B,C, pero es menor que los elementos E y F.
Pilas
Existe solamente un lugar en donde cualquier elemento puede ser agregado a la pila. Después de haber insertado el nuevo elemento, G ahora es el elemento en la cima. «Debemos aclarar en qué pila deseamos insertar elementos, puesto que es posible tener más de una pila al mismo tiempo».
Pilas
Pilas-Dinámica
La manera en cómo entran los datos a la estructura de datos y cómo salen, se denomina fifo, que viene del inglés first in first out (primero en entrar, primero en salir).
se muestran “fotografías” en distintos momentos de la pila, cuando se desea insertar H justo debajo de F. Para hacer esto se requiere, retirar tantos elementos como sean necesarios, aquí se han retirado de la cima G y F para luego insertar H, que quedará posteriormente debajo de F.
Pilas
Lo que sucede es que, cuando se retira el
elemento G se debe hacer una evaluación para determinar si el elemento retirado es el elemento objetivo, en este caso el elemento objetivo es F, puesto que se desea insertar un elemento debajo de F. Después de haber insertado F, insertamos de nuevo los elementos F y G en ese orden, además de insertar finalmente el elemento I que queda en la cima de la pila. Enseguida veremos con más detalle las operaciones básicas de las pilas.
Pilas
Lo que sucede es que, cuando se retira el
elemento G se debe hacer una evaluación para determinar si el elemento retirado es el elemento objetivo, en este caso el elemento objetivo es F, puesto que se desea insertar un elemento debajo de F. Después de haber insertado F, insertamos de nuevo los elementos F y G en ese orden, además de insertar finalmente el elemento I que queda en la cima de la pila. Enseguida veremos con más detalle las operaciones básicas de las pilas.
Pilas
Las operaciones básicas de una pila son:
1. En la pila S, insertar un elemento e: Push(S,e),2. Retirar un elemento de la pila S: pop(S),3. Verificar si la pila S está vacía: stackempty(S) 4. Saber cuál es el elemento en la cima de la pila S: stacktop(S).
Pilas - Operaciones
Sirve para insertar un elemento e en la pila S, lo vamos a escribir como:
push(S,e)
Después de hacer esta operación sucede que:El elemento en la cima de la pila S ahora es e
Pilas - Operación push
Para retirar un elemento de la pila S y asignarlo a una variable del mismo tipo que el tipo de los elementos de la pila, usaremos la operación pop escribiéndola como:v=pop(S);En donde v es una variable que almacena el valor del elemento que estaba en la cima de S. Hacer esta operación tiene algunas implicaciones: La variable v debe ser del mismo tipo que los elementos
almacenados en la pila. Solamente se puede retirar un elemento de la pila a la vez. Antes de la operación, e era el elemento en la cima, ahora ya
no lo es más. El apuntador “cima” decrece en una unidad.
Pilas - La operación pop
Esta operación toma como argumento una estructura del tipo stack (pila) y devuelve un valor booleano, devuelve un true si la pila está vacía y devuelve un false si la pila tiene al menos un elemento, es decir:stackempty(S)= true si S tiene 0 elementos false si S tiene más de 0 elementos
Pilas - La operación stackempty
Devuelve el valor del elemento en la cima de la pila S. Para hacer esta operación escribiremos:
v=stacktop(S)Las implicaciones de usar esta operación son:
1. Se hace una copia del elemento que está en la cima
2. En realidad se hacen dos operaciones, primero se hace v=pop(S), luego un push(S,v), porque después de la operación stacktop, la pila S queda sin cambio alguno.
Pila - La operación stacktop(S)
Recommended