Colas y pilas

Colas
Una cola (queue) es una estructura de datos lineal que utiliza una política de inserción y eliminación de elementos "primero en entrar, primero en salir" conocido en inglés como "first-in, first-out". Esto significa que el primer elemento agregado a una cola es el primer elemento en ser eliminado de la cola. En otras palabras, las cosas se eliminan del inicio y sólo se agregan al final dela cola.
Las colas son usadas en el mundo real en muchos lugares. Recuerda que en la sección 1.2.1 ¿Qué son las Estructuras de Datos y Algoritmos? discutimos una fila en un cine como ejemplo de una estructura de datos. Esta línea es en realidad una cola o fila. La gente se agrega a la fila al final y deja la fila al llegar al frente y comprar sus boletos. Los aviones que esperan aterrizar ydespegar de un aeropuerto también esperan en colas. En donde se muestre el señalamiento "Primero en entrar, primero en ser servido" está trabajando en base a una cola.
Las colas tienen muchas aplicaciones diferentes en las ciencias computacionales y el desarrollo de software. Una cola puede usarse para proveer un almacén o buffer. Un buffer ofrece un almacenamiento temporal para la información quedebe ser procesada después. Los ruteadores de redes guardan los paquetes de datos entrantes en una cola para dar tiempo a los ruteadores de procesar los paquetes salientes. Los sistemas operativos pueden usar una cola para implantar una política de calendarización que decida qué programa ejecutar después. Las aplicaciones que transportan audio y video a través de Internet, almacenan un cierto númerode paquetes en una cola para prevenir bajas temporales en la velocidad de conexión.
La Biblioteca de Plantillas Estándar (STL) contiene adaptadores que proveen una interfaz nueva, pero similar a un contenedor existente. El adaptador de colas ofrece la interfaz adecuada para una estructura de datos de colas. Está basada, por default, en el contenedor deque. Cuando un objeto de tipo deque es usado,un objeto de tipo deque es instanciado realmente, sólo que con una interfaz más adecuada para una cola. El Listado 1 ilustra la interfaz entera del adaptadorqueue.
 1:
 2:
 3:
 4:
 5:
 6:
 7:
 8:
 9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28: | #include <iostream> #include <string>#include <cstdlib> #include <queue> using namespace std; int main(int argc, char* argv[]) { queue<int> q; // push and pop q.push(1); q.pop(); // front andback q.push(1); q.push(2); cout << q.front() << endl; cout << q.back() << endl; // size and empty cout << q.size() << endl; cout << q.empty() << endl; return EXIT_SUCCESS;} |
Listado 1  La interfaz queue |
Sólo existen seis funciones miembro en la interfaz de adopción de colas. Los métodos push y pop insertan y remueven elementos de una cola, y los métodosfront y back brindan acceso a los datos almacenados al inicio y final de una cola. De forma similar a otros contenedores de STL que hemos examinado, el método size regresa elnúmero de elementos almacenados en una cola, y el método empty despliega un true si la cola está vacía y un false si la cola está almacenando al menos un elemento. Nota en la línea 4 del listado anterior, que la inclusión de la biblioteca <queue> es necesaria para usar el adaptador de colas.
Algo de lo que el adaptador de colas carece, es el soporte de iteradores. Sin iteradores, no existe...