Дек.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ограничение времени\t2 секунды  \n",
    "Ограничение памяти\t64Mb  \n",
    "\n",
    "Ввод\tстандартный ввод или input.txt  \n",
    "Вывод\tстандартный вывод или output.txt  \n",
    "\n",
    "Гоша реализовал структуру данных Дек, максимальный размер которого определяется заданным числом. Методы push_back(x), push_front(x), pop_back(), pop_front() работали корректно. Но, если в деке было много элементов, программа работала очень долго. Дело в том, что не все операции выполнялись за O(1). Помогите Гоше! Напишите эффективную реализацию.\n",
    "\n",
    "Внимание: при реализации используйте кольцевой буфер.\n",
    "\n",
    "Формат ввода  \n",
    "В первой строке записано количество команд n — целое число, не превосходящее 100000. Во второй строке записано число m — максимальный размер дека. Он не превосходит 50000. В следующих n строках записана одна из команд:\n",
    "\n",
    "push_back(value) – добавить элемент в конец дека. Если в деке уже находится максимальное число элементов, вывести «error».\n",
    "push_front(value) – добавить элемент в начало дека. Если в деке уже находится максимальное число элементов, вывести «error».\n",
    "pop_front() – вывести первый элемент дека и удалить его. Если дек был пуст, то вывести «error».\n",
    "pop_back() – вывести последний элемент дека и удалить его. Если дек был пуст, то вывести «error».\n",
    "Value — целое число, по модулю не превосходящее 1000.\n",
    "\n",
    "Формат вывода  \n",
    "Выведите результат выполнения каждой команды на отдельной строке. Для успешных запросов push_back(x) и push_front(x) ничего выводить не надо."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import Optional\n",
    "\n",
    "\n",
    "class StackOverFlow(Exception):\n",
    "    \"\"\"Вызывается при добавлении элемента в полный дек.\"\"\"\n",
    "\n",
    "    pass\n",
    "\n",
    "\n",
    "class StackEmpty(Exception):\n",
    "    \"\"\"Вызывается при удалении элемента из пустого дек.\"\"\"\n",
    "\n",
    "    pass\n",
    "\n",
    "\n",
    "class Deque:\n",
    "    \"\"\"Класс двухсторонней очереди.\"\"\"\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.queue = [None] * n\n",
    "        self.max_n = n\n",
    "        self.head = 0\n",
    "        self.tail = 1\n",
    "        self.size = 0\n",
    "\n",
    "    def is_empty(self) -> None:\n",
    "        \"\"\"Проверка на пустоту.\"\"\"\n",
    "        if self.size == 0:\n",
    "            raise StackEmpty('error')\n",
    "\n",
    "    def is_full(self) -> None:\n",
    "        \"\"\"Проверка на переполненность.\"\"\"\n",
    "        if self.size == self.max_n:\n",
    "            raise StackOverFlow('error')\n",
    "\n",
    "    def push_front(self, value: str) -> None:\n",
    "        \"\"\"Добавить элемент в начало очереди.\"\"\"\n",
    "        self.is_full()\n",
    "        self.queue[self.head] = value\n",
    "        self.head = (self.head - 1) % self.max_n\n",
    "        self.size += 1\n",
    "\n",
    "    def push_back(self, value: str) -> None:\n",
    "        \"\"\"Добавить элемент в конец очереди.\"\"\"\n",
    "        self.is_full()\n",
    "        self.queue[self.tail] = value\n",
    "        self.tail = (self.tail + 1) % self.max_n\n",
    "        self.size += 1\n",
    "\n",
    "    def pop_back(self) -> str:\n",
    "        \"\"\"Убрать элемент с конца очереди.\"\"\"\n",
    "        self.is_empty()\n",
    "        self.tail = (self.tail - 1) % self.max_n\n",
    "        out_element = self.queue[self.tail]\n",
    "        self.queue[self.tail] = None\n",
    "        self.size -= 1\n",
    "        return out_element\n",
    "\n",
    "    def pop_front(self) -> str:\n",
    "        \"\"\"Убрать элемент с начала очереди.\"\"\"\n",
    "        self.is_empty()\n",
    "        self.head = (self.head + 1) % self.max_n\n",
    "        out_element = self.queue[self.head]\n",
    "        self.queue[self.head] = None\n",
    "        self.size -= 1\n",
    "        return out_element\n",
    "\n",
    "\n",
    "def run_command(deque) -> Optional[str]:\n",
    "    \"\"\"Получает и выполняет команду для переданного дека\"\"\"\n",
    "    command, *arg = input().split()\n",
    "    try:\n",
    "        return getattr(deque, command)(*arg)\n",
    "    except Exception as error:\n",
    "        return error\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    commands_counter = int(input())\n",
    "    max_size = int(input())\n",
    "    deque = Deque(max_size)\n",
    "\n",
    "    for i in range(commands_counter):\n",
    "        result = run_command(deque)\n",
    "        if result:\n",
    "            print(result)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.6"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}