Чарга

**Чарга́** — працэс, арганізаваны згодна прынцыпу FIFO (first in — first out): першы прыйшоў — першы выйшаў. Такая арганізацыя найбольш пашыраная пры абслугоўваньні кліентаў: той хто раней прыйшоў, атрымае паслугу раней.
У праграмаваньні **чарга** — структура зьвестак, што мадэлюе такія працэсы. Сярод усіх элемэнтаў чаргі выдзяляюцца два: першы і апошні.

## Апэрацыі
Асноўныя апэрацыі ў чарзе:
* **push**: дадаць элемэнт у хвост (пасьля апошняга) чаргі. Колькасьць элемэнтаў у чарзе павялічваецца на 1. Калі памер чаргі абмежаваны, гэтая апэрацыя можа выклікаць памылку *overflow* — перапаўненьне.
* **pop**: атрымаць першы элемэнт. Колькасьць элемэнтаў памяньшаецца на 1. Першым элемэнтам становіцца той, што дагэтуль быў другім (калі такі быў). Гэтая апэрацыя магчымая толькі калі ў чарзе быў прынамсі адзін элемэнт.
Дадатковыя, службовыя апэрацыі:
* **isEmpty**: праверка, ці ёсьць элемэнты ў чарзе. Рэзультат: ісьціна, калі ў чарзе няма элемэнтаў.
* **isFull**: праверка, ці запоўненая чарга. Рэзультат: ісьціна, калі ў чаргу больш нельга дадаць ніводнага элемэнта.
* **clear**: ачысьціць чаргу (выдаліць усе элемэнты).
* **size**: атрымаць памер чаргі (колькасьць элемэнтаў).
* **top**: атрымаць верхні элемэнт.

## Рэалізацыі чаргі
Рэалізацыя чаргі можа быць зроблена праз масіў ці сьпіс.

### Праз масіў

Для захаваньня элемэнтаў чаргі рэзэрвуецца масіў пэўнага памеру і дзьве зьменных, якія зьмяшчаюць індэкс першага элемэнту і памер (даўжыню) чаргі.

 **record** queue
 {
   *object*[0..N-1] data;
   *int* top = 0;
   *int* size = 0;
 }

Апэрацыя **push** павялічвае памер чаргі, а **pop** павялічвае індэкс першага элемэнту і зьмяньшае памер чаргі.
   **function** queue.push( *object* element )
   {
      **if** ( size  0 )
      {
        **var** *object* element = data[top];
        top = ( top + 1 ) **mod** N;
        size--;
        **return** element;
      }
      **else**
         **throw** queue.underflow;
   }

Функцыі **top** і **size** вяртаюць значэньні адпаведных зьменных, функцыя **clear** абнуляе іх.

Прыклад ужываньня
 **var** *int* a;
 **var** *queue* q = **new** queue();
 
 q.push(3);
 q.push(4);
 
 a = q.pop(); *// a == 3*

### Празь сьпіс
У гэтым выпадку выкарыстоўваецца просты аднабаковы сьпіс, які зьмяшчае элемэнты чаргі і дзьве зьменныя, што захоўваюць спасылкі на першы і апошні элемэнты сьпіса.
   **record** list
   {
      *object* head; 
      *list* tail;
   }
   
   **record** queue
   {
      *list* top;
      *list* last;
   }

Апэрацыя **push** стварае новы элемэнт сьпісу, і дадае яго ў канец чаргі, пасьля бягучага апошняга. **pop** вяртае бягучы першы элемэнт і рухае спасылку пачатковага элемэнта на другі:
   **function** queue.push( *object* element )
   {
      **var** *list* newElement = **new** list();
      newElement.head = element;
      newElement.tail = **null**;
      **if** ( top == **null** )
      {
         top = newElement; 
         last = newElement; 
      }
      **else**
      {
         last.tail = newElement;
         last = newElement;
      }
   }
   
   **function** queue.pop()
   {
      **if** ( top == **null** )
         **throw** queue.underflow;
      **var** *object* first = top.head;
      top = top.tail;
      **return** first;
   }

Прыклад ужываньня
 **var** *int* a;
 **var** *queue* q = **new** queue();
 
 q.push(3);
 q.push(4);
 
 a = q.pop(); *// a == 3*

## Прымяненьні чаргі
Чэргі ўжываецца ў альгарытмах, што мадэлююць працэсы, арганізаваны згодна прынцыпу FIFO. Напрыклад, пры апрацоўцы клявіатуры: коды націснутых клявіш зьмяшчаюцца ў чаргу; працэсар кампутара мае чаргу каманд, пакуль выконваецца першая, у канец чаргі з памяці дадаюцца наступныя; праграмы, што пабудаваныя на апрацоўцы падзей (event driven, кіраваныя падзеямі) маюць чаргу, дзе захоўваюцца зьвесткі пра новыя падзеі пакуль выконваецца рэакцыя на першую падзею.
Мова праграмаваньня Oroogu выкарыстоўвае чаргу як адзіную структуру дадзеных.

## Глядзіце таксама
* Дрэва
* Масіў
* Стэк
* Сьпіс

Катэгорыя:Структуры зьвестак