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

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

Проблем

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

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

const actions = [];
actions.push("Въведе текст");
actions.push("Удебели заглавието");
actions.push("Вмъкна снимка");


// Ctrl+Z: отмени последното действие.
const undone = actions.shift();
console.log(`Отменено: ${undone}`);
console.log("Остава:", actions);
Изход
Отменено: Въведе текст
Остава: [ 'Удебели заглавието', 'Вмъкна снимка' ]

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

Идеята

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

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

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

const history = [];
history.push("Начало");
history.push("Лаптопи");
history.push("Лаптоп 14 инча");
console.log(`Сега: ${history.at(-1)}`);


history.pop();
console.log(`Назад: ${history.at(-1)}`);
console.log(history);
Изход
Сега: Лаптоп 14 инча
Назад: Лаптопи
[ 'Начало', 'Лаптопи' ]

Отделен клас за стек в JavaScript няма: масивът е стек, ако слагаш и взимаш само от края.

  • push слага отгоре, pop() маха и връща горния, at(-1) само поглежда горния.
  • Отгоре е краят на масива. И двете операции са бързи, защото в края нищо не се мести.
  • console.log печата стека отдолу нагоре: горният е последен.
По-точно, за любопитните
  • pop() и at(-1) на празен масив не спират програмата, а дават undefined:
const history = [];
console.log(history.pop());
console.log(history.at(-1));
Изход
undefined
undefined

Затова провери history.length, преди да вземеш.

Пробвай

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

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

const undo = [];
undo.push("шрифт");
undo.push("цвят");
undo.push("размер");
undo.pop();
undo.push("подчертаване");
while (undo.length > 0) {
  console.log(undo.pop());
}
Отговор

Идеята

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

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

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

const printer = [];
printer.push("фактура.pdf");
printer.push("договор.docx");
printer.push("снимка.jpg");
console.log(`Следващ: ${printer[0]}`);


while (printer.length > 0) {
  console.log(`Печатам ${printer.shift()}`);
}
console.log("Опашка:", printer);
Изход
Следващ: фактура.pdf
Печатам фактура.pdf
Печатам договор.docx
Печатам снимка.jpg
Опашка: []

Отделен клас за опашка в JavaScript няма. Масивът става опашка, ако слагаш отзад и взимаш отпред:

  • push слага отзад, shift маха и връща първия, printer[0] поглежда първия.
  • shift на празен масив дава undefined, а не спира програмата.

shift обаче има цена. Той мести всички останали с едно място напред, като вмъкването отпред в урока за масивите. При няколко заявки към принтера това не се усеща. При опашка с десетки хиляди елементи е много пъти по-бавно, отколкото само да четеш поред. Тогава се ползва свързаният списък от следващата карта, който пази и първия, и последния възел.

По-точно, за любопитните
  • shift на празна опашка:
const clients = ["Клиент 1"];
console.log(`Обслужен: ${clients.shift()}`);
console.log(clients.shift());
Изход
Обслужен: Клиент 1
undefined
  • Двигателят V8 понякога прави shift бърз, като премества началото на масива, вместо да мести елементите. При големи масиви това не става. Не разчитай на него.

Пробвай

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

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

const checkout = [];
checkout.push("Иван");
checkout.push("Мария");
const client = checkout.();
console.log(`Заповядай, ${client}`);

Виж го

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

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

class Node {
  constructor(value, next) {
    this.value = value;
    this.next = next;
  }
}

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

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


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

Идеята

Масивът и кое кога

Готов свързан списък в JavaScript няма. Масивът може да добавя и маха в двата края: push и pop отзад, unshift и shift отпред:

const route = [];
route.push("Пловдив");
route.push("Стара Загора");
route.unshift("София");
route.push("Бургас");
console.log(route);


route.splice(route.indexOf("Стара Загора"), 1);
console.log("След промяната:", route);
console.log(`От ${route[0]} до ${route.at(-1)}`);
Изход
[ 'София', 'Пловдив', 'Стара Загора', 'Бургас' ]
След промяната: [ 'София', 'Пловдив', 'Бургас' ]
От София до Бургас

Кое кога:

  • Списък по номер: масив. Това е обичайният избор.
  • Стек: масив с push и pop.
  • Опашка: масив с push и shift, докато е малка. Голяма опашка с хиляди елементи: свързан списък като този от предишната карта, който пази и последния възел.
По-точно, за любопитните
  • unshift е като shift: мести всички елементи с едно място, затова отпред е бавен при голям масив.
  • Защо масивът обикновено е по-бърз от свързан списък, дори при вмъкване? Всеки възел е отделен обект някъде в паметта, а процесорът чете най-бързо данни, които стоят една до друга. Масивът е точно такъв.
  • Възелът от тази карта има само next. Такъв списък се казва едносвързан.

Пробвай

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

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

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

Упражнение

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

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

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

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

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

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

3. Борсов тикер. Клас StockTicker пази последните N цени на една акция. Конструкторът получава символа и N. updatePrice(price) добавя цена, а ако цените станат повече от N, маха най-старата. Добави getLastPrice() и average() за пазените цени. За SAP с N = 3 подай цените 150, 152, 149 и 155. Подсказка: at(-1) е последната цена. Цените печатай с два знака след точката, с toFixed(2).

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

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

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

5. Свой свързан списък. Клас MyLinkedList с възлите от урока и методи add(value) (в края), remove(value), contains(value), size() и toString(). При remove намери възела преди търсения и пренасочи неговия next. Отделно провери случая, когато се маха първият.

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

Още задачи

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

Тест

Провери се

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

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