Кръгла опашка


Ниво на трудност Лесно
Често задавани в Infosys Maq o9 решения Оракул
Опашка Училищно програмиране Теория

A кръгова опашка е усъвършенствана форма на линейна опашка. В линейната опашка не можем да вмъкнем елемент в опашката, ако задната част сочи към последния индекс на опашката и опашката не е напълно запълнена. Това причинява загуба на памет. За да преодолеем тази загуба, използваме кръговата опашка.

В кръгова опашка, ако последният индекс е попълнен тогава, задната част сочи към първия индекс на опашката. Работи на принципа First In First Out (FIFO).

Червената стрелка е преден показалец, а черната стрелка е задна показалка.

Кръгла опашка

 

Основни терминологии 

  1. Front: Първият указател сочи към първия елемент в опашката.
  2. Rear: Задният указател сочи към последния елемент от опашката.
  3. Опашка:  вмъкването на елемент в опашката се нарича опашка.
  4. Dequeue: Това е процесът на изтриване на елемент от опашката.

Вмъкване в кръговата опашка

Стъпка 1:

  • Проверете дали опашката е напълно запълнена или не.
  • Ако (отзад == размер на опашката-1 И отпред == 0) ИЛИ (отзад == отпред-1), тогава опашката е напълно запълнена и не можем да вмъкнем повече елементи в нея.

Стъпка 2:

  • В противен случай проверяваме дали задната == размер на опашката-1, след това присвояваме задна = 0 иначе задна = задна + 1 и след това вмъкваме елемент в задна позиция.

Изтриване в кръговата опашка

Стъпка 1:

  • Проверяваме дали опашката съдържа някакъв елемент.
  • Ако отпред == - 1, опашката е празна.

Стъпка 2:

  • Когато опашката не е празна и предният и задният указател сочат към един и същ индекс, тогава задайте front = -1 и back = -1  В противен случай, ако front == queue size-1, тогава front = 0.

Кръгла опашка

C ++ програма за вмъкване и изтриване в Circular Queue

// C or C++ program for insertion and 
// deletion in Circular Queue 
#include<bits/stdc++.h> 
using namespace std; 

struct Queue 
{ 
  // Initialize front and rear 
  int rear, front; 

  // Circular Queue 
  int size; 
  int *arr; 

  Queue(int s) 
  { 
  front = rear = -1; 
  size = s; 
  arr = new int[s]; 
  } 

  void enQueue(int value); 
  int deQueue(); 
  void displayQueue(); 
}; 


/* Function to create Circular queue */
void Queue::enQueue(int value) 
{ 
  if ((front == 0 && rear == size-1) || 
      (rear == (front-1)%(size-1))) 
  { 
    printf("\nQueue is Full"); 
    return; 
  } 

  else if (front == -1) /* Insert First Element */
  { 
    front = rear = 0; 
    arr[rear] = value; 
  } 

  else if (rear == size-1 && front != 0) 
  { 
    rear = 0; 
    arr[rear] = value; 
  } 

  else
  { 
    rear++; 
    arr[rear] = value; 
  } 
} 

// Function to delete element from Circular Queue 
int Queue::deQueue() 
{ 
  if (front == -1) 
  { 
    printf("\nQueue is Empty"); 
    return INT_MIN; 
  } 

  int data = arr[front]; 
  arr[front] = -1; 
  if (front == rear) 
  { 
    front = -1; 
    rear = -1; 
  } 
  else if (front == size-1) 
    front = 0; 
  else
    front++; 

  return data; 
} 

// Function displaying the elements 
// of Circular Queue 
void Queue::displayQueue() 
{ 
  if (front == -1) 
  { 
    printf("\nQueue is Empty"); 
    return; 
  } 
  printf("\nElements in Circular Queue are: "); 
  if (rear >= front) 
  { 
    for (int i = front; i <= rear; i++) 
      printf("%d ",arr[i]); 
  } 
  else
  { 
    for (int i = front; i < size; i++) 
      printf("%d ", arr[i]); 

    for (int i = 0; i <= rear; i++) 
      printf("%d ", arr[i]); 
  } 
} 

