WPROWADZENIE I IMPLEMENTACJA TABLICY KOLEJEK - TECHCODEVIEW.COM

Podobnie jak kolejka, jest liniową strukturą danych, która ma określoną kolejność wykonywania operacji przechowywania danych. Kolejność jest taka: „pierwsze weszło, pierwsze wyszło”. (FIFO) . Kolejkę można sobie wyobrazić jako kolejkę osób czekających na coś w kolejności sekwencyjnej, zaczynającej się od początku kolejki. Jest to uporządkowana lista, na której wstawiania dokonuje się na jednym końcu, zwanym tyłem, a usuwania dokonuje się na drugim końcu, zwanym przodem. Dobrym przykładem kolejki jest dowolna kolejka konsumentów do zasobu, w której konsument, który przyszedł pierwszy, jest obsługiwany jako pierwszy.
Różnica między stosami i kolejkami polega na usuwaniu. Ze stosu usuwamy element ostatnio dodany; w kolejce usuwamy element dodany najpóźniej.

Zalecana praktykaZaimplementuj kolejkę przy użyciu tablicyWypróbuj!

Kolejka Struktura danych

Podstawowe operacje na kolejce:

enqueue(): Wstawia element na końcu kolejki, tj. na jej końcu. dequeue(): Ta operacja usuwa i zwraca element znajdujący się na początku kolejki. front(): Ta operacja zwraca element z przodu bez jego usuwania. rear(): Ta operacja zwraca element na końcu bez jego usuwania. isEmpty(): Ta operacja wskazuje, czy kolejka jest pusta, czy nie. isFull(): Ta operacja wskazuje, czy kolejka jest pełna, czy nie. size(): Ta operacja zwraca rozmiar kolejki, tj. całkowitą liczbę elementów, które zawiera.

Rodzaje kolejek:

Okrągła kolejka : W kolejce kołowej element kolejki działa jak okrągły pierścień. Działanie kolejki okrężnej jest podobne do kolejki liniowej, z tą różnicą, że ostatni element jest połączony z pierwszym elementem. Jego zaletą jest lepsze wykorzystanie pamięci. Dzieje się tak dlatego, że jeśli jest puste miejsce, tj. jeśli na określonej pozycji w kolejce nie ma żadnego elementu, wówczas element można łatwo dodać na tej pozycji, korzystając z pojemności modulo ( %N ).
Kolejka priorytetowa : Ta kolejka jest specjalnym typem kolejki. Jego specjalnością jest to, że porządkuje elementy w kolejce w oparciu o pewien priorytet. Priorytetem może być coś, w czym element o najwyższej wartości ma priorytet, więc tworzy kolejkę z malejącą kolejnością wartości. Priorytet może być również taki, że element o najniższej wartości otrzyma najwyższy priorytet, co z kolei spowoduje utworzenie kolejki o rosnącej kolejności wartości. We wstępnie zdefiniowanej kolejce priorytetów C++ nadaje priorytet najwyższej wartości, podczas gdy Java daje priorytet najniższej wartości.
Odpowiednio : Usuwanie z kolejki jest również znane jako kolejka z podwójnym zakończeniem. Jak sama nazwa wskazuje, podwójne zakończenie oznacza, że element można wstawić lub usunąć z obu końców kolejki, w przeciwieństwie do innych kolejek, w których można to zrobić tylko z jednego końca. Ze względu na tę właściwość może nie spełniać właściwości First In First Out.

Zastosowania kolejki:

Kolejka jest używana, gdy rzeczy nie muszą zostać przetworzone natychmiast, ale muszą zostać przetworzone F pierwszy I N F pierwszy O w takiej kolejności Wyszukiwanie wszerz . Ta właściwość Queue sprawia, że jest ona również przydatna w następujących scenariuszach.

Gdy zasób jest współdzielony przez wielu konsumentów. Przykłady obejmują planowanie procesora, planowanie dysku.

Implementacja tablicy kolejki:

Aby zaimplementować kolejkę, musimy śledzić dwa indeksy, przedni i tylny. Kolejkujemy przedmiot z tyłu i usuwamy z kolejki z przodu. Jeśli po prostu zwiększymy indeksy przód i tył, mogą pojawić się problemy, przód może dotrzeć do końca tablicy. Rozwiązaniem tego problemu jest zwiększenie przodu i tyłu w sposób okrężny.

Kroki w kolejce:

Sprawdź, czy kolejka jest pełna, czy nie
Jeśli jest pełny, wydrukuj przepełnienie i wyjdź
Jeśli kolejka nie jest pełna, zwiększ ogon i dodaj element

Kroki usuwania z kolejki:

