Las pilas y colas son estructuras de datos que se generalmente simplifican ciertas operaciones de programación. Estas estructuras pueden implementarse mediante “arrays” o mediante listas enlazadas.
Pilas
Las pilas son estructuras de datos a las cuales se les puede acceder por un solo extremo de la misma. Las operaciones de inserción y extracción se realizan a través del tope, por lo cual no se puede acceder a cualquier elemento de la pila. Tienen dos operaciones básicas: “push” para insertar elementos, y “pop” para extraer elementos. Son conocidas también como estructuras de datos LIFO, que en inglés quiere decir “last in, first out”, o último en entrar, primero en salir. La pila se considera un grupo ordenado de elementos, teniendo en cuenta que el orden de los mismos depende del tiempo que lleven "dentro" de la estructura. Una posible
implementación mediante listas enlazadas sería insertando y extrayendo
siempre por el principio de la lista. Gracias a las pilas es posible el uso de la
recursividad. La variable que llama al mismo procedimiento en el q está, habrá que guardarla así como el resto de variables de la nueva llamada, para a la vuelta de la recursividad ir sacándolas, esto es posible a la implementación de pilas.
Aquí una representación gráfica de cómo es una pila, mostrando como de apila y desapila siempre en el tope.
Y aquí un ejemplo del código escrito en Python:
>>> pila = [6,7,8]
>>> pila.append(9)
>>> pila
[6, 7, 8, 9]
>>> pila.pop()
9
>>> pila.pop()
8
>>> pila[-1]
7
**************************************************************
Colas
Las colas también son llamadas FIFO (First In First Out), que quiere
decir “el primero que entra es el primero que sale”. Tanto el frente como el final de la cola, son los únicos indicados para retirar e insertar elementos, respectivamente. Esto significa que no podemos acceder directamente a cualquier elemento de la cola, sino solo al primero, o sea el que está o se encuentra en el frente, y no se pueden insertar elementos en cualquier posición sino solo por el final, así el elemento insertado queda como último.
Colas simples:
Se inserta por un sitio y se saca por otro, en el caso de la cola simple se
inserta por el final y se saca por el principio. Para realizar este tipo de cola
hay que recordar siempre cual es el siguiente elemento que se va a leer y cual
es el último elemento que se ha introducido.
Colas circulares:
En las colas circulares se considera que después del último elemento se
accede de nuevo al primero. De esta forma se reutilizan las posiciones
extraídas, el final de la cola es a su vez el principio, creándose un circuito
cerrado.
Aquí un ejemplo:
Lo que sucedió en esta tabla fue que se insertó un 5, se sacó un 1 y se insertó un 8.
Colas con prioridad:
Las colas con prioridad se implementan mediante listas o arrays
ordenados. No nos interesa en este caso que salgan en el orden de entrada
sino con una prioridad que le asignemos. Puede darse el caso que existan
varios elementos con la misma prioridad, en este caso saldrá primero aquel
que primero llego (FIFO).
Aquí un ejemplo de cola en Python:
>>> queue = ["Erick", "Juan", "Miguel"]
>>> queue.append("Tomás") # llega Tomás
>>> queue.append("Gerardo") # llega Gerardo
>>> queue.pop(0)
'Erick'
>>> queue.pop(0)
'Juan'
>>> queue
Y aquí una liga donde se muestra una cola de prioridades en código Python:
http://es.w3support.net/index.php?db=so&id=407734
Referencias:
+4
ResponderEliminarMoy bueno.
ResponderEliminar