Introducción a las Estructuras de Datos (IV)

CHenry [chenry@lab.matcom.uh.cu]

Colas

Definición:

Una cola es un contenedor de objetos que se insertan y se eliminan siguiendo el principio de primero en entrar, primero en salir (FIFO: First In First Out). Al elemento de mas tiempo en la cola se le denomina frente de la cola (front).

Las operaciones definidas para una cola son las siguientes:
• enqueue: inserta un objeto al final de la cola.
• empty: retorna si la cola esta vacía o no.
• dequeue: remueve el objeto que está en el frente de la cola; no está¡ definido si la cola está¡ vacía.
• front: retorna el objeto que esta en el frente de la cola sin borrarlo; no esta definido si la cola esta vacía.

Su definición axiomática es como sigue:

Cola
Tipo	QUEUE[G]
Funciones	enqueue: QUEUE[G] x G P QUEUE[G] dequeue: QUEUE[G] R-> QUEUE[G] front: QUEUE[G] R-> G empty: QUEUE[G] P-> BOOLEAN new: QUEUE[G]
Axiomas x: G, q: QUEUE[G]	empty(new): al crear una cola siempre está vacía. not empty(enqueue(q,x)): una cola que se le añade un elemento no está vacía. front(enqueue(q, x)) = x si empty(q): si a una cola vacía se le añade un elemento, este pasa a ser el frente. front(enqueue(q, x)) = front(q) si not empty(q): si a una cola que no está vacía le añadimos un elemento, el frente sigue siendo el mismo. dequeue(enqueue(q, x)) = q si empty(q) (semejante a front). dequeue(enqueue(q, x)) = enqueue(dequeue(q), x) si not empty(q) (semejante a front).
Precondiciones	dequeue(q: QUEUE[G]): not empty(q) front(q: QUEUE[G]): not empty(q)

Las colas pueden ser implementadas de varias formas, como son:
• Arreglo (Aparece una nueva operación para la cola para saber si está llena; la mejor forma de hacerlo es considerando el arreglo con forma circular).
• Nodos enlazables.

Pilas

Definición:

Una pila es un contenedor de objetos que se insertan y se eliminan siguiendo el principio el último en entrar, primero en salir (LIFO: Last In First Out). Al último elemento que se inserta en una pila se le denomina tope de la pila.

Las operaciones definidas para una pila son las siguientes:
• push: inserta un objeto en el tope de la pila.
• empty: retorna si la pila esta vacía o no.
• pop: extrae el objeto que esta en el tope de la pila; no esta definido si la pila esta vacía.
• top: retorna el objeto que esta en el tope de la pila sin borrarlo; no esta definido si la pila esta vacía.

Su definición como TDA es igual al mostrado en el artículo introductorio.

Pila
Tipo	STACK[G]
Funciones	push: STACK[G] x G P STACK[G] pop: STACK[G] R-> STACK[G] top: STACK[G] R-> G empty: STACK[G] P BOOLEAN new: STACK[G]
Axiomas	top(push(s, x)) = x pop(push(s, x)) = s empty(new) not empty(push(s, x))
Precondiciones	pop(s: STACK[G]): not empty(s) top(s: STACK[G]): not empty(s)

Las pilas pueden ser implementadas de varias formas; entre ellas sobresalen como las más comunes:
• Arreglo (Aparece una nueva operación para la pila para saber si está llena.)
• Nodos enlazables.

Artículos relacionados