Структура на данните за опашката и внедряване в Java, Python и C / C ++

В този урок ще научите какво представлява опашката. Също така ще намерите изпълнение на опашка в C, C ++, Java и Python.

Опашката е полезна структура от данни при програмирането. Подобно е на опашката за билети извън киносалона, където първият човек, който влиза в опашката, е първият човек, който получава билета.

Опашката следва правилото First In First Out (FIFO) - елементът, който влиза първо, е елементът, който излиза първи.

FIFO Представяне на опашката

В горното изображение, тъй като 1 е бил държан в опашката преди 2, той е първият, който също е премахнат от опашката. Той следва правилото FIFO .

От гледна точка на програмирането, поставянето на елементи в опашката се нарича enqueue , а премахването на елементи от опашката се нарича dequeue .

Можем да приложим опашката на всеки език за програмиране като C, C ++, Java, Python или C #, но спецификацията е почти същата.

Основни операции на опашката

Опашката е обект (абстрактна структура от данни - ADT), който позволява следните операции:

  • Опашка : Добавете елемент в края на опашката
  • Dequeue : Премахнете елемент от предната страна на опашката
  • IsEmpty : Проверете дали опашката е празна
  • IsFull : Проверете дали опашката е пълна
  • Погледнете : Получете стойността на предната част на опашката, без да я премахвате

Работа на опашката

Операциите на опашката работят както следва:

  • два указателя отпред и отзад
  • FRONT проследява първия елемент от опашката
  • REAR проследяване на последния елемент от опашката
  • първоначално задайте стойност на FRONT и REAR на -1

Операция на опашката

  • проверете дали опашката е пълна
  • за първия елемент задайте стойността на FRONT на 0
  • увеличете индекса REAR с 1
  • добавете новия елемент в позицията, посочена от REAR

Операция за отстраняване на опашката

  • проверете дали опашката е празна
  • връща стойността, посочена от FRONT
  • увеличете индекса FRONT с 1
  • за последния елемент нулирайте стойностите на FRONT и REAR на -1
Операции за опашка и отмяна

Реализации на опашката в Python, Java, C и C ++

Обикновено използваме масиви за реализиране на опашки в Java и C / ++. В случая на Python използваме списъци.

Python Java C C ++
 # Queue implementation in Python class Queue: def __init__(self): self.queue = () # Add an element def enqueue(self, item): self.queue.append(item) # Remove an element def dequeue(self): if len(self.queue) < 1: return None return self.queue.pop(0) # Display the queue def display(self): print(self.queue) def size(self): return len(self.queue) q = Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.display() q.dequeue() print("After removing an element") q.display() 
 // Queue implementation in Java public class Queue ( int SIZE = 5; int items() = new int(SIZE); int front, rear; Queue() ( front = -1; rear = -1; ) boolean isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) return false; ) boolean isEmpty() ( if (front == -1) return true; else return false; ) void enQueue(int element) ( if (isFull()) ( System.out.println("Queue is full"); ) else ( if (front == -1) front = 0; rear++; items(rear) = element; System.out.println("Inserted " + element); ) ) int deQueue() ( int element; if (isEmpty()) ( System.out.println("Queue is empty"); return (-1); ) else ( element = items(front); if (front>= rear) ( front = -1; rear = -1; ) /* Q has only one element, so we reset the queue after deleting it. */ else ( front++; ) System.out.println("Deleted -> " + element); return (element); ) ) void display() ( /* Function to display elements of Queue */ int i; if (isEmpty()) ( System.out.println("Empty Queue"); ) else ( System.out.println("Front index-> " + front); System.out.println("Items -> "); for (i = front; i " + rear); ) ) public static void main(String() args) ( Queue q = new Queue(); // deQueue is not possible on empty queue q.deQueue(); // enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // 6th element can't be added to because the queue is full q.enQueue(6); q.display(); // deQueue removes element entered first i.e. 1 q.deQueue(); // Now we have just 4 elements q.display(); ) )
 // Queue implementation in C #include #define SIZE 5 void enQueue(int); void deQueue(); void display(); int items(SIZE), front = -1, rear = -1; int main() ( //deQueue is not possible on empty queue deQueue(); //enQueue 5 elements enQueue(1); enQueue(2); enQueue(3); enQueue(4); enQueue(5); // 6th element can't be added to because the queue is full enQueue(6); display(); //deQueue removes element entered first i.e. 1 deQueue(); //Now we have just 4 elements display(); return 0; ) void enQueue(int value) ( if (rear == SIZE - 1) printf("Queue is Full!!"); else ( if (front == -1) front = 0; rear++; items(rear) = value; printf("Inserted -> %d", value); ) ) void deQueue() ( if (front == -1) printf("Queue is Empty!!"); else ( printf("Deleted : %d", items(front)); front++; if (front> rear) front = rear = -1; ) ) // Function to print the queue void display() ( if (rear == -1) printf("Queue is Empty!!!"); else ( int i; printf("Queue elements are:"); for (i = front; i <= rear; i++) printf("%d ", items(i)); ) printf(""); )
 // Queue implementation in C++ #include #define SIZE 5 using namespace std; class Queue ( private: int items(SIZE), front, rear; public: Queue() ( front = -1; rear = -1; ) bool isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) return false; ) bool isEmpty() ( if (front == -1) return true; else return false; ) void enQueue(int element) ( if (isFull()) ( cout << "Queue is full"; ) else ( if (front == -1) front = 0; rear++; items(rear) = element; cout << endl << "Inserted " << element << endl; ) ) int deQueue() ( int element; if (isEmpty()) ( cout << "Queue is empty" <= rear) ( front = -1; rear = -1; ) /* Q has only one element, so we reset the queue after deleting it. */ else ( front++; ) cout << endl < " << element << endl; return (element); ) ) void display() ( /* Function to display elements of Queue */ int i; if (isEmpty()) ( cout << endl << "Empty Queue" << endl; ) else ( cout << endl < " << front; cout << endl < "; for (i = front; i <= rear; i++) cout << items(i) << " "; cout << endl < " << rear << endl; ) ) ); int main() ( Queue q; //deQueue is not possible on empty queue q.deQueue(); //enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // 6th element can't be added to because the queue is full q.enQueue(6); q.display(); //deQueue removes element entered first i.e. 1 q.deQueue(); //Now we have just 4 elements q.display(); return 0; )

Ограничения на опашката

Както можете да видите на изображението по-долу, след малко поставяне в опашка и отпадане, размерът на опашката е намален.

Ограничение на опашката

И ние можем да добавяме индекси 0 и 1 само когато опашката е нулирана (когато всички елементи са деактивирани).

След като REAR достигне последния индекс, ако можем да съхраняваме допълнителни елементи в празните пространства (0 и 1), можем да използваме празните пространства. Това се реализира от модифицирана опашка, наречена кръгова опашка.

Анализ на сложността

Сложността на операциите за опашка и отлагане в опашка с помощта на масив е O(1).

Приложения на опашката

  • Планиране на процесора, Дисково планиране
  • Когато данните се прехвърлят асинхронно между два процеса, опашката се използва за синхронизация. Например: IO буфери, тръби, файл IO и т.н.
  • Обработка на прекъсвания в системи в реално време.
  • Телефонните системи на Call Center използват Опашки, за да задържат хората, които им се обаждат по ред.

Препоръчителни четива

  • Видове опашка
  • Кръгла опашка
  • Deque Структура на данните
  • Опашка с приоритет

Интересни статии...