Стек и опашка в JavaScript

Проблем

Имейлът за поръчката излиза празен

Магазинът праща имейл за всяка поръчка по шаблон: Поръчка {order}: [{items}] (общо {total} €). Шаблоните се пишат на ръка и понякога една скоба не се затваря или се затваря с грешната. Тогава програмата за имейли не попълва нищо и клиентът получава празно писмо.

Искаш преди изпращане да кажеш: „шаблонът е наред“ или „грешка на позиция 25“. Броенето на скобите не стига: в [{items}) отворените са две и затворените са две, а грешката е там.

В урока за колекциите „Стек, опашка и свързан списък“ стекът и опашката бяха готови: масивът. Тук ги правиш сам, за да видиш какво струва всяка операция и къде е капанът.

Идеята

Стек върху растящ масив

Скобите се затварят в обратен ред: последната отворена се затваря първа. Това е стек: слагаш отгоре и взимаш отгоре.

Отвътре стекът е масив и брояч size:

push пише на място size и увеличава брояча;
pop намалява брояча и връща това, което е там;
когато масивът се напълни, става два пъти по-голям, както в амортизираната сложност.

class CharStack {
  constructor() {
    this.items = new Array(4);
    this.size = 0;
  }

  push(c) {
    if (this.size === this.items.length) {
      const bigger = new Array(this.size * 2);
      for (let i = 0; i < this.size; i++) bigger[i] = this.items[i];
      this.items = bigger;
    }
    this.items[this.size] = c;
    this.size++;
  }

  pop() {
    if (this.size === 0) throw new Error("празен стек");
    this.size--;
    return this.items[this.size];
  }

  isEmpty() {
    return this.size === 0;
  }
}

И push, и pop работят само с края на масива. Нищо не се мести, затова двете са O(1) (push е O(1) средно заради растенето).

В JavaScript масивът вече расте сам, а push и pop() са точно push и pop на стека. Тук масивът се удвоява на ръка, за да се види какво прави двигателят вместо теб.

Виж го

Проверката на шаблона

Минаваш по шаблона знак по знак:

отваряща скоба отива в стека;
затваряща взима горната от стека и проверява, че е от същия вид;
ако стекът е празен при затваряща или не е празен накрая, шаблонът е грешен.

function firstError(text) {
  const opened = new CharStack();
  for (let i = 0; i < text.length; i++) {
    const c = text[i];
    if ("([{".includes(c)) {
      opened.push(c);
    } else if (")]}".includes(c)) {
      if (opened.isEmpty()) return i;
      if ("([{".indexOf(opened.pop()) !== ")]}".indexOf(c)) return i;
    }
  }
  return opened.isEmpty() ? -1 : text.length;
}

const templates = [
  "Поръчка {order}: [{items}] (общо {total} €)",
  "Поръчка {order}: [{items}) (общо {total} €)",
  "Поръчка {order}: [{items}] (общо {total} €",
];
for (const t of templates) {
  const at = firstError(t);
  console.log(at < 0 ? "OK" : `грешка на позиция ${at}`);
}

OK
грешка на позиция 25
грешка на позиция 42

