queue data structure c with illustration
Кратко въведение в опашката в C ++ с илюстрация.
Опашката е основна структура от данни, точно като стека. За разлика от стека, който използва подхода LIFO, опашката използва подхода FIFO (първи вход, първи изход). При този подход първият елемент, който се добавя към опашката, е първият елемент, който се премахва от опашката. Подобно на Stack, опашката също е линейна структура от данни.
как да отворите dat файла в pdf
В реална аналогия можем да си представим автобусна опашка, където пътниците чакат автобуса на опашка или линия. Първият пътник в линията влиза в автобуса първи, тъй като този пътник е този, който е дошъл първи.
=> Прочетете Популярната серия за обучение на C ++ тук.
Какво ще научите:
Опашка в C ++
От гледна точка на софтуера, опашката може да се разглежда като набор или колекция от елементи, както е показано по-долу. Елементите са подредени линейно.
Имаме два края, т.е. „отпред“ и „отзад“ на опашката. Когато опашката е празна, тогава и двата указателя са зададени на -1.
„Задният“ краен указател е мястото, откъдето елементите се вмъкват в опашката. Операцията по добавяне / вмъкване на елементи в опашката се нарича „опашка“.
Крайният указател „преден“ е мястото, от което елементите се отстраняват от опашката. Операцията за премахване / изтриване на елементи от опашката се нарича “dequeue”.
Когато стойността на задния указател е размер-1, тогава казваме, че опашката е пълна. Когато предната част е нула, тогава опашката е празна.
Основни операции
Структурата на данните за опашката включва следните операции:
- EnQueue: Добавя елемент към опашката. Добавянето на елемент към опашката винаги се извършва в задната част на опашката.
- DeQueue: Премахва елемент от опашката. Елементът се премахва или отстранява на опашка винаги от предната страна на опашката.
- празно е: Проверява дали опашката е празна.
- е пълен: Проверява дали опашката е пълна.
- надникнете: Получава елемент в предната част на опашката, без да го премахва.
Опашка
В този процес се изпълняват следните стъпки:
- Проверете дали опашката е пълна.
- Ако е пълно, създайте грешка при преливане и излезте.
- В противен случай, увеличете ‘отзад’.
- Добавете елемент към местоположението, посочено от ‘отзад’.
- Върнете успеха.
Отмяна
Операцията за отмяна се състои от следните стъпки:
- Проверете дали опашката е празна.
- Ако е празно, покажете грешка при подтичане и излезте.
- В противен случай елементът за достъп е посочен с „front“.
- Увеличаване на „отпред“, за да сочи към следващите достъпни данни.
- Върнете успеха.
След това ще видим подробна илюстрация на операциите за вмъкване и изтриване в опашката.
Илюстрация
Това е празна опашка и по този начин имаме задна и празна настройка на -1.
След това добавяме 1 към опашката и в резултат задният указател се придвижва напред с едно място.
На следващата фигура добавяме елемент 2 към опашката, като преместваме задния указател напред с още едно увеличение.
На следващата фигура добавяме елемент 3 и преместваме задния показалец с 1.
В този момент задният указател има стойност 2, докато предният показалец е на 0тиместоположение.
След това изтриваме елемента, посочен от предния указател. Тъй като предният указател е на 0, елементът, който се изтрива, е 1.
По този начин първият елемент, въведен в опашката, т.е. 1, се оказва първият елемент, отстранен от опашката. В резултат на това, след първото отменяне, предният указател сега ще бъде преместен напред t0 на следващото място, което е 1.
Внедряване на масив за опашка
Нека приложим структурата на данните за опашката, използвайки C ++.
#include #define MAX_SIZE 5 using namespace std; class Queue { private: int myqueue(MAX_SIZE), front, rear; public: Queue(){ front = -1; rear = -1; } boolisFull(){ if(front == 0 && rear == MAX_SIZE - 1){ return true; } return false; } boolisEmpty(){ if(front == -1) return true; else return false; } void enQueue(int value){ if(isFull()){ cout << endl<< 'Queue is full!!'; } else { if(front == -1) front = 0; rear++; myqueue(rear) = value; cout << value << ' '; } } int deQueue(){ int value; if(isEmpty()){ cout << 'Queue is empty!!' <= rear){ //only one element in queue front = -1; rear = -1; } else { front++; } cout << endl < ' << value << ' from myqueue'; return(value); } } /* Function to display elements of Queue */ void displayQueue() { int i; if(isEmpty()) { cout << endl << 'Queue is Empty!!' << endl; } else { cout << endl << 'Front = ' << front; cout << endl << 'Queue elements : '; for(i=front; i<=rear; i++) cout << myqueue(i) << ' '; cout << endl << 'Rear = ' << rear << endl; } } }; int main() { Queue myq; myq.deQueue(); //deQueue cout<<'Queue created:'< queue is full myq.enQueue(60); myq.displayQueue(); //deQueue =>removes 10 myq.deQueue(); //queue after dequeue myq.displayQueue(); return 0; }
Изход:
Опашката е празна !!
Създадена опашка:
10 20 30 40 50
Опашката е пълна !!
Отпред = 0
Елементи на опашката: 10 20 30 40 50
Задна = 4
Изтрито => 10 от myqueue
Отпред = 1
Елементи на опашката: 20 30 40 50
Задна = 4
Горното изпълнение показва опашката, представена като масив. Посочваме max_size за масива. Също така дефинираме операциите за опашка и отмяна, както и операциите isFull и isEmpty.
По-долу е дадено изпълнението на Java на структурата от данни на опашката.
// A class representing a queue class Queue { int front, rear, size; int max_size; int myqueue(); public Queue(int max_size) { this.max_size = max_size; front = this.size = 0; rear = max_size - 1; myqueue = new int(this.max_size); } //if size = max_size , queue is full boolean isFull(Queue queue) { return (queue.size == queue.max_size); } // size = 0, queue is empty boolean isEmpty(Queue queue) { return (queue.size == 0); } // enqueue - add an element to the queue void enqueue( int item) { if (isFull(this)) return; this.rear = (this.rear + 1)%this.max_size; this.myqueue(this.rear) = item; this.size = this.size + 1; System.out.print(item + ' ' ); } // dequeue - remove an elment from the queue int dequeue() { if (isEmpty(this)) return Integer.MIN_VALUE; int item = this.myqueue(this.front); this.front = (this.front + 1)%this.max_size; this.size = this.size - 1; return item; } // move to front of the queue int front() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.myqueue(this.front); } // move to the rear of the queue int rear() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.myqueue(this.rear); } } // main class class Main { public static void main(String() args) { Queue queue = new Queue(1000); System.out.println('Queue created as:'); queue.enqueue(10); queue.enqueue(20); queue.enqueue(30); queue.enqueue(40); System.out.println('
Element ' + queue.dequeue() + ' dequeued from queue
'); System.out.println('Front item is ' + queue.front()); System.out.println('Rear item is ' + queue.rear()); } }
Изход:
Опашката е създадена като:
10 20 30 40
Елемент 10, деактивиран от опашката
Предната позиция е 20
Задният елемент е 40
Гореизпълнението е подобно на изпълнението на C ++.
След това нека приложим опашката в C ++, като използваме свързан списък.
Внедряване на свързан списък за опашка:
#include using namespace std; struct node { int data; struct node *next; }; struct node* front = NULL; struct node* rear = NULL; struct node* temp; void Insert(int val) { if (rear == NULL) { rear = new node; rear->next = NULL; rear->data = val; front = rear; } else { temp=new node; rear->next = temp; temp->data = val; temp->next = NULL; rear = temp; } } void Delete() { temp = front; if (front == NULL) { cout<<'Queue is empty!!'next; cout<<'Element deleted from queue is : ' Изход:
Опашка създадена:
10 20 30 40 50
Изтритият от опашката елемент е: 10
Опашка след едно изтриване:
20 30 40 50
как отваряте json файлове
Stack Vs. Опашка
Стековете и опашките са вторични структури от данни, които могат да се използват за съхраняване на данни. Те могат да бъдат програмирани с помощта на първичните структури от данни като масиви и свързани списъци. След като обсъдихме подробно и двете структури от данни, е време да обсъдим основните разлики между тези две структури от данни.
Стекове Опашки Използва LIFO (Last in, First out) подход. Използва FIFO (First in, First out) подход. Елементите се добавят или изтриват само от единия край, наречен “Top” на стека. Елементите се добавят от „Задния“ край на опашката и се премахват от „предната част“ на опашката. Основните операции за стека са “push” и “Pop”. Основните операции за опашката са „enqueue“ и „dequeue“. Можем да правим всички операции в стека, като поддържаме само един указател за достъп до горната част на стека. В опашките трябва да поддържаме два указателя, един за достъп до предната част на опашката и вторият за достъп до задната част на опашката. Стекът се използва най-вече за решаване на рекурсивни проблеми. Опашките се използват за решаване на проблеми, свързани с подредената обработка.
Приложения на опашката
Нека обсъдим различните приложения на структурата на данните за опашката по-долу.
- Структурата на данните за опашката се използва в различни процесори и дисково планиране. Тук имаме множество задачи, изискващи CPU или диск едновременно. Времето на процесора или диска е планирано за всяка задача с помощта на опашка.
- Опашката може да се използва и за натрупване на печат, при което броят на заданията за печат се поставя в опашка.
- Обработката на прекъсванията в системи в реално време се извършва чрез използване на структура от данни на опашката. Прекъсванията се обработват в реда, в който пристигат.
- Първо по ширина търсене, при което съседните възли на дърво се обхождат, преди да се премине към следващото ниво, използва опашка за изпълнение.
- Телефонните системи на телефонния център използват опашки за задържане на повикванията, докато представителите на услугата не отговорят на тях.
Като цяло можем да кажем, че структурата на данните за опашката се използва винаги, когато изискваме ресурсите или елементите да бъдат обслужвани в реда, в който пристигат, т.е.
Заключение
Опашката е FIFO (First In, First Out) структура от данни, която се използва най-вече в ресурси, където се изисква планиране. Той има два указателя отзад и отпред в два края и те се използват за вмъкване на елемент и съответно премахване на елемент към / от опашката.
В следващия урок ще научим за някои от разширенията на опашката като приоритетна опашка и кръгова опашка.
=> Вижте тук, за да разгледате пълния списък с уроци за C ++.
Препоръчително четене
- Структура на данните за приоритетна опашка в C ++ с илюстрация
- Приоритетна опашка в STL
- Структура на данните за стека в C ++ с илюстрация
- Структура на данните от кръгов обвързан списък в C ++ с илюстрация
- Свързана списъчна структура на данните в C ++ с илюстрация
- Структура на данните от списъка с двойно свързване в C ++ с илюстрация
- Въведение в структурите на данни в C ++
- Параметризиране на данни на JMeter, използвайки дефинирани от потребителя променливи