Домашнее задание

Практическая часть по стеку

1. Перевернуть строку через стек -> Дана строка "hello". Ее нужно перевернуть и вернуть "olleh"
2. Удаление последовательных дубликатов -> Удалите повторяющиеся последовательные символы из строки, используя стек. Строка"abbaca" должна быть преобразована в "ca"
3. https://leetcode.com/problems/valid-parentheses/?envType=study-plan-v2&envId=top-interview-150
4. https://leetcode.com/problems/evaluate-reverse-polish-notation/description/?envType=study-plan-v2&envId=top-interview-150

Практическая часть по очереди

1. Симулируйте процесс обслуживания покупателей в магазине с помощью очереди. Каждый покупатель, заходящий в магазин, добавляется в очередь и затем обслуживается в порядке их прибытия. Создайте функцию, которая будет регистрировать покупателей в очереди и выводить информацию о том, кто обслужен.
2. Симулируйте очередь клиентов в банке, где каждый клиент представляет операцию, такую как вклад или снятие средств. Клиенты приходят в банк и встают в очередь. Каждый клиент обслуживается строго в порядке прибытия, следуя принципу FIFO. Создайте функцию, которая добавляет клиентов в очередь и обрабатывает каждую операцию, выводя результаты выполненных операций по мере обслуживания клиентов.
3. https://leetcode.com/problems/first-unique-character-in-a-string/description/
4. https://leetcode.com/problems/design-circular-deque/description/

Ответы на вопросы

Стек

Задача 1

function reverseString(str) {
  const stack = [];
  for (let char of str) {
    stack.push(char);
  }
  let reversedStr = "";
  while (stack.length > 0) {
    reversedStr += stack.pop();
  }
  return reversedStr;
}

console.log(reverseString("hello")); // "olleh"

Задача 2

function removeDuplicates(str) {
  const stack = [];
  for (let char of str) {
    if (stack.length > 0 && stack[stack.length - 1] === char) {
      stack.pop();
    } else {
      stack.push(char);
    }
  }
  return stack.join("");
}

console.log(removeDuplicates("abbaca")); // "ca"

Задача 3

function isValid(s) {
  const stack = [];
  const map = {
    "(": ")",
    "{": "}",
    "[": "]",
  };

  for (let char of s) {
    if (map[char]) {
      stack.push(char);
    } else {
      const top = stack.pop();
      if (map[top] !== char) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

Задача 4

function evalRPN(tokens) {
  const stack = [];
  const operators = new Set(["+", "-", "*", "/"]);

  for (let token of tokens) {
    if (!operators.has(token)) {
      stack.push(Number(token));
    } else {
      const b = stack.pop();
      const a = stack.pop();
      let result;
      switch (token) {
        case "+":
          result = a + b;
          break;
        case "-":
          result = a - b;
          break;
        case "*":
          result = a * b;
          break;
        case "/":
          result = Math.trunc(a / b);
          break;
      }
      stack.push(result);
    }
  }

  return stack.pop();
}

Очередь

Задача 1

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) return "Queue is empty";
    return this.items.shift();
  }

  isEmpty() {
    return this.items.length === 0;
  }

  front() {
    if (this.isEmpty()) return "Queue is empty";
    return this.items[0];
  }

  printQueue() {
    return this.items.join(" ");
  }
}

function serveCustomers(customers) {
  const queue = new Queue();
  customers.forEach((customer) => queue.enqueue(customer));

  while (!queue.isEmpty()) {
    const servedCustomer = queue.dequeue();
    console.log(`Served customer: ${servedCustomer}`);
  }
}

const customers = ["Customer 1", "Customer 2", "Customer 3"];
serveCustomers(customers);

Задача 2

class BankQueue extends Queue {
  processOperations() {
    while (!this.isEmpty()) {
      const customer = this.dequeue();
      console.log(`Processing ${customer.operation} for ${customer.name}`);
      // Логика обработки операции (вклад, снятие и т.д.)
    }
  }
}

const bankQueue = new BankQueue();
bankQueue.enqueue({ name: "Customer 1", operation: "deposit" });
bankQueue.enqueue({ name: "Customer 2", operation: "withdrawal" });
bankQueue.enqueue({ name: "Customer 3", operation: "deposit" });

bankQueue.processOperations();

Задача 3

function firstUniqChar(s) {
  const charCount = {};

  for (let char of s) {
    charCount[char] = (charCount[char] || 0) + 1;
  }

  for (let i = 0; i < s.length; i++) {
    if (charCount[s[i]] === 1) {
      return i;
    }
  }

  return -1;
}

Задача 4

class MyCircularDeque {
  constructor(k) {
    this.k = k;
    this.deque = [];
  }

  insertFront(value) {
    if (this.deque.length < this.k) {
      this.deque.unshift(value);
      return true;
    }
    return false;
  }

  insertLast(value) {
    if (this.deque.length < this.k) {
      this.deque.push(value);
      return true;
    }
    return false;
  }

  deleteFront() {
    if (this.deque.length > 0) {
      this.deque.shift();
      return true;
    }
    return false;
  }

  deleteLast() {
    if (this.deque.length > 0) {
      this.deque.pop();
      return true;
    }
    return false;
  }

  getFront() {
    return this.deque.length === 0 ? -1 : this.deque[0];
  }

  getRear() {
    return this.deque.length === 0 ? -1 : this.deque[this.deque.length - 1];
  }

  isEmpty() {
    return this.deque.length === 0;
  }

  isFull() {
    return this.deque.length === this.k;
  }
}