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 carril, 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:

enqueue() - agregar (almacenar) un artículo a la cola.
dequeue() - eliminar (acceder) un elemento de la cola.

Se requieren pocas funciones más para que la operación de cola mencionada anteriormente sea eficiente. Estos son ...

peek() - Obtiene el elemento al principio de la cola sin eliminarlo.
isfull() - Comprueba si la cola está llena.
isempty() - Comprueba si la cola está vacía.

En la cola, siempre retiramos (o accedemos) a los datos, señalados por front puntero y mientras buscamos (o almacenamos) datos en la cola, tomamos la ayuda de rear puntero.

Primero aprendamos sobre las funciones de apoyo de una cola:

ojeada()

Esta función ayuda a ver los datos en el frontde la cola. El algoritmo de la función peek () es el siguiente:

Algorithm

begin procedure peek
   return queue[front]
end procedure

Implementación de la función peek () en lenguaje de programación C -

Example

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 () -

Algorithm

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 -

Example

bool isfull() {
   if(rear == MAXSIZE - 1)
      return true;
   else
      return false;
}

esta vacio()

Algoritmo de la función isempty () -

Algorithm

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 front es menor que MIN o 0, indica que la cola aún no se ha inicializado, por lo tanto, está vacía.

Aquí está el código de programación C:

Example

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, front y rear. 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:

Step 1 - Comprueba si la cola está llena.
Step 2 - Si la cola está llena, producirá un error de desbordamiento y saldrá.
Step 3 - Si la cola no está llena, incremente rear puntero para señalar el siguiente espacio vacío.
Step 4 - Agregue un elemento de datos a la ubicación de la cola, donde apunta la parte posterior.
Step 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 -

Example

int enqueue(int data)      
   if(isfull())
      return 0;
   
   rear = rear + 1;
   queue[rear] = data;
   
   return 1;
end procedure

Operación Dequeue

Acceder a los datos de la cola es un proceso de dos tareas: acceder a los datos donde frontestá apuntando y eliminar los datos después del acceso. Se siguen los siguientes pasos para realizardequeue operación -

Step 1 - Compruebe si la cola está vacía.
Step 2 - Si la cola está vacía, producirá un error de subdesbordamiento y saldrá.
Step 3 - Si la cola no está vacía, acceda a los datos donde front está apuntando.
Step 4 - Incremento front puntero para apuntar al siguiente elemento de datos disponible.
Step 5 - Devolver el éxito.

Algoritmo para sacar 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 -

Example

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

↰ Previous page Next page ↱