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


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


Також дивитеся інші матеріали цієї серії: бінарне дерево, динамічний масив, зв’язний список, оцінка складності алгоритму, сортування і множини.

Стік

Стік – це колекція, елементи якої отримують за принципом “останній увійшов, перший вийшов” (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"

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

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