Основні операції з чергою[ред. • ред. Код]

• англ. enqueue — "поставити в чергу". Операція додавання елемента в "хвіст" черги. При цьому довжина черги збільшується на одиницю. Якщо відбувається намагання додати елемент у вже заповнену чергу, відбувається її переповнення (англ. queue overflow).

• англ. dequeue — "отримання з черги". Операція, яка повертає елемент з голови та видаляє його з черги, таким чином встановлюючи голову на наступний за видаленим елемент та зменшуючи довжину на одиницю. При намаганні видалити елемент з пустої черги, виникає ситуація "незаповнення" (англ. queue underflow).

Реалізація на мовах програмування[ред. • ред. Код]

Черга може бути реалізована за допомогою масива Q[1...n], в якому зберігаються дані та двох додаткових змінних head[Q] та tail[Q], в яких зберігаються індекси відповідно "голови" та "хвоста" черги, length[Q] -- довжина черги.

Тоді операції enqueue та dequeue запишуться так:

ENQUEUE (Q, x) 1 Q[tail[Q]] := x 2 if tail[Q] = length[Q] 3 then tail[Q] := 1 4 else tail[Q] := tail[Q] + 1

DEQUEUE (Q) 1 x := Q[head[Q]] 2 if head[Q] = length[Q] 3 then head[Q] := 1 4 else head[Q] := head[Q] + 1 5 return x

По́шук у ширину́ — алгоритм пошуку на графі.^[1]

Якщо задано граф G = (V, E) та початкову вершину s, алгоритм пошуку в ширину систематично обходить всі досяжні із s вершини. На першому кроці вершина s позначається, як пройдена, а в список додаються всі вершини, досяжні з s без відвідування проміжних вершин. На кожному наступному кроці всі поточні вершини списку відмічаються, як пройдені, а новий список формується із вершин, котрі є ще не пройденими сусідами поточних вершин списку. Для реалізації списку вершин найчастіше використовується черга. Виконання алгоритму продовжується до досягнення шуканої вершини або до того часу, коли на певному кроці в список не включається жодна вершина. Другий випадок означає, що всі вершини, доступні з початкової, уже відмічені, як пройдені, а шлях до цільової вершини не знайдений.

Алгоритм має назву пошуку в ширину, оскільки «фронт» пошуку (між пройденими та непройденими вершинами) одноманітно розширюється вздовж всієї своєї ширини. Тобто, алгоритм проходить всі вершини на відстані k перед тим як пройти вершини на відстані k+1.

Наведемо кроки алгоритму

1. Почати з довільної вершини v. Виконати BFS(v):=1. Включити вершину v у чергу.

2. Розглянути вершину, яка перебуває на початку черги; нехай це буде вершина х. Якщо для всіх вершин, суміжних із вершиною х, уже визначено BFS-номери, то перейти до кроку 4, інакше - до кроку 3.

3. Нехай {x,y} - ребро, у якому номер BFS(у) не визначено. Позначити це ребро потовщеною суцільною лінією, визначити BFS(у) як черговий BFS-номер, включити вершину у у чергу й перейти до кроку 2.

4. Виключити вершину х зі черги. Якщо черга порожня, то зупинитись, інакше - перейти до кроку 2.

Циклічний буфер або кільцевий буфер - це структура даних, яка має фіксований розмір і використовується так ніби кінець буферу і початок замкнені в кільце, тобто при досягненні кінця буфера знов переміщуються в його початок. Така структура дає можливість здійснювати буферизацію потоків даних.

В програмуванні двійкове дерево — структура даних у вигляді дерева, в якому кожна вершина має не більше двох дітей. Зазвичай такі діти називаються правим та лівим. На базі двійкових дерев будуються такі структури, як двійкові дерева пошуку та двійкові купи.

Двійкове (або Бінарне) дéрево пóшуку (англ.binary search tree, BST) в інформатиці—двійкове дерево, в якому кожній вершині x зіставлене певне значення val[x]. При цьому такі значення повинні задовольняти умові впорядкованості

• нехай x — довільна вершина двійкового дерева пошуку. Якщо вершина y знаходиться в лівому піддереві вершини x, то val[y] ≤ val[x].

• Якщо у знаходиться у правому піддереві x, то val[y] ≥ val[x].

Таке структурування дозволяє надрукувати усі значення у зростаючому порядку за допомогою простого алгоритму центрованого обходу дерева.^[

Представляється таке дерево вузлами наступного вигляду:

*Node = (element, key, left, right, parent). Доступ до дерева T здійснюється за допомогою посилання root.

Бінарні дерева пошуку набагато ефективніші в операціях пошуку, аніж лінійні структури, в яких витрати часу на пошук пропорційні O(n), де n — розмір масивуданих, тоді як в повному бінарному дереві цей час пропорційний в середньомуO(log₂n) або O(h), де h — висота дерева (хоча гарантувати, що h не перевищує log₂n можна лише для збалансованих дерев, які є ефективнішими в алгоритмах пошуку, аніж прості бінарні дерева пошуку)

Обхід бінарного дерева передбачає відвідування усіх вершин бінарного дерева, при цьому кожна з вершин відвідується тільки один раз.

Існують три види таких обходів, кожний з яких визначається рекурсивно:

• прямий порядок (англ.preorder) наступної послідовності:

1. відвідати корінь

2. відвідати ліве піддерево

3. відвідати праве піддерево

Тобто, в такому порядку обходу кожна вершина відвідується до того, як будуть відвідані її діти.

• зворотний порядок (англ.postorder) наступної послідовності:

1. відвідати ліве піддерево

2. відвідати праве піддерево

3. відвідати корінь

Тобто, в такому порядку кожна вершина відвідується лише після того, як будуть відвідані її діти.

• центрований (центральний) порядок (англ.inorder) наступної послідовності:

1. відвідати ліве піддерево

2. відвідати корінь

3. відвідати праве піддерево

В такому порядку кожна вершина відвідується між відвіданням лівої та правої дитини. Такий порядок особливо часто застосовується в бінарних деревах пошуку, тому що дає можливість обходу вершин у порядку збільшення їхніх порядкових номерів.

Для цього бінарного дерева,

• Прямий порядок: 2, 7, 2, 6, 5, 11, 5, 9, 4

• Зворотний порядок: 2, 5, 11, 6, 7, 4, 9, 5, 2

• Центрований (центральний) порядок: 2, 7, 5, 6, 11, 2, 5, 4, 9