Чарга

Чарга́ — працэс, арганізаваны згодна прынцыпу 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 < N ) 
     {
        data[ (top + size) mod N] = element;
        size++;
     }
     else
        throw queue.overflow;
  }
  
  function queue.pop()
  {
     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 выкарыстоўвае чаргу як адзіную структуру дадзеных.

Глядзіце таксама

• Дрэва
• Масіў
• Стэк
• Сьпіс