Чарга

Зьвесткі зь Вікіпэдыі — вольнай энцыкляпэдыі
Перайсьці да: навігацыі, пошуку

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

Апэрацыі[рэдагаваць | рэдагаваць крыніцу]

Асноўныя апэрацыі ў чарзе:

  • push: дадаць элемэнт у хвост (пасьля апошняга) чаргі. Колькасьць элемэнтаў у чарзе павялічваецца на 1. Калі памер чаргі абмежаваны, гэтая апэрацыя можа выклікаць памылку overflow – перапаўненьне.
  • pop: атрымаць першы элемэнт. Колькасьць элемэнтаў памяньшаецца на 1. Першым элемэнтам становіцца той, што дагэтуль быў другім (калі такі быў). Гэтая апэрацыя магчымая толькі калі ў чарзе быў прынамсі адзін элемэнт.

Дадатковыя, службовыя апэрацыі:

  • isEmpty: праверка, ці ёсьць элемэнты ў чарзе. Рэзультат: ісьціна, калі ў чарзе няма элемэнтаў.
  • isFull: праверка, ці запоўненая чарга. Рэзультат: ісьціна, калі ў чаргу больш нельга дадаць ніводнага элемэнта.
  • clear: ачысьціць чаргу (выдаліць усе элемэнты).
  • size: атрымаць памер чаргі (колькасьць элемэнтаў).
  • top: атрымаць верхні элемэнт.

Рэалізацыі чаргі[рэдагаваць | рэдагаваць крыніцу]

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

Праз масіў[рэдагаваць | рэдагаваць крыніцу]

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

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 выкарыстоўвае чаргу як адзіную структуру дадзеных.

Глядзі таксама[рэдагаваць | рэдагаваць крыніцу]

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