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

Проблем

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

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

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

// Ctrl+Z: отмени последното действие.
String undone = actions.remove(0);
System.out.println("Отменено: " + undone);
System.out.println("Остава: " + actions);

Отменено: Въведе текст
Остава: [Удебели заглавието, Вмъкна снимка]

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

Идеята

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

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

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

Deque<String> history = new ArrayDeque<>();
history.push("Начало");
history.push("Лаптопи");
history.push("Лаптоп 14 инча");
System.out.println("Сега: " + history.peek());

history.pop();
System.out.println("Назад: " + history.peek());
System.out.println(history);

Сега: Лаптоп 14 инча
Назад: Лаптопи
[Лаптопи, Начало]

push слага отгоре, pop маха и връща горния, peek само поглежда горния.
Deque е интерфейсът, а ArrayDeque е класът. И двата са в java.util.
println печата стека отгоре надолу.

По-точно, за любопитните

pop на празен стек спира програмата с java.util.NoSuchElementException. peek на празен стек връща null.
Java има и по-стар клас Stack. Той работи, но документацията на Java препоръчва ArrayDeque:

Stack<String> stack = new Stack<>();
stack.push("Google");
stack.push("Apple");
stack.push("Microsoft");
System.out.println("На върха: " + stack.peek());
while (!stack.isEmpty()) {
    System.out.println("Изваден: " + stack.pop());
}

На върха: Microsoft
Изваден: Microsoft
Изваден: Apple
Изваден: Google

Пробвай

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

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

Deque<String> undo = new ArrayDeque<>();
undo.push("шрифт");
undo.push("цвят");
undo.push("размер");
undo.pop();
undo.push("подчертаване");
while (!undo.isEmpty()) {
    System.out.println(undo.pop());
}

Отговор

подчертаване
цвят
шрифт

шрифт
цвят
подчертаване

шрифт
цвят
размер

подчертаване
размер
цвят
шрифт

Идеята

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

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

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

Queue<String> printer = new ArrayDeque<>();
printer.offer("фактура.pdf");
printer.offer("договор.docx");
printer.offer("снимка.jpg");
System.out.println("Следващ: " + printer.peek());

while (!printer.isEmpty()) {
    System.out.println("Печатам " + printer.poll());
}
System.out.println("Опашка: " + printer);

Следващ: фактура.pdf
Печатам фактура.pdf
Печатам договор.docx
Печатам снимка.jpg
Опашка: []

offer слага отзад, poll маха и връща първия, peek поглежда първия.
Типът е интерфейсът Queue, а класът пак е ArrayDeque. Той може и двете: да е стек и да е опашка. Името идва от double-ended queue, опашка с два края.
poll и peek на празна опашка връщат null.

По-точно, за любопитните

Има и add, remove() и element(). Те правят същото, но при празна опашка хвърлят изключение, вместо да върнат null.
В старите примери опашката е LinkedList. И това работи, защото LinkedList също изпълнява Queue:

Queue<String> clients = new LinkedList<>();
clients.offer("Клиент 1");
clients.offer("Клиент 2");
System.out.println("Обслужен: " + clients.poll());
System.out.println("Чака: " + clients);

Обслужен: Клиент 1
Чака: [Клиент 2]

ArrayDeque не приема null като елемент. Иначе poll нямаше как да каже „празно е“.

Пробвай

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

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

Queue<String> checkout = new ArrayDeque<>();
checkout.offer("Иван");
checkout.offer("Мария");
String next = checkout.();
System.out.println("Заповядай, " + next);

Виж го

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

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

class Node {
    String value;
    Node next;

    Node(String value, Node next) {
        this.value = value;
        this.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) {
    System.out.println(n.value);
}

Стъпка по стъпка, с думи

Списъкът е празен: head сочи към null.
Нов възел: next е старият head (null), а head се премества на възела.
Вторият възел сочи към първия. Нищо не се мести в паметта, сменят се само стрелките.
Третият възел също влиза отпред: последното добавено е първо.
n тръгва от head и печата всеки възел.
n стига null: цикълът спира.

Вмъкване отпред: нов възел, чийто next сочи стария първи, и head сочи новия. Две стрелки, без да местиш нищо.
Обхождане: тръгваш от head и минаваш по next, докато не стигнеш null.
Цената: възлите нямат индекси. До петия елемент се стига, като минеш през първите четири.

Идеята

LinkedList и кое кога

Java има готов свързан списък: LinkedList. Той изпълнява и List, и Deque, затова има add, get, remove, но и addFirst, addLast, getFirst:

LinkedList<String> route = new LinkedList<>();
route.add("Пловдив");
route.add("Стара Загора");
route.addFirst("София");
route.addLast("Бургас");
System.out.println(route);

route.remove("Стара Загора");
System.out.println("След промяната: " + route);
System.out.println("От " + route.getFirst() + " до " + route.getLast());

[София, Пловдив, Стара Загора, Бургас]
След промяната: [София, Пловдив, Бургас]
От София до Бургас

Кое кога:

Списък по номер: ArrayList. Това е обичайният избор.
Стек или опашка: ArrayDeque.
LinkedList: рядко. Работи и за двете, но обикновено е по-бавен от тях.

По-точно, за любопитните

Защо LinkedList губи, дори при вмъкване? Всеки възел е отделен обект някъде в паметта, а процесорът чете най-бързо данни, които стоят една до друга. Масивът зад ArrayList и ArrayDeque е точно такъв. На практика LinkedList печели само ако често вмъкваш или махаш в средата през итератор, който вече е стигнал дотам.
LinkedList пази стрелки в двете посоки, към следващия и към предишния. Затова getLast и removeLast също са бързи. Възелът от тази карта има само next. Такъв списък се казва едносвързан.

Пробвай

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

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

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

Упражнение

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

Реши задачите в редактора си. Колекцията е 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. Подсказка: Deque има peekLast().

SAP: последна цена 155.0 €
Средно за последните 3: 152.0 €

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), size() и toString(). При remove намери възела преди търсения и пренасочи неговия next. Отделно провери случая, когато се маха първият.

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

Още задачи

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

Тест

Провери се

1. В стек се слагат А, после Б, после В. Кое излиза първо при pop?АБВ

2. Кое е за опашка?Бутонът „Назад“ в браузъраЗаявките към принтер, които се печатат по реда на пристиганеОтмяната на последното действие

3. Какво връща poll() на празна ArrayDeque?0nullХвърля NoSuchElementException

4. Защо вмъкването в началото на свързан списък е бързо?Защото списъкът се подрежда самЗащото се прави нов възел и се местят две стрелки, без да се пипат останалите елементиЗащото елементите стоят един до друг в паметта

5. Кое е бавно при свързан списък?Взимане на елемент по номер, например петстотнияДобавяне в началотоМахане на първия елемент

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

Бисквитки