Алгоритми і структури даних для початківців: стеки і черги


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

У попередніх частинах ми розглядали базові структури даних, які, по суті, були надбудовами над масивом. У цій статті ми додамо до колекцій прості операції і подивимося, як це вплине на їх можливості.

Стек

Стек – це колекція, елементи якої отримують за принципом “останній увійшов, перший вийшов” (Last – In – First – Out або LIFO). Це означає, що ми матимемо доступ тільки до останнього доданого елемента.

На відміну від списків, ми не можемо отримати доступ до довільного елемента стека. Ми можемо тільки додавати або видаляти елементи за допомогою спеціальних методів. У стека немає також методу Contains, як у списків. Крім того, у стека немає ітератора. Для того щоб розуміти, чому на стек накладаються такі обмеження, давайте подивимося на те, як він працює і як використовується.

Аналогія, що найчастіше зустрічається, для пояснення стека – стопка тарілок. Незалежно від того, скільки тарілок у стопці, ми завжди можемо зняти верхню. Чисті тарілки так само кладуться на верх стопки, і ми завжди будемо першими брати ту тарілку, яка була покладена останньою.

Якщо ми покладемо, наприклад, червону тарілку, потім синю, а потім зелену, то спочатку потрібно буде зняти зелену, потім синю, і, нарешті, червону. Головне, що потрібно запам’ятати – тарілки завжди ставляться і на верх стопки. Коли хтось бере тарілку, він також знімає її згори. Виходить, що тарілки розбираються в порядку, зворотному тому, в якому ставилися.

Тепер, коли ми розуміємо, як працює стек, введемо декілька термінів. Операція додавання елемента на стек називається “push”, видалення – “pop”. Останній доданий елемент називається верхівкою стека, або “top”, і його можна подивитися за допомогою операції “peek”. Давайте тепер подивимося на заготівлю класу, що реалізовує стек.

Клас Stack

Клас Stack визначає методи Push, Pop, Peek для доступу до елементів і поле Count. У реалізації ми використовуватимемо LinkedList для зберігання елементів.

public class Stack{ LinkedList_items = new LinkedList (); public void Push (T value) { throw new NotImplementedException (); } public T Pop (){ throw new NotImplementedException (); } public T Peek (){
throw new NotImplementedException (); } public int Count { get; }}

Метод Push

  • Поведінка: додає елемент на вершину стека.
  • Складність: O (1).

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

public void Push (T value){_items.AddLast (value);}

Метод Pop

  • Поведінка: видаляє елемент з вершини стека і повертає його. Якщо стек порожній, видає InvalidOperationException.
  • Складність: O (1).

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

public T Pop (){ if (_ items.Count == 0) {
throw new InvalidOperationException ("The stack is empty"); } T result =_items.Tail.Value;_items.RemoveLast (); return result;}

Метод Peek

  • Поведінка: повертає верхній елемент стека, але не видаляє його. Якщо стек порожній, видає InvalidOperationException.
  • Складність: O (1).
public T Peek (){ if (_ items.Count == 0) { throw new InvalidOperationException ("The stack is empty"); } return_items.Tail.Value;}

Метод Count

  • Поведінка: повертає кількість елементів у стеку.
  • Складність: O (1).

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

public int Count{ get { return_items.Count; }}

Приклад: калькулятор у зворотному польському записі.

Класичний приклад використання стека – калькулятор у зворотному польському, або постфіксному, записі. У ній оператор записується після своїх операндів, тобто, ми пишемо:

<операнд> <операнд> <оператор>

замість традиційного:

<операнд> <оператор> <операнд>

Другими словами, замість “4 + 2” ми запишемо “4 2 +”. Якщо Вас цікавить походження зворотного польського запису та його назви, Ви можете дізнатися про це з Вікіпедії або в пошуковику.

Як обчислюється зворотний польський запис і чому стек такий коисний за його використання, видно з наведеного нижче алгоритму:

for each input value if the value is an integer push the value on to the operand stack else if the value is an operator pop the left and right values from the stack evaluate the operator push the result on to the stackpop answer from stack.