/* Driver of the program */
int main() 
{ 
  Queue q(5); 

  // Inserting elements in Circular Queue 
  q.enQueue(14); 
  q.enQueue(22); 
  q.enQueue(13); 
  q.enQueue(-6); 

  // Display elements present in Circular Queue 
  q.displayQueue(); 

  // Deleting elements from Circular Queue 
  printf("\nDeleted value = %d", q.deQueue()); 
  printf("\nDeleted value = %d", q.deQueue()); 

  q.displayQueue(); 

  q.enQueue(9); 
  q.enQueue(20); 
  q.enQueue(5); 

  q.displayQueue(); 

  q.enQueue(20); 
  return 0; 
} 
Elements in Circular Queue are: 14 22 13 -6 
Deleted value = 14
Deleted value = 22
Elements in Circular Queue are: 13 -6 
Elements in Circular Queue are: 13 -6 9 20 5 
Queue is Full

Java програма за вмъкване и изтриване в Circular Queue

// Java program for insertion and 
// deletion in Circular Queue 
import java.util.* ; 

class Solution 
{ 
  
// Structure of a Node 
static class Node 
{ 
  int data; 
  Node link; 
} 
  
static class Queue 
{ 
  Node front, rear; 
} 
  
// Function to create Circular queue 
static void enQueue(Queue q, int value) 
{ 
  Node temp = new Node(); 
  temp .data = value; 
  if (q .front == null) 
    q .front = temp; 
  else
    q .rear .link = temp; 
  
  q .rear = temp; 
  q .rear .link = q .front; 
} 
  
// Function to delete element from Circular Queue 
static int deQueue(Queue q) 
{ 
  if (q .front == null) 
  { 
    System.out.printf ("Queue is empty"); 
    return Integer.MIN_VALUE; 
  } 
  
  // If this is the last node to be deleted 
  int value; // Value to be dequeued 
  if (q .front == q .rear) 
  { 
    value = q .front .data; 
    q .front = null; 
    q .rear = null; 
  } 
  else // There are more than one nodes 
  { 
    Node temp = q .front; 
    value = temp .data; 
    q .front = q .front .link; 
    q .rear .link= q .front; 
  } 
  
  return value ; 
} 
  
// Function displaying the elements of Circular Queue 
static void displayQueue( Queue q) 
{ 
  Node temp = q .front; 
  System.out.printf("\nElements in Circular Queue are: "); 
  while (temp .link != q .front) 
  { 
    System.out.printf("%d ", temp .data); 
    temp = temp .link; 
  } 
  System.out.printf("%d", temp .data); 
} 
  
/* Driver of the program */
public static void main(String args[]) 
{ 
  // Create a queue and initialize front and rear 
  Queue q = new Queue(); 
  q .front = q .rear = null; 
  
  // Inserting elements in Circular Queue 
  enQueue(q, 14); 
  enQueue(q, 22); 
  enQueue(q, 6); 
  
  // Display elements present in Circular Queue 
  displayQueue(q); 
  
  // Deleting elements from Circular Queue 
  System.out.printf("\nDeleted value = %d", deQueue(q)); 
  System.out.printf("\nDeleted value = %d", deQueue(q)); 
  
  // Remaining elements in Circular Queue 
  displayQueue(q); 
  
  enQueue(q, 9); 
  enQueue(q, 20); 
  displayQueue(q); 
  
} 
}
Elements in Circular Queue are: 14 22 6
Deleted value = 14
Deleted value = 22
Elements in Circular Queue are: 6
Elements in Circular Queue are: 6 9 20

Сложност във времето

  1. enqueue (): O (1).
  2. dequeue (): O (1).

Приложение в реалния живот

  1. При планирането на процесора първо се изпълнява задачата, която е на първо място.
  2. Компютърно контролирана система за трафик използва кръгова опашка за контрол на трафика.

Препратки