Sprawdź, czy kolejka jest pusta, czy nie
jeśli jest pusty, wydrukuj niedomiar i wyjdź
jeśli nie jest pusty, wydrukuj element na głowicy i zwiększ głowicę

Poniżej znajduje się program realizujący powyższą operację na kolejce

C++

tablica c ciąg

// CPP program for array> // implementation of queue> #include> using> namespace> std;> // A structure to represent a queue> class> Queue {> public>:> >int> front, rear, size;> >unsigned capacity;> >int>* array;> };> // function to create a queue> // of given capacity.> // It initializes size of queue as 0> Queue* createQueue(unsigned capacity)> {> >Queue* queue =>new> Queue();> >queue->pojemność = pojemność;> >queue->przód = kolejka->rozmiar = 0;> >// This is important, see the enqueue> >queue->tył = pojemność - 1;> >queue->tablica =>new> int>[queue->pojemność];> >return> queue;> }> // Queue is full when size> // becomes equal to the capacity> int> isFull(Queue* queue)> {> >return> (queue->rozmiar == kolejka->pojemność);> }> // Queue is empty when size is 0> int> isEmpty(Queue* queue)> {> >return> (queue->rozmiar == 0);> }> // Function to add an item to the queue.> // It changes rear and size> void> enqueue(Queue* queue,>int> item)> {> >if> (isFull(queue))> >return>;> >queue->tył = (kolejka->tył + 1)> >% queue->pojemność;> >queue->tablica[kolejka->tył] = element;> >queue->rozmiar = kolejka->rozmiar + 1;> >cout << item <<>

' enqueued to queue
'>

;> }> // Function to remove an item from queue.> // It changes front and size> int> dequeue(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >int> item = queue->tablica[kolejka->przód];> >queue->przód = (kolejka->przód + 1)> >% queue->pojemność;> >queue->rozmiar = kolejka->rozmiar - 1;> >return> item;> }> // Function to get front of queue> int> front(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->tablica[kolejka->przód];> }> // Function to get rear of queue> int> rear(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->tablica[kolejka->tył];> }> // Driver code> int> main()> {> >Queue* queue = createQueue(1000);> >enqueue(queue, 10);> >enqueue(queue, 20);> >enqueue(queue, 30);> >enqueue(queue, 40);> >cout << dequeue(queue)> ><<>

' dequeued from queue
'>

;> >cout <<>'Front item is '> ><< front(queue) << endl;> >cout <<>'Rear item is '> ><< rear(queue) << endl;> >return> 0;> }> // This code is contributed by rathbhupendra>

C

// C program for array implementation of queue> #include> #include> #include> // A structure to represent a queue> struct> Queue {> >int> front, rear, size;> >unsigned capacity;> >int>* array;> };> // function to create a queue> // of given capacity.> // It initializes size of queue as 0> struct> Queue* createQueue(unsigned capacity)> {> >struct> Queue* queue = (>struct> Queue*)>malloc>(> >sizeof>(>struct> Queue));> >queue->pojemność = pojemność;> >queue->przód = kolejka->rozmiar = 0;> >// This is important, see the enqueue> >queue->tył = pojemność - 1;> >queue->tablica = (>int>*)>malloc>(> >queue->pojemność *>sizeof>(>int>));> >return> queue;> }> // Queue is full when size becomes> // equal to the capacity> int> isFull(>struct> Queue* queue)> {> >return> (queue->rozmiar == kolejka->pojemność);> }> // Queue is empty when size is 0> int> isEmpty(>struct> Queue* queue)> {> >return> (queue->rozmiar == 0);> }> // Function to add an item to the queue.> // It changes rear and size> void> enqueue(>struct> Queue* queue,>int> item)> {> >if> (isFull(queue))> >return>;> >queue->tył = (kolejka->tył + 1)> >% queue->pojemność;> >queue->tablica[kolejka->tył] = element;> >queue->rozmiar = kolejka->rozmiar + 1;> >printf>(>

'%d enqueued to queue
'>

, item);> }> // Function to remove an item from queue.> // It changes front and size> int> dequeue(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >int> item = queue->tablica[kolejka->przód];> >queue->przód = (kolejka->przód + 1)> >% queue->pojemność;> >queue->rozmiar = kolejka->rozmiar - 1;> >return> item;> }> // Function to get front of queue> int> front(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->tablica[kolejka->przód];> }> // Function to get rear of queue> int> rear(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->tablica[kolejka->tył];> }> // Driver program to test above functions./> int> main()> {> >struct> Queue* queue = createQueue(1000);> >enqueue(queue, 10);> >enqueue(queue, 20);> >enqueue(queue, 30);> >enqueue(queue, 40);> >printf>(>