Для виразу “4 2 +” потрібні дії:

push (4) push (2) push (pop () + pop())

У кінці на стеку виявиться одне значення – 6.

Далі наводиться повний код простого калькулятора, який зчитує вираз (наприклад, 4 2 +) з консолі, розбиває вхідні дані за пропусками (["4", " 2", "+"]) і виконує алгоритм обчислення. Обчислення триває до тих пір, поки не буде зустрінуте слово quit.

void RpnLoop (){ while (true) { Console.Write ("> "); string input = Console.ReadLine (); if (input.Trim ().ToLower () == " quit") { break; } // Стек ще не оброблених значень. Stack values = new Stack (); foreach (string token in input.Split (new char[] { ' ' })) {
// Якщо значення - ціле число... int value; if (int.TryParse (token, out value)) { // ... покласти його на стек. values.Push (value); } else { // інакше виконати операцію... int rhs = values.Pop (); int lhs = values.Pop (); // ... і покласти результат назад. switch (token) { case "+": values.Push (lhs + rhs); break; case "-": values.Push (lhs - rhs); break; case "*": values.Push (lhs * rhs); break; case "/": values.Push (lhs / rhs);
break; case "%": values.Push (lhs % rhs); break; default: // Якщо операція не +, -, * або / throw new ArgumentException ( string.Format ("Unrecognized token: {0}", token)); } } } // Останній елемент на стеку і є результат. Console.WriteLine (values.Pop()); }}

Черга

Черги дуже схожі на стеки. Вони також не дають доступу до довільного елемента, але, на відміну від стека, елементи кладуться (enqueue) і забираються (dequeue) з різних кінців. Такий метод називається “перший увійшов, перший вийшов” (First – In – First – Out або FIFO). Забирати елементи з черги ми будемо в тому ж порядку, що і ложили. Подібно до реальної черги або конвеєра.

Черги часто використовуються в програмах для реалізації буфера, в який можна покласти елемент для подальшої обробки, зберігаючи порядок вступу. Наприклад, якщо база даних підтримує тільки одно з’єднання, можна використати чергу потоків, які будуть, як не дивно, чекати своєї черги на доступ до БД.

Клас Queue

Клас Queue, як і стек, буде реалізований за допомогою зв’язного списку. Він надаватиме методи Enqueue для додавання елемента, Dequeue для видалення, Peek і Count. Як і клас Stack, він не реалізовуватиме інтерфейс ICollection, оскільки це колекції спеціального призначення.

public class Queue{ LinkedList_items = new LinkedList (); public void Enqueue (T value) { throw new NotImplementedException (); } public T Dequeue (){ throw new NotImplementedException (); } public T Peek (){ throw new NotImplementedException (); } public int Count { get; }}

Метод Enqueue

  • Поведінка: додає елемент в чергу.
  • Складність: O (1).

Нові елементи черги можна додавати як в початок списку, так і в кінець. Важливо тільки, щоб елементи діставалися з протилежного краю. У цій реалізації ми додаватимемо нові елементи в початок внутрішнього списку.

Public void Enqueue (T value){_items.AddFirst (value);}

Метод Dequeue

  • Поведінка: видаляє перший поміщений елемент з черги і повертає його. Якщо черга порожня, видає InvalidOperationException.
  • Складність: O (1).

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

public T Dequeue (){ if (_ items.Count == 0) { throw new InvalidOperationException ("The queue is empty"); } T last =_items.Tail.Value;_items.RemoveLast (); return last;}

Метод Peek

  • Поведінка: повертає елемент, який поверне наступний виклик методу Dequeue. Черга залишається без змін. Якщо черга порожня, видає InvalidOperationException.
  • Складність: O (1).
public T Peek (){ if (_ items.Count == 0) { throw new InvalidOperationException ("The queue is empty"); } return_items.Tail.Value;}

Метод Count

  • Поведінка: повертає кількість елементів у чергу або 0, якщо черга порожня.
  • Складність: O (1).
public int Count{ get { return_items.Count; }}

Двостороння черга

Двостороння черга (Double – ended queue), чи дек (Deque), розширює поведінку черги. У дек можна додавати або видаляти елементи як з початку, так і з кінця черги. Така поведінка корисна у багатьох задачах, наприклад, планування виконання потоків або реалізація інших структур даних. Пізніше ми розглянемо варіант реалізації стека за допомогою двосторонньої черги.

Клас Deque

Клас Deque найпростіше реалізувати за допомогою двозв’язного списку. Він дозволяє переглядати, видаляти і додавати елементи в початок і в кінець списку. Основна відмінність двосторонньої черги від звичайної – методи Enqueue, Dequeue, і Peek розділені на пари для роботи з обома кінцями списку.

public class Deque{ LinkedList_items = new LinkedList (); public void EnqueueFirst (T value) {
throw new NotImplementedException (); } public void EnqueueLast (T value) { throw new NotImplementedException (); } public T DequeueFirst (){ throw new NotImplementedException (); } public T DequeueLast (){ throw new NotImplementedException (); } public T PeekFirst (){ throw new NotImplementedException (); } public T PeekLast (){ throw new NotImplementedException (); } public int Count { get; }}

Метод EnqueueFirst

  • Поведінка: додає елемент в початок черги. Цей елемент буде взятий з черги наступним при виклику методу DequeueFirst.
  • Складність: O (1).
public void EnqueueFirst (T value){_items.AddFirst (value);}

Метод EnqueueLast

  • Поведінка: додає елемент в кінець черги. Цей елемент буде взятий з черги наступним при виклику методу DequeueLast.
  • Складність: O (1).
public void EnqueueLast (T value){_items.AddLast (value);}

Метод DequeueFirst

  • Поведінка: видаляє елемент з початку черги і повертає його. Якщо черга порожня, видає InvalidOperationException.
  • Складність: O (1).
public T DequeueFirst (){ if (_ items.Count == 0) { throw new InvalidOperationException ("DequeueFirst called when deque is empty"); } T temp =_items.Head.Value;_items.RemoveFirst (); return temp;}

Метод DequeueLast

  • Поведінка: видаляє елемент з кінця черги і повертає його. Якщо черга порожня, видає InvalidOperationException.
  • Складність: O (1).
public T DequeueLast (){ if (_ items.Count == 0) { throw new InvalidOperationException ("DequeueLast called when deque is empty"); } T temp =_items.Tail.Value;_items.RemoveLast (); return temp;}

Метод PeekFirst

  • Поведінка: повертає елемент з початку черги, не змінюючи її. Якщо черга порожня, видає InvalidOperationException.
  • Складність: O (1).
public T PeekFirst (){ if (_ items.Count == 0) { throw new InvalidOperationException ("PeekFirst called when deque is empty"); } return_items.Head.Value;}

Метод PeekLast

  • Поведінка: повертає елемент з кінця черги, не змінюючи її. Якщо черга порожня, видає InvalidOperationException.
  • Складність: O (1).
public T PeekLast (){ if (_ items.Count == 0) { throw new InvalidOperationException ("PeekLast called when deque is empty"); } return_items.Tail.Value;}

Метод Count

  • Поведінка: повертає кількість елементів у чергу або 0, якщо черга порожня.
  • Складність: O (1).
public int Count{ get { return_items.Count; }}

Приклад: реалізація стека

Двостороння черга часто використовується для реалізації інших структур даних. Давайте подивимося на приклад реалізації стека з її допомогою.

У Вас, можливо, постало питання: “Навіщо реалізовувати стек на основі черги замість зв’язного списку?”. Причини дві: продуктивність і повторне використання коду. У зв’язного списку є накладні витрати на створення вузлів і немає гарантії локальності даних: елементи можуть бути розташовані у будь-якому місці пам’яті, що викликає велику кількість промахів і падіння продуктивності на рівні процесорів. Продуктивніша реалізація двосторонньої черги вимагає масиву для зберігання елементів.

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

Пізніше ми подивимося на варіант черги з використанням масиву, але спочатку давайте поглянемо на клас стека з використанням двосторонньої черги:

public class Stack{ Deque_items = new Deque (); public void Push (T value) {_items.EnqueueFirst (value); } public T Pop (){ return_items.DequeueFirst (); } public T Peek (){ return_items.PeekFirst (); } public int Count { get { return_items.Count; } }}

Зверніть увагу на те, що вся обробка помилок тепер лежить на класі Deque, і, крім того, будь-яка оптимізація черги також відіб’ється на стеку. Реалізація звичайної черги на основі двосторонньої настільки проста, що ми залишимо її читачеві як вправу.

Зберігання елементів у масиві

Як вже було зазначено вище, у реалізації черги з використанням масиву є свої переваги. Вона виглядає простою, але насправді є ряд нюансів, які потрібно врахувати.

Давайте подивимося на проблеми, які можуть виникнути, і на їх розв’язання. Крім того, нам знадобиться інформація про збільшення внутрішнього масиву з попередньої статті про динамічні масиви.

При створенні черги спостерігаємо, як у неї всередині створюється масив нульової довжини. Червоні букви “h” і ” t” означають покажчики _ head і _ tail відповідно.

Deque deq = new Deque ();deq.EnqueueFirst (1);

Додаємо елемент в початок

deq.EnqueueLast (2);

Додаємо елемент в кінець

deq.EnqueueFirst (0);

Додаємо ще один елемент в початок

Зверніть увагу: індекс “голови” черги змістився в початок списку. Тепер перший елемент, який буде повернений при виклику методу DequeueFirst – 0 (індекс 3).

deq.EnqueueLast (3);

І ще один в кінець

Масив заповнений, тому при додаванні елемента відбудеться таке:

  • Алгорим зростання визначить розмір нового масиву.
  • Елементи скопіюються в новий масив з “голови” до ” хвоста”.
  • Додасться новий елемент.
deq.EnqueueLast (4);

Додаємо значення в кінець розширеного масиву

Тепер подивимося, що відбувається при видаленні елемента:

deq.DequeueFirst ();

Видаляємо елемент з початку

deq.DequeueLast ();

Видаляємо елемент з кінця

Ключовий момент: незалежно від місткості або заповненої внутрішнього масиву, логічно, вміст черги – елементи від “голови” до “хвоста” з урахуванням “закільцьованості”. Така поведінка називається “кільцевим буфером”.

Тепер давайте подивимося на реалізацію.

Клас Deque (з використанням масиву)

Інтерфейс черги на основі масиву такий, як і в разі реалізації через зв’язний список. Ми його не повторюватимемо. Проте оскільки список був замінений на масив, у нас додалися нові поля – сам масив, його розмір і покажчики на “хвіст” і “голову” черги.

public class Deque{ T[]_items = new T[0]; // Кількість елементів в черзі. int_size = 0; // Індекс першого (найстарішого) елементу. int_head = 0; // Індекс останнього (найновішого) елементу. int_tail = - 1;...}

Алгоритм зростання

Коли вільне місце у внутрішньому масиві закінчується, його необхідно збільшити, скопіювати елементи і оновити покажчики на “хвіст” і “голову”. Ця операція робиться за необхідності під час додавання елемента. Параметр startingIndex використовується, щоб показати, скільки полів на початку необхідно залишити порожніми (у разі додавання в початок).

Зверніть увагу на те, як витягаються дані, коли доводиться переходити в початок масиву при проході від “голови” до “хвоста”.

private void allocateNewArray (int startingIndex){ int newLength =  (_ size == 0) ? 4 :_size * 2; T[] newArray = new T[newLength]; if (_ size > 0) { int targetIndex = startingIndex; // Копіюємо вміст... // Якщо масив не закольцован, просто копіюємо елементи.
// Інакше, копіює від head до кінця, а потім від початку масиву до tail. // Якщо tail менше, ніж head, переходимо в початок. if (_ tail <_head) { // Копіюємо_items[head]._ items[end] у newArray[0].newArray[N]. for (int index =_head; index <_items.Length; index++) { newArray[targetIndex] =_items[index]; targetIndex++; } // Копіюємо_items[0]._ items[tail] у newArray[N+1]. for (int index = 0; index <=_tail; index++) { newArray[targetIndex] =_items[index]; targetIndex++; } } else { // Копіюємо_items[head]._ items[tail] у newArray[0].newArray[N] for (int index =_head; index <=_tail; index++) {
newArray[targetIndex] =_items[index]; targetIndex++; } }_head = startingIndex;_tail = targetIndex - 1; } else { // Масив порожній._head = 0;_tail = - 1; }_items = newArray;}

Метод EnqueueFirst

  • Поведінка: додає елемент у початок черги. Цей елемент буде взятий з черги наступним при виклику методу DequeueFirst.
  • Складність: O (1) у більшості випадків; O (n), коли треба розширення масиву.
public void EnqueueFirst (T item){ // Перевіримо, чи потрібне збільшення масиву: if (_ items.Length ==_size) { allocateNewArray (1); } // Оскільки масив не заповнений і_head більше 0, // ми знаємо, що є місце на початку масиву.
if (_ head > 0) {_head--; } else { // Інакше ми повинні закільцьовувати._head =_items.Length - 1; }_items[_ head] = item;_size++;}

Метод EnqueueLast

  • Поведінка: додає елемент в кінець черги. Цей елемент буде взятий з черги наступним при виклику методу DequeueLast.
  • Складність: O (1) у більшості випадків; O (n), коли треба розширення масиву.
public void EnqueueLast (T item){ // Перевіримо, чи потрібне збільшення масиву: if (_ items.Length ==_size) { allocateNewArray (0); } // Тепер, коли у нас є відповідний масив, // якщо_tail у кінці масиву, нам потрібно перейти в початок. if (_ tail ==_items.Length - 1) {_tail = 0; } else {
_ tail++; }_items[_ tail] = item;_size++;}

Метод DequeueFirst

  • Поведінка: видаляє елемент з початку черги і повертає його. Якщо черга порожня, видає InvalidOperationException.
  • Складність: O (1).
public T DequeueFirst (){ if (_ size == 0) { throw new InvalidOperationException ("The deque is empty"); } T value =_items[_ head]; if (_ head ==_items.Length - 1) { // Якщо head встановлений на останньому індексі, переходиться до початку масиву._head = 0; } else { // Переходимо до наступного елементу._head++; }_size--; return value;}

Метод DequeueLast

  • Поведінка: видаляє елемент з кінця черги і повертає його. Якщо черга порожня, видає InvalidOperationException.
  • Складність: O (1).
public T DequeueLast (){ if (_ size == 0) { throw new InvalidOperationException ("The deque is empty"); } T value =_items[_ tail]; if (_ tail == 0) { // Якщо tail встановлений на початок масиву, переходиться до кінця._tail =_items.Length - 1; } else { // Переходимо до попереднього елементу._tail--; }_size--; return value;}

Метод PeekFirst

  • Поведінка: повертає елемент з початку черги, не змінюючи її. Якщо черга порожня, видає InvalidOperationException.
  • Складність: O (1).
public T PeekFirst (){
if (_ size == 0) { throw new InvalidOperationException ("The deque is empty"); } return_items[_ head];}

Метод PeekLast

  • Поведінка: повертає елемент з кінця черги, не змінюючи її. Якщо черга порожня, кидає InvalidOperationException.
  • Складність: O (1).
public T PeekLast (){ if (_ size == 0) { throw new InvalidOperationException ("The deque is empty"); } return_items[_ tail];}

Метод Count

  • Поведінка: повертає кількість елементів у черги або 0, якщо черга порожня.
  • Складність: O (1).
public int Count{ get { return_size; }}

Далі буде

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

Переклад статті “Stacks and Queues”

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Trends: масив стек чеерга, додавання елемента в кінець черги метод

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *