Queue es una estructura de datos abstracta, algo similar a Stacks. A diferencia de las pilas, una cola está abierta en ambos extremos. Un extremo siempre se usa para insertar datos (poner en cola) y el otro se usa para eliminar datos (quitar de cola). La cola sigue la metodología First-In-First-Out, es decir, se accederá primero al elemento de datos almacenado primero.
Un ejemplo real de cola puede ser una carretera de un solo sentido, donde el vehículo entra primero y sale primero. Se pueden ver más ejemplos del mundo real como colas en las ventanillas de boletos y las paradas de autobús.
Representación de cola
Como ahora entendemos que en cola, accedemos a ambos extremos por diferentes motivos. El siguiente diagrama que se muestra a continuación intenta explicar la representación de la cola como estructura de datos:
Al igual que en las pilas, también se puede implementar una cola mediante matrices, listas vinculadas, punteros y estructuras. En aras de la simplicidad, implementaremos colas utilizando una matriz unidimensional.
Operaciones básicas
Las operaciones de cola pueden implicar inicializar o definir la cola, utilizarla y luego borrarla por completo de la memoria. Aquí intentaremos comprender las operaciones básicas asociadas con las colas:
Se requieren pocas funciones más para que la operación de cola mencionada anteriormente sea eficiente. Estos son …
-
ojeada() – Obtiene el elemento al principio de la cola sin eliminarlo.
-
está lleno() – Comprueba si la cola está llena.
-
esta vacio() – Comprueba si la cola está vacía.
En la cola, siempre sacamos de la cola (o accedemos) a los datos, señalados por parte delantera puntero y mientras buscamos (o almacenamos) datos en la cola, tomamos la ayuda de trasero puntero.
Primero aprendamos sobre las funciones de apoyo de una cola:
ojeada()
Esta función ayuda a ver los datos en el parte delantera de la cola. El algoritmo de la función peek () es el siguiente:
Algoritmo
begin procedure peek return queue[front] end procedure
Implementación de la función peek () en lenguaje de programación C –
Ejemplo
int peek() {
return queue[front];
}
está lleno()
Como estamos usando una matriz de una sola dimensión para implementar la cola, solo verificamos que el puntero trasero alcance MAXSIZE para determinar que la cola está llena. En caso de que mantengamos la cola en una lista enlazada circular, el algoritmo será diferente. Algoritmo de la función isfull () –
Algoritmo
begin procedure isfull
if rear equals to MAXSIZE
return true
else
return false
endif
end procedure
Implementación de la función isfull () en lenguaje de programación C –
Ejemplo
bool isfull() {
if(rear == MAXSIZE - 1)
return true;
else
return false;
}
esta vacio()
Algoritmo de la función isempty () –
Algoritmo
begin procedure isempty
if front is less than MIN OR front is greater than rear
return true
else
return false
endif
end procedure
Si el valor de parte delantera es menor que MIN o 0, indica que la cola aún no se ha inicializado y, por lo tanto, está vacía.
Aquí está el código de programación C:
Ejemplo
bool isempty() {
if(front < 0 || front > rear)
return true;
else
return false;
}
Operación de puesta en cola
Las colas mantienen dos punteros de datos, parte delantera y trasero. Por lo tanto, sus operaciones son comparativamente difíciles de implementar que las de las pilas.
Se deben seguir los siguientes pasos para poner en cola (insertar) datos en una cola:
-
Paso 1 – Compruebe si la cola está llena.
-
Paso 2 – Si la cola está llena, producirá un error de desbordamiento y saldrá.
-
Paso 3 – Si la cola no está llena, incremente trasero puntero para señalar el siguiente espacio vacío.
-
Paso 4 – Agregue un elemento de datos a la ubicación de la cola, donde apunta la parte posterior.
-
Paso 5 – devuelve el éxito.
A veces, también verificamos si una cola está inicializada o no, para manejar cualquier situación imprevista.
Algoritmo para la operación de puesta en cola
procedure enqueue(data)
if queue is full
return overflow
endif
rear ← rear + 1
queue[rear] ← data
return true
end procedure
Implementación de enqueue () en lenguaje de programación C –
Ejemplo
int enqueue(int data)
if(isfull())
return 0;
rear = rear + 1;
queue[rear] = data;
return 1;
end procedure
Operación de sacar de cola
Acceder a los datos de la cola es un proceso de dos tareas: acceder a los datos donde parte delantera está apuntando y eliminar los datos después del acceso. Se siguen los siguientes pasos para realizar sacar de cola operación –
-
Paso 1 – Compruebe si la cola está vacía.
-
Paso 2 – Si la cola está vacía, producirá un error de subdesbordamiento y saldrá.
-
Paso 3 – Si la cola no está vacía, acceda a los datos donde parte delantera está apuntando.
-
Paso 4 – Incremento parte delantera puntero para apuntar al siguiente elemento de datos disponible.
-
Paso 5 – Devolver el éxito.
Algoritmo para la operación de eliminación de cola
procedure dequeue
if queue is empty
return underflow
end if
data = queue[front]
front ← front + 1
return true
end procedure
Implementación de dequeue () en lenguaje de programación C –
Ejemplo
int dequeue() {
if(isempty())
return 0;
int data = queue[front];
front = front + 1;
return data;
}
Para obtener un programa de cola completo en lenguaje de programación C, haga clic aquí.