Към съдържанието
wannacode

Стек, опашка и свързан списък

Накратко: Стекът връща последния добавен елемент пръв (LIFO), опашката връща първия добавен пръв (FIFO), а свързаният списък пази всеки елемент във възел със стрелка към следващия.

Проблем

„Отмени“ отменя не това

Текстовият редактор пази действията в списък. Ctrl+Z трябва да отмени последното, но отменя първото:

List<string> actions = new List<string>();
actions.Add("Въведе текст");
actions.Add("Удебели заглавието");
actions.Add("Вмъкна снимка");


// Ctrl+Z: отмени последното действие.
string undone = actions[0];
actions.RemoveAt(0);
Console.WriteLine("Отменено: " + undone);
Console.WriteLine("Остава: " + string.Join(", ", actions));
Изход
Отменено: Въведе текст
Остава: Удебели заглавието, Вмъкна снимка

Поправката е actions[^1] и actions.RemoveAt(actions.Count - 1): RemoveAt не връща махнатия елемент, затова той се чете преди това. Но всеки, който пипа този код, трябва да помни от кой край се маха. А при касата в магазина е обратното: обслужва се първият, който е дошъл. Има ли колекция, която сама знае от кой край?

Идеята

Стек: последното най-отгоре

Стекът е като купчина чинии. Слагаш отгоре и взимаш отгоре. Последното сложено излиза първо. На английски това е LIFO: last in, first out.

Бутонът „Назад“ в браузъра е стек:

Stack<string> history = new Stack<string>();
history.Push("Начало");
history.Push("Лаптопи");
history.Push("Лаптоп 14 инча");
Console.WriteLine("Сега: " + history.Peek());


history.Pop();
Console.WriteLine("Назад: " + history.Peek());
Console.WriteLine(string.Join(", ", history));
Изход
Сега: Лаптоп 14 инча
Назад: Лаптопи
Лаптопи, Начало
  • Push слага отгоре, Pop маха и връща горния, Peek само поглежда горния.
  • Stack<T> е в System.Collections.Generic, като List<T>.
  • string.Join минава по стека отгоре надолу.
По-точно, за любопитните
  • Pop и Peek на празен стек спират програмата. TryPeek не я спира: връща false, ако стекът е празен, а горния елемент дава през out:
Stack<string> history = new Stack<string>();
if (history.TryPeek(out string page))
{
    Console.WriteLine("Сега: " + page);
}
else
{
    Console.WriteLine("Няма предишна страница.");
}
history.Pop();
Грешка
Unhandled exception. System.InvalidOperationException: Stack empty.

Програмата първо печата „Няма предишна страница.“, а спира на Pop. За Pop има и TryPop.

  • C# има и по-стар клас Stack без ъгли, в System.Collections. Той пази всичко като object. Работи, но днес се ползва Stack<T>:
Stack stack = new Stack();
stack.Push("Google");
stack.Push("Apple");
stack.Push("Microsoft");
Console.WriteLine("На върха: " + stack.Peek());
while (stack.Count > 0)
{
    Console.WriteLine("Изваден: " + stack.Pop());
}
Изход
На върха: Microsoft
Изваден: Microsoft
Изваден: Apple
Изваден: Google

Пробвай

Какво остава за отмяна?

Какво ще отпечата програмата?

Stack<string> undo = new Stack<string>();
undo.Push("шрифт");
undo.Push("цвят");
undo.Push("размер");
undo.Pop();
undo.Push("подчертаване");
while (undo.Count > 0)
{
    Console.WriteLine(undo.Pop());
}
Отговор

Идеята

Опашка: първият дошъл

Опашката е като на касата. Нареждаш се отзад, обслужва се първият. На английски е FIFO: first in, first out.

Заявките към принтера чакат на опашка:

Queue<string> printer = new Queue<string>();
printer.Enqueue("фактура.pdf");
printer.Enqueue("договор.docx");
printer.Enqueue("снимка.jpg");
Console.WriteLine("Следващ: " + printer.Peek());


while (printer.Count > 0)
{
    Console.WriteLine("Печатам " + printer.Dequeue());
}
Console.WriteLine("Опашка: " + printer.Count);
Изход
Следващ: фактура.pdf
Печатам фактура.pdf
Печатам договор.docx
Печатам снимка.jpg
Опашка: 0
  • Enqueue слага отзад, Dequeue маха и връща първия, Peek поглежда първия.
  • Queue<T> е в System.Collections.Generic. Count казва колко чакат, затова цикълът пита Count > 0.
  • Dequeue и Peek на празна опашка спират програмата. TryDequeue и TryPeek връщат false.
