Estructura de datos y algoritmos: cola

---

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í.