В компютърните науки опашката е линейна структура от данни, където компонентите се поставят в единия край и се премахват от другия край според принципа „първи влязъл, първи излязъл“ (FIFO). Тази структура от данни може да се използва за контролиране на последователност от действия или за съхраняване на данни. C е компютърен език с възможност за опашка, включена под формата на масиви или свързани списъци.
Характеристики:
- Опашката е вид линейна структура от данни, която може да бъде конструирана с масив или свързан списък.
- Елементите се преместват в задната част на опашката, докато се премахват отпред.
- Enqueue (добавяне на елемент отзад) и dequeue (премахване на елемент отпред) са две операции на опашка.
- Когато елементите се добавят и премахват често, опашката може да бъде изградена като кръгова опашка, за да се предотврати загубата на памет.
Използване на масив:
За да реализирате опашка в C, използвайки масив, първо дефинирайте максималния размер на опашката и декларирайте масив с този размер. Предните и задните цели числа бяха съответно зададени на 1. Предната променлива представлява предния елемент на опашката, а задната променлива представлява задния елемент.
Преди да натиснем новия елемент до крайната позиция на опашката, трябва да увеличим променливата back с 1. Сега опашката е пълна и не могат да се добавят други допълнителни елементи, когато задната позиция достигне максималния капацитет на опашката. Добавяме елемент в началото на опашката и увеличаваме предната променлива с единица само за да премахнем елемент от опашката. Ако предната и задната позиции са равни и повече компоненти не могат да бъдат изтрити, следователно можем да кажем, че опашката е празна.
По-долу е екземпляр на опашка, написана на C, която използва масив:
Език за програмиране C:
arraylist в java
#define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf('Queue is full'); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front > rear) { printf('Queue is empty'); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } Резултатът от кода ще бъде:
Изход:
10 20 30 Queue is empty-1
Обяснение:
- Първо, поставяме три елемента 10, 20 и 30 в опашката.
- След това премахваме опашката и отпечатваме предния елемент на опашката, който е 10.
- След това премахваме опашката и отново отпечатваме предния елемент на опашката, който е 20.
- След това премахваме опашката и отново отпечатваме предния елемент на опашката, който е 30.
- Накрая правим деопашка от празна опашка, която извежда „Опашката е празна“ и връща -1.
Използване на свързан списък:
Друг алтернативен подход за конструиране на опашка в езика за програмиране C е използването на свързан списък. Всеки от възлите в опашката се изразява с помощта на този метод чрез възел, който съдържа стойността на елемента и указател към следващия възел в опашката. За да се следи съответно първият и последният възел в опашката, се използват предни и задни указатели.
Създаваме нов възел със стойността на елемента и задаваме неговия следващ указател на NULL, за да добавим елемент към опашката. Към новия възел задаваме предния и задния указател, ако опашката е празна. Ако не, актуализираме задния указател и задаваме следващия указател на стария заден възел да сочи към новия възел.
Когато изтривате възел от опашката, първо се изтрива предходният възел, след това предният указател се актуализира към следващия възел в опашката и накрая се освобождава паметта, която премахнатият възел е заемал. Ако предният указател е NULL след премахване, опашката е празна.
Ето пример за опашка, реализирана в C с помощта на свързан списък:
Език за програмиране C:
#include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = element; new_node->next = NULL; if (front == NULL && rear == NULL) { front = rear = new_node; return; } rear->next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf('Queue is empty'); return -1; } struct Node* temp = front; int element = temp->data; if (front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } Резултатът от кода ще бъде:
Изход:
10 20 30 Queue is empty-1
Обяснение:
- Първо, поставяме три елемента 10, 20 и 30 в опашката.
- След това премахваме опашката и отпечатваме предния елемент на опашката, който е 10.
- След това премахваме опашката и отново отпечатваме предния елемент на опашката, който е 20.
- След това премахваме опашката и отново отпечатваме предния елемент на опашката, който е 30.
- Накрая се опитваме да излезем от празната опашка, което отпечатва съобщението „Опашката е празна“ и връща -1.
Предимства:
- Опашките са особено полезни за прилагане на алгоритми, които изискват елементите да се обработват в точна последователност, като търсене в ширина и планиране на задачи.
- Тъй като операциите с опашка имат времева сложност O(1), те могат да се изпълняват бързо дори на огромни опашки.
- Опашките са особено гъвкави, тъй като могат просто да бъдат реализирани с помощта на масив или свързан списък.
Недостатъци:
- Опашката, за разлика от стека, не може да бъде конструирана с един указател, което прави изпълнението на опашка малко по-ангажирано.
- Ако опашката е конструирана като масив, тя може скоро да се запълни, ако се добавят твърде много елементи, което води до проблеми с производителността или евентуално до срив.
- Когато се използва свързан списък за реализиране на опашката, натоварването на паметта на всеки възел може да бъде значително, особено за малки елементи.
Заключение:
Приложенията, които използват опашки, ключова структура от данни, включват операционни системи, мрежи и игри, за да назовем само няколко. Те са идеални за алгоритми, които трябва да обработват елементи в определен ред, тъй като са лесни за създаване с помощта на масив или свързан списък. Опашките обаче имат недостатъци, които трябва да се имат предвид при избора на структура от данни за конкретно приложение, като консумация на памет и сложност на изпълнението.