По-точно, за любопитните
  • Празната опашка:
Queue<string> clients = new Queue<string>();
clients.Enqueue("Клиент 1");
Console.WriteLine("Обслужен: " + clients.Dequeue());
if (!clients.TryDequeue(out string next))
{
    Console.WriteLine("Няма чакащи.");
}
clients.Dequeue();
Грешка
Unhandled exception. System.InvalidOperationException: Queue empty.

TryDequeue казва „Няма чакащи.“, а последният Dequeue спира програмата.

  • Опашка с два края като отделен клас в C# няма. LinkedList<T> може да слага и маха и в двата края, затова в по-стари примери го ползват за опашка:
LinkedList<string> clients = new LinkedList<string>();
clients.AddLast("Клиент 1");
clients.AddLast("Клиент 2");
clients.AddFirst("Клиент с час");
Console.WriteLine("Обслужен: " + clients.First.Value);
clients.RemoveFirst();
Console.WriteLine("Последен: " + clients.Last.Value);
Console.WriteLine("Чакат: " + string.Join(", ", clients));
Изход
Обслужен: Клиент с час
Последен: Клиент 2
Чакат: Клиент 1, Клиент 2
  • Queue<string> приема и null като елемент. Празната опашка се познава по Count или по TryDequeue, не по null:
Queue<string> printer = new Queue<string>();
printer.Enqueue(null);
Console.WriteLine(printer.Count);
Изход
1

Пробвай

Следващият на касата

Касиерката вика следващия клиент. Кой метод го взима от опашката?

Queue<string> checkout = new Queue<string>();
checkout.Enqueue("Иван");
checkout.Enqueue("Мария");
string next = checkout.();
Console.WriteLine("Заповядай, " + next);

Виж го

Свързан списък отвътре

List<T> пази елементите един до друг в масив. Затова вмъкването отпред мести всички останали. Има и друг начин: всеки елемент е в отделен обект, който пази стойността и стрелка към следващия. Такъв обект се казва възел (node):

class Node
{
    public string Value;
    public Node Next;


    public Node(string value, Node next)
    {
        Value = value;
        Next = next;
    }
}

Списък от възли се казва свързан списък. Достатъчно е да пазиш първия възел, head. Всеки следващ се намира по стрелката Next. Последният сочи null.

Node head = null;
head = new Node("Кафе", head);
head = new Node("Мляко", head);
head = new Node("Хляб", head);


for (Node n = head; n != null; n = n.Next)
{
    Console.WriteLine(n.Value);
}
Стъпка по стъпка, с думи
  1. Списъкът е празен: head сочи към null.
  2. Нов възел: Next е старият head (null), а head се премества на възела.
  3. Вторият възел сочи към първия. Нищо не се мести в паметта, сменят се само стрелките.
  4. Третият възел също влиза отпред: последното добавено е първо.
  5. n тръгва от head и печата всеки възел.
  6. n стига null: цикълът спира.
  • Вмъкване отпред: нов възел, чийто Next сочи стария първи, и head сочи новия. Две стрелки, без да местиш нищо.
  • Обхождане: тръгваш от head и минаваш по Next, докато не стигнеш null.
  • Цената: възлите нямат индекси. До петия елемент се стига, като минеш през първите четири.

Идеята

LinkedList<T> и кое кога

C# има готов свързан списък: LinkedList<T>. Той слага в двата края с AddFirst и AddLast, маха по стойност с Remove, а първия и последния възел дава през First и Last:

LinkedList<string> route = new LinkedList<string>();
route.AddLast("Пловдив");
route.AddLast("Стара Загора");
route.AddFirst("София");
route.AddLast("Бургас");
Console.WriteLine(string.Join(", ", route));


route.Remove("Стара Загора");
Console.WriteLine("След промяната: " + string.Join(", ", route));
Console.WriteLine("От " + route.First.Value + " до " + route.Last.Value);
Изход
София, Пловдив, Стара Загора, Бургас
След промяната: София, Пловдив, Бургас
От София до Бургас

Индекси LinkedList<T> няма изобщо. До елемент по номер се стига само през възлите, затова компилаторът не дава [ ]:

Console.WriteLine(route[1]);
Грешка при компилиране
error CS0021: Cannot apply indexing with [] to an expression of type 'LinkedList<string>'

Кое кога:

  • Списък по номер: List<T>. Това е обичайният избор.
  • Стек: Stack<T>. Опашка: Queue<T>.
  • LinkedList<T>: рядко. Когато трябват и двата края, или често вмъкваш и махаш до възел, който вече имаш.