Във втория шаблон ) идва, когато отгоре в стека е [: грешка на позиция 25. В третия ( не се затваря и грешката е в края, на позиция 42, колкото е дължината на текста.

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

Истински проверител на JSON прескача и скобите вътре в текст в кавички: "[1" не отваря нищо. Тогава стекът пази и „сега съм в текст“. Същото е с таговете в HTML: стекът пази имената на отворените тагове, а </div> трябва да срещне отгоре div.

Пробвай

Предвиди изхода

console.log(firstError("({total)}"));

Отговор

-1

Проблем

Сутрешната опашка за доставки

В 8 сутринта в системата чакат 10 000 заявки за доставка. Куриерите ги взимат една по една, най-старата първа: това е опашка. Някой я е написал с обикновен списък:

const jobs = [];
for (let id = 1; id <= 10_000; id++) {
  jobs.push(`#${id}`);
}
let done = 0;
while (jobs.length > 0) {
  const job = jobs.shift();
  done++;
}
console.log(`обработени: ${done}`);

обработени: 10000

Изглежда невинно, но jobs.shift() маха от място 0 на масив. Всички след първия се местят с едно място напред. При 10 000 чакащи първото вземане мести 9 999, второто 9 998… Заедно са около 50 милиона премествания само за да вземеш всеки по веднъж.

Идеята

Пръстенов буфер: мести се head, не поръчките

Не мести поръчките. Мести показалеца към първата.

head е мястото на първата поръчка, а size е колко чакат.
Вземането чете items[head], изчиства мястото и мести head с едно напред. Никой друг не се мести.
Новата поръчка отива на tail = (head + size) % места. Остатъкът при деление прави масива на кръг: след последното място идва първото. Празните места отпред, които вземането е освободило, се ползват пак.
Когато всички места са заети, grow прави масив два пъти по-голям и копира поръчките в реда на опашката, от head нататък. После head е 0.

Такъв масив, в който краят продължава от началото, се казва пръстенов буфер (ring buffer или circular buffer).

class JobQueue {
  constructor() {
    this.items = new Array(4).fill(null);
    this.head = 0;
    this.size = 0;
  }

  enqueue(job) {
    if (this.size === this.items.length) this.grow();
    const tail = (this.head + this.size) % this.items.length;
    this.items[tail] = job;
    this.size++;
  }

  dequeue() {
    if (this.size === 0) {
      throw new Error("празна опашка");
    }
    const job = this.items[this.head];
    this.items[this.head] = null;
    this.head = (this.head + 1) % this.items.length;
    this.size--;
    return job;
  }

  isEmpty() {
    return this.size === 0;
  }

  grow() {
    const n = this.items.length;
    const bigger = new Array(n * 2).fill(null);
    for (let i = 0; i < this.size; i++) {
      bigger[i] = this.items[(this.head + i) % n];
    }
    this.items = bigger;
    this.head = 0;
  }
}

За да виждаш какво е вътре, класът има и метод за печат:

toString() {
  const shown = this.items.map((s) => s ?? "-").join(", ");
  return `[${shown}] head=${this.head}`;
}

Виж го

head, tail и връщането в началото

Три поръчки влизат, две излизат, после още три. Последната от тях не е след края на масива, а на място 0. После масивът е пълен и седмата поръчка го кара да расте:

class JobQueue {
  constructor() {
    this.items = new Array(4).fill(null);
    this.head = 0;
    this.size = 0;
  }

  enqueue(job) {
    if (this.size === this.items.length) this.grow();
    const tail = (this.head + this.size) % this.items.length;
    this.items[tail] = job;
    this.size++;
  }

  dequeue() {
    if (this.size === 0) {
      throw new Error("празна опашка");
    }
    const job = this.items[this.head];
    this.items[this.head] = null;
    this.head = (this.head + 1) % this.items.length;
    this.size--;
    return job;
  }

  isEmpty() {
    return this.size === 0;
  }

  grow() {
    const n = this.items.length;
    const bigger = new Array(n * 2).fill(null);
    for (let i = 0; i < this.size; i++) {
      bigger[i] = this.items[(this.head + i) % n];
    }
    this.items = bigger;
    this.head = 0;
  }
}

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

Опашка за доставки върху масив с 4 места. head е мястото на първата поръчка, size е колко чакат.
enqueue: новата поръчка отива на (head + size) % 4. Три поръчки заемат места 0, 1 и 2.
dequeue взима поръчката на head и мести head напред. Никой друг не се мести: #103 си стои на място 2.
#104: (2 + 1) % 4 = 3, последното място на масива.
#105: (2 + 2) % 4 = 0. Краят на масива се връща в началото и празните места отпред се ползват пак.
#106 отива на място 1. Вече са 4 от 4: масивът е пълен, а първият на опашката е на място 2.
#107 не се побира. grow прави 8 места и копира в реда на опашката, от head нататък: #103, #104, #105, #106. head става 0.
#107 отива на място 4. Едно копиране на поръчка при растене и нито едно при вземане отпред.

const q = new JobQueue();
for (let id = 101; id <= 103; id++) q.enqueue(`#${id}`);
console.log(String(q));
console.log(`доставка: ${q.dequeue()}`);
console.log(`доставка: ${q.dequeue()}`);
console.log(String(q));
for (let id = 104; id <= 106; id++) q.enqueue(`#${id}`);
console.log(String(q));
q.enqueue("#107");
console.log(String(q));

[#101, #102, #103, -] head=0
доставка: #101
доставка: #102
[-, -, #103, -] head=2
[#105, #106, #103, #104] head=2
[#103, #104, #105, #106, #107, -, -, -] head=0

Виж третия ред на изхода: [#105, #106, #103, #104] head=2. Първата на опашката е #103, на място 2, а #105 и #106 са отпред, защото там е имало свободни места. Подредбата в масива не е подредбата на опашката. Затова grow не копира едно към едно.

Пробвай

Къде отиват #205 и #206?

const q = new JobQueue();
for (let id = 201; id <= 204; id++) q.enqueue(`#${id}`);
q.dequeue();
q.dequeue();
q.dequeue();
q.enqueue("#205");
q.enqueue("#206");
console.log(String(q));

Отговор

[#205, #206, -, #204] head=3

[#204, #205, #206, -] head=0

[-, -, -, #204, #205, #206, -, -] head=3

Пробвай

Попълни

Новата поръчка отива на място:

const tail = (this.head + this.size) % ;

Идеята

Колко струва

Броим преместванията на вече записани заявки: копията при растене и местенето напред при вземане от място 0. И двете опашки започват с 4 места и се удвояват. 10 000 заявки влизат, после всички излизат:

function shiftMoves(n) {
  let items = new Array(4);
  let size = 0;
  let moves = 0;
  for (let job = 1; job <= n; job++) {
    if (size === items.length) {
      const bigger = new Array(size * 2);
      for (let i = 0; i < size; i++) bigger[i] = items[i];
      moves += size;
      items = bigger;
    }
    items[size++] = job;
  }
  while (size > 0) {
    for (let i = 1; i < size; i++) {
      items[i - 1] = items[i];
      moves++;
    }
    size--;
  }
  return moves;
}

function ringMoves(n) {
  let items = new Array(4);
  let head = 0;
  let size = 0;
  let moves = 0;
  for (let job = 1; job <= n; job++) {
    if (size === items.length) {
      const bigger = new Array(size * 2);
      for (let i = 0; i < size; i++) {
        bigger[i] = items[(head + i) % items.length];
        moves++;
      }
      items = bigger;
      head = 0;
    }
    items[(head + size) % items.length] = job;
    size++;
  }
  while (size > 0) {
    head = (head + 1) % items.length;
    size--;
  }
  return moves;
}

for (const n of [1000, 10000]) {
  console.log(`${n}: списък ${shiftMoves(n)}, пръстен ${ringMoves(n)}`);
}

1000: списък 500520, пръстен 1020
10000: списък 50011380, пръстен 16380

Пусни го и до 100 000:

Списък: махни от място 0 O(n²)
Пръстенов буфер O(n)

Алгоритъм	n = 10	n = 1000	n = 10 000	n = 100 000
Списък: махни от място 0	57	500 520	50 011 380	≈ 5 001 138 000
Пръстенов буфер	12	1020	16 380	131 068

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

При 10 000 заявки списъкът прави 50 011 380 премествания, а пръстенът 16 380, и всички те са от растенето. Вземане от място 0 е O(n), затова n вземания са O(n²). В пръстена вземането е O(1), а добавянето е O(1) средно, като стека.

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

Как е в езиците:

Java: ArrayDeque е пръстенов буфер: масив elements и индекси head и tail. Едно място винаги остава празно, за да се различи „празна“ (head == tail) от „пълна“, затова масивът отначало е с 17 места за 16 елемента. Когато се напълни, при малък масив расте малко над два пъти, а при голям с 50%.
C#: Queue<T> е пръстенов буфер с _array, _head, _tail и _size. Започва с 4 места и при пълен масив го удвоява. Stack<T> е масив, който също се удвоява.
Python: collections.deque не е пръстенов буфер, а свързан списък от блокове по 64 места. Затова и двата края са O(1). list.pop(0) е O(n), точно като в проблема.
JavaScript: вградена опашка няма. shift() мести всички елементи на масива. V8 понякога го прави бързо, като премества началото на масива, вместо да мести елементите, но при големи масиви не, и не е обещано. За голяма опашка се пише пръстен като тук или опашка от възли.

Някои пръстени пазят tail вместо size, а други и двете. Това е само друг запис на същото: tail = (head + size) % места.

Пробвай

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

Някой е написал grow по-кратко. Поръчките до растенето излизат наред, а после разбъркано:

grow() {
  const n = this.items.length;
  const bigger = new Array(n * 2).fill(null);
  for (let i = 0; i < this.size; i++) {
    bigger[i] = this.items[i];
  }
  this.items = bigger;
  this.head = 0;
}

const q = new JobQueue();
for (let id = 101; id <= 103; id++) q.enqueue(`#${id}`);
q.dequeue();
q.dequeue();
for (let id = 104; id <= 107; id++) q.enqueue(`#${id}`);
const order = [];
while (!q.isEmpty()) order.push(q.dequeue());
console.log(order.join(" "));

#105 #106 #103 #104 #107

На кой ред е грешката?

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

Упражнение

Последните 5 реда от лога

Реши задачата в редактора си.

Последните 5 реда. Сървърът на магазина пише ред в лога за всяко действие. При грешка искаш да видиш последните 5 реда, а не целия лог. Напиши LastLines с пръстен от 5 места, който никога не расте: докато има място, редът влиза на (head + size) % 5; когато е пълен, новият ред пише върху най-стария (на head), а head се мести напред. Метод lines() връща редовете от най-стария към най-новия. Подай му осемте реда:

09:00 вход: ана
09:02 кошница: +2
09:03 плащане: 48 €
09:05 изход: ана
09:07 вход: иво
09:08 търсене: кафе
09:09 кошница: +1
09:11 плащане: 12 €

Последните 5:
09:05 изход: ана
09:07 вход: иво
09:08 търсене: кафе
09:09 кошница: +1
09:11 плащане: 12 €

Още задачи

Скоби и тагове. Разшири проверката на шаблона и за таговете <b>…</b> и <i>…</i>: стекът пази имената на отворените тагове.
Опашка, която се свива. Ако след сутрешния пик в опашката с 8192 места чакат 10 заявки, паметта стои празна. Накарай опашката да намалява масива наполовина, когато е пълна под една четвърт. Защо не под половината?
Стек от две опашки. Направи стек само с две свои опашки. Колко струва pop?

Тест

Провери се

1. Защо стекът проверява скобите, а не просто брои отворените и затворените?Защото броенето е по-бавноЗащото броят не работи с повече от 10 скобиЗащото последната отворена скоба трябва да се затвори първа, а броят не знае коя е последната

2. Опашка с 10 000 чакащи е върху обикновен списък и всяко вземане е от място 0. Колко премествания струва едно вземане отпред?Около толкова, колкото чакат след него: всички се местят с едно място напредЕдноНито едно

3. Пръстенов буфер с 8 места: head = 6, size = 3. На кое място отива новата поръчка?На 0На 9На 1

4. Пръстеновият буфер е пълен и трябва да расте. Защо grow не може просто да копира items[0], items[1]… в новия масив?Защото новият масив е по-малъкМоже: местата са същитеЗащото първият на опашката е на head, не на 0; копирането трябва да е в реда на опашката, от head нататък

Стек и опашка

Бисквитки