'%d dequeued from queue

'>

,> >dequeue(queue));> >printf>(>

'Front item is %d
'>

, front(queue));> >printf>(>

'Rear item is %d
'>

, rear(queue));> >return> 0;> }>

co to jest ul

Jawa

// Java program for array> // implementation of queue> // A class to represent a queue> class> Queue {> >int> front, rear, size;> >int> capacity;> >int> array[];> >public> Queue(>int> capacity)> >{> >this>.capacity = capacity;> >front =>this>.size =>0>;> >rear = capacity ->1>;> >array =>new> int>[>this>.capacity];> >}> >// Queue is full when size becomes> >// equal to the capacity> >boolean> isFull(Queue queue)> >{> >return> (queue.size == queue.capacity);> >}> >// Queue is empty when size is 0> >boolean> isEmpty(Queue queue)> >{> >return> (queue.size ==>0>);> >}> >// Method to add an item to the queue.> >// It changes rear and size> >void> enqueue(>int> item)> >{> >if> (isFull(>this>))> >return>;> >this>.rear = (>this>.rear +>1>)> >%>this>.capacity;> >this>.array[>this>.rear] = item;> >this>.size =>this>.size +>1>;> >System.out.println(item> >+>' enqueued to queue'>);> >}> >// Method to remove an item from queue.> >// It changes front and size> >int> dequeue()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >int> item =>this>.array[>this>.front];> >this>.front = (>this>.front +>1>)> >%>this>.capacity;> >this>.size =>this>.size ->1>;> >return> item;> >}> >// Method to get front of queue> >int> front()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >return> this>.array[>this>.front];> >}> >// Method to get rear of queue> >int> rear()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >return> this>.array[>this>.rear];> >}> }> // Driver class> public> class> Test {> >public> static> void> main(String[] args)> >{> >Queue queue =>new> Queue(>1000>);> >queue.enqueue(>10>);> >queue.enqueue(>20>);> >queue.enqueue(>30>);> >queue.enqueue(>40>);> >System.out.println(queue.dequeue()> >+>

' dequeued from queue
'>

);> >System.out.println(>'Front item is '> >+ queue.front());> >System.out.println(>'Rear item is '> >+ queue.rear());> >}> }> // This code is contributed by Gaurav Miglani>

Python3

mapowanie w maszynopisie

# Python3 program for array implementation of queue> # Class Queue to represent a queue> class> Queue:> ># __init__ function> >def> __init__(>self>, capacity):> >self>.front>=> self>.size>=> 0> >self>.rear>=> capacity>->1> >self>.Q>=> [>None>]>*>capacity> >self>.capacity>=> capacity> > ># Queue is full when size becomes> ># equal to the capacity> >def> isFull(>self>):> >return> self>.size>=>=> self>.capacity> > ># Queue is empty when size is 0> >def> isEmpty(>self>):> >return> self>.size>=>=> 0> ># Function to add an item to the queue.> ># It changes rear and size> >def> EnQueue(>self>, item):> >if> self>.isFull():> >print>(>'Full'>)> >return> >self>.rear>=> (>self>.rear>+> 1>)>%> (>self>.capacity)> >self>.Q[>self>.rear]>=> item> >self>.size>=> self>.size>+> 1> >print>(>'% s enqueued to queue'> %> str>(item))> ># Function to remove an item from queue.> ># It changes front and size> >def> DeQueue(>self>):> >if> self>.isEmpty():> >print>(>'Empty'>)> >return> > >print>(>'% s dequeued from queue'> %> str>(>self>.Q[>self>.front]))> >self>.front>=> (>self>.front>+> 1>)>%> (>self>.capacity)> >self>.size>=> self>.size>->1> > ># Function to get front of queue> >def> que_front(>self>):> >if> self>.isEmpty():> >print>(>'Queue is empty'>)> >print>(>'Front item is'>,>self>.Q[>self>.front])> > ># Function to get rear of queue> >def> que_rear(>self>):> >if> self>.isEmpty():> >print>(>'Queue is empty'>)> >print>(>'Rear item is'>,>self>.Q[>self>.rear])> # Driver Code> if> __name__>=>=> '__main__'>:> >queue>=> Queue(>30>)> >queue.EnQueue(>10>)> >queue.EnQueue(>20>)> >queue.EnQueue(>30>)> >queue.EnQueue(>40>)> >queue.DeQueue()> >queue.que_front()> >queue.que_rear()>

stos Javy

C#