По-точно, за любопитните
  • Защо LinkedList<T> обикновено е по-бавен, дори при вмъкване? Всеки възел е отделен обект някъде в паметта, а процесорът чете най-бързо данни, които стоят една до друга. Масивът зад List<T>, Stack<T> и Queue<T> е точно такъв.
  • Възлите на LinkedList<T> се виждат: First е LinkedListNode<string> с Value, Next и Previous. Стрелките са в двете посоки, затова Last и RemoveLast също са бързи:
LinkedList<string> route = new LinkedList<string>();
route.AddLast("София");
route.AddLast("Пловдив");
route.AddLast("Бургас");
LinkedListNode<string> second = route.First.Next;
Console.WriteLine(second.Value);
Console.WriteLine(second.Previous.Value + " <- " + second.Value + " -> " + second.Next.Value);
Console.WriteLine(route.Last.Next == null);
Изход
Пловдив
София <- Пловдив -> Бургас
True
  • Възелът от предишната карта има само Next. Такъв списък се казва едносвързан.

Пробвай

Намери грешката

Методът трябва да преброи възлите. За списъка Хляб → Мляко → Кафе връща 2 вместо 3. А за празен списък спира с NullReferenceException. На кой ред е грешката?

Избери реда с грешката.

Упражнение

Стекове и опашки в работа

Реши задачите в редактора си. Колекцията е private поле на класа.

1. Влакче. Клас Train с методи AddWagon(string wagon) и RemoveWagon(). Влакът е стек: откача се последният закачен вагон. RemoveWagon() връща откачения вагон или null, ако няма. Добави свойство Count. Закачи три вагона и откачи два.

Изход
Откачен: Вагон 3
Откачен: Вагон 2
Вагони: 1

2. Маршрут на автобус. Клас BusRoute с опашка от спирки и методи AddStop(string stop) и GetNextStop(), който връща следващата спирка или null, ако маршрутът е свършил. Добави „Централна гара“, „НДК“, „Студентски град“ и обходи маршрута.

Изход
Следваща спирка: Централна гара
Следваща спирка: НДК
Следваща спирка: Студентски град
Край на маршрута.

3. Борсов тикер. Клас StockTicker пази последните N цени на една акция. Конструкторът получава символа и N. UpdatePrice(double price) добавя цена, а ако цените станат повече от N, маха най-старата. Добави GetLastPrice() и Average() за пазените цени. За SAP с N = 3 подай цените 150, 152, 149 и 155. Подсказка: Queue<T> вижда само първия елемент, затова пази последната цена в отделно поле. Цените печатай с F2.

Изход
SAP: последна цена 155.00 €
Средно за последните 3: 152.00 €

4. Скобите в баланс. Редакторът на код проверява дали скобите (), [] и {} са затворени в правилния ред. Напиши IsBalanced(string text) със стек: при отваряща скоба я слагаш в стека, при затваряща махаш горната и проверяваш дали е от същия вид. Накрая стекът трябва да е празен. Прочети три реда.

Вход
(1 + [2 * 3])
(1 + 2]
((5)
Изход
(1 + [2 * 3]) -> да
(1 + 2] -> не
((5) -> не

5. Свой свързан списък. Клас MyLinkedList с възлите от урока и методи Add(string value) (в края), Remove(string value), Contains(string value), свойство Count и ToString(). При Remove намери възела преди търсения и пренасочи неговия Next. Отделно провери случая, когато се маха първият.

Изход
[Фактура, Отчет, Среща]
Има ли Отчет: True
След триене: [Фактура, Среща]
Размер: 2

Още задачи

  • Отмени и Повтори. Пази два стека: undo и redo. Ново действие отива в undo и изчиства redo. „Отмени“ мести горното от undo в redo, а „Повтори“ го връща обратно.
  • Думите наобратно. Прочети изречение и го отпечатай с думите в обратен ред, като минеш през стек: „Днес е петък“ става „петък е Днес“.
  • Две каси. Клиентите идват един по един и отиват на касата с по-къса опашка. Отпечатай кой на коя каса е обслужен.
  • Обърни свързания списък. Добави на MyLinkedList метод Reverse(), който обръща стрелките, без да прави нови възли.

Тест

Провери се

1. В стек се слагат А, после Б, после В. Кое излиза първо при Pop?
2. Кое е за опашка?
3. Какво става при Dequeue() на празна Queue<string>?
4. Защо вмъкването в началото на свързан списък е бързо?
5. Кое е бавно при свързан списък?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·