// C# program for array implementation of queue> using> System;> namespace> GeeksForGeeks {> // A class to represent a linearqueue> class> Queue {> >private> int>[] ele;> >private> int> front;> >private> int> rear;> >private> int> max;> >public> Queue(>int> size)> >{> >ele =>new> int>[size];> >front = 0;> >rear = -1;> >max = size;> >}> >// Function to add an item to the queue.> >// It changes rear and size> >public> void> enqueue(>int> item)> >{> >if> (rear == max - 1) {> >Console.WriteLine(>'Queue Overflow'>);> >return>;> >}> >else> {> >ele[++rear] = item;> >}> >}> >// Function to remove an item from queue.> >// It changes front and size> >public> int> dequeue()> >{> >if> (front == rear + 1) {> >Console.WriteLine(>'Queue is Empty'>);> >return> -1;> >}> >else> {> >Console.WriteLine(ele[front] +>' dequeued from queue'>);> >int> p = ele[front++];> >Console.WriteLine();> >Console.WriteLine(>'Front item is {0}'>, ele[front]);> >Console.WriteLine(>'Rear item is {0} '>, ele[rear]);> >return> p;> >}> >}> >// Function to print queue.> >public> void> printQueue()> >{> >if> (front == rear + 1) {> >Console.WriteLine(>'Queue is Empty'>);> >return>;> >}> >else> {> >for> (>int> i = front; i <= rear; i++) {> >Console.WriteLine(ele[i] +>' enqueued to queue'>);> >}> >}> >}> }> // Driver code> class> Program {> >static> void> Main()> >{> >Queue Q =>new> Queue(5);> >Q.enqueue(10);> >Q.enqueue(20);> >Q.enqueue(30);> >Q.enqueue(40);> >Q.printQueue();> >Q.dequeue();> >}> }> }>

JavaScript

> // Queue class> class Queue> {> >// Array is used to implement a Queue> >constructor()> >{> >this>.items = [];> >}> >isEmpty()> >{> >// return true if the queue is empty.> >return> this>.items.length == 0;> >}> >enqueue(element)> >{> >// adding element to the queue> >this>.items.push(element);> >document.write(element +>' enqueued to queue '>);> >}> >dequeue()> >{> >// removing element from the queue> >// returns underflow when called> >// on empty queue> >if>(>this>.isEmpty())> >return> 'Underflow '>;> >return> this>.items.shift();> >}> >front()> >{> >// returns the Front element of> >// the queue without removing it.> >if>(>this>.isEmpty())> >return> 'No elements in Queue '>;> >return> this>.items[0];> >}> >rear()> >{> >// returns the Rear element of> >// the queue without removing it.> >if>(>this>.isEmpty())> >return> 'No elements in Queue '>;> >return> this>.items[>this>.items.length-1];> >}> }> // creating object for queue class> var> queue =>new> Queue();> // Adding elements to the queue> queue.enqueue(10);> queue.enqueue(20);> queue.enqueue(30);> queue.enqueue(40);> // queue contains [10, 20, 30, 40]> // removes 10> document.write(queue.dequeue() +>' dequeued from queue '>);> // queue contains [20, 30, 40]> // Front is now 20> document.write(>'Front item is '> + queue.front() +>' '>);> // printing the rear element> // Rear is 40> document.write(>'Rear item is '> + queue.rear() +>' '>);> // This code is contributed by Susobhan Akhuli> >

ile tygodni ma miesiąc

Wyjście

10 enqueued to queue 20 enqueued to queue 30 enqueued to queue 40 enqueued to queue 10 dequeued from queue Front item is 20 Rear item is 40>

Analiza złożoności:

Złożoność czasu

Operacje	Złożoność
Kolejkuj (wstawianie)	O(1)
Deque(usunięcie)	O(1)
Przód (do przodu)	O(1)
Tył (dostań się do tyłu)	O(1)
IsFull (Sprawdź, czy kolejka jest pełna, czy nie)	O(1)
IsEmpty (Sprawdź, czy kolejka jest pusta, czy nie)	O(1)

Zalety implementacji tablicy:

Łatwe do wdrożenia.
Można z łatwością efektywnie zarządzać dużą ilością danych.
Operacje takie jak wstawianie i usuwanie można wykonywać z łatwością, zgodnie z zasadą „pierwsze weszło, pierwsze wyszło”.

Wady implementacji tablic:

Statyczna struktura danych, stały rozmiar.
Jeśli kolejka zawiera dużą liczbę operacji dodawania i usuwania z kolejki, w pewnym momencie (w przypadku liniowego przyrostu indeksów przednich i tylnych) możemy nie być w stanie wstawić elementów do kolejki, nawet jeśli kolejka jest pusta (tego problemu unika się za pomocą kolejki okrężnej).
Należy wcześniej określić maksymalny rozmiar kolejki.

TechCodeview

Wprowadzenie i implementacja tablicy kolejki