Untitled1.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ArrayQueue:\n",
    "  \"\"\"FIFO queue implementation using a Python list as underlying storage.\"\"\"\n",
    "  DEFAULT_CAPACITY = 10          # moderate capacity for all new queues\n",
    "\n",
    "  def __init__(self):\n",
    "    \"\"\"Create an empty queue.\"\"\"\n",
    "    self._data = [None] * ArrayQueue.DEFAULT_CAPACITY\n",
    "    self._size = 0\n",
    "    self._front = 0\n",
    "\n",
    "  def __len__(self):\n",
    "    \"\"\"Return the number of elements in the queue.\"\"\"\n",
    "    return self._size\n",
    "\n",
    "  def is_empty(self):\n",
    "    \"\"\"Return True if the queue is empty.\"\"\"\n",
    "    return self._size == 0\n",
    "\n",
    "  def first(self):\n",
    "    \"\"\"Return (but do not remove) the element at the front of the queue.\n",
    "\n",
    "    Raise Empty exception if the queue is empty.\n",
    "    \"\"\"\n",
    "    if self.is_empty():\n",
    "      raise ValueError('Queue is empty')\n",
    "    return self._data[self._front]\n",
    "\n",
    "  def dequeue(self):\n",
    "    \"\"\"Remove and return the first element of the queue (i.e., FIFO).\n",
    "\n",
    "    Raise Empty exception if the queue is empty.\n",
    "    \"\"\"\n",
    "    if self.is_empty():\n",
    "      raise ValueError('Queue is empty')\n",
    "    answer = self._data[self._front]\n",
    "    self._data[self._front] = None         # help garbage collection\n",
    "    self._front = (self._front + 1) % len(self._data)\n",
    "    self._size -= 1\n",
    "    return answer\n",
    "\n",
    "  def enqueue(self, e):\n",
    "    \"\"\"Add an element to the back of queue.\"\"\"\n",
    "    if self._size == len(self._data):\n",
    "      self._resize(2 * len(self.data))     # double the array size\n",
    "    avail = (self._front + self._size) % len(self._data)\n",
    "    self._data[avail] = e\n",
    "    self._size += 1\n",
    "\n",
    "  def _resize(self, cap):                  # we assume cap >= len(self)\n",
    "    \"\"\"Resize to a new list of capacity >= len(self).\"\"\"\n",
    "    old = self._data                       # keep track of existing list\n",
    "    self._data = [None] * cap              # allocate list with new capacity\n",
    "    walk = self._front\n",
    "    for k in range(self._size):            # only consider existing elements\n",
    "      self._data[k] = old[walk]            # intentionally shift indices\n",
    "      walk = (1 + walk) % len(old)         # use old size as modulus\n",
    "    self._front = 0                        # front has been realigned\n",
    "  def p(self):\n",
    "    print(self._data,end=' -> ')\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = ArrayQueue()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "ename": "AttributeError",
     "evalue": "'ArrayQueue' object has no attribute 'data'",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-7-82cd2907b5b8>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mz\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m10\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m     \u001b[0ma\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0menqueue\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mz\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      3\u001b[0m     \u001b[0ma\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mp\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      4\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mz\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m10\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m     \u001b[0ma\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mdequeue\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-4-593babf097ef>\u001b[0m in \u001b[0;36menqueue\u001b[1;34m(self, e)\u001b[0m\n\u001b[0;32m     42\u001b[0m     \u001b[1;34m\"\"\"Add an element to the back of queue.\"\"\"\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     43\u001b[0m     \u001b[1;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_size\u001b[0m \u001b[1;33m==\u001b[0m \u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_data\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 44\u001b[1;33m       \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_resize\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m2\u001b[0m \u001b[1;33m*\u001b[0m \u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mdata\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m     \u001b[1;31m# double the array size\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     45\u001b[0m     \u001b[0mavail\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_front\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_size\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m%\u001b[0m \u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_data\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     46\u001b[0m     \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_data\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mavail\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0me\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mAttributeError\u001b[0m: 'ArrayQueue' object has no attribute 'data'"
     ]
    }
   ],
   "source": [
    "for z in range(10):\n",
    "    a.enqueue(z)\n",
    "    a.p()\n",
    "for z in range(10):\n",
    "    a.dequeue()\n",
    "    a.p()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n",
      "False\n",
      "5\n",
      "True\n",
      "9\n",
      "3\n",
      "4\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "class ArrayStack:\n",
    "  \"\"\"LIFO Stack implementation using a Python list as underlying storage.\"\"\"\n",
    "\n",
    "  def __init__(self):\n",
    "    \"\"\"Create an empty stack.\"\"\"\n",
    "    self._data = []                       # nonpublic list instance\n",
    "\n",
    "  def __len__(self):\n",
    "    \"\"\"Return the number of elements in the stack.\"\"\"\n",
    "    return len(self._data)\n",
    "\n",
    "  def is_empty(self):\n",
    "    \"\"\"Return True if the stack is empty.\"\"\"\n",
    "    return len(self._data) == 0\n",
    "\n",
    "  def push(self, e):\n",
    "    \"\"\"Add element e to the top of the stack.\"\"\"\n",
    "    self._data.append(e)                  # new item stored at end of list\n",
    "\n",
    "  def top(self):\n",
    "    \"\"\"Return (but do not remove) the element at the top of the stack.\n",
    "\n",
    "    Raise Empty exception if the stack is empty.\n",
    "    \"\"\"\n",
    "    if self.is_empty():\n",
    "      raise Empty('Stack is empty')\n",
    "    return self._data[-1]                 # the last item in the list\n",
    "\n",
    "  def pop(self):\n",
    "    \"\"\"Remove and return the element from the top of the stack (i.e., LIFO).\n",
    "\n",
    "    Raise Empty exception if the stack is empty.\n",
    "    \"\"\"\n",
    "    if self.is_empty():\n",
    "      raise Empty('Stack is empty')\n",
    "    return self._data.pop()               # remove last item from list\n",
    "\n",
    "if __name__ == '__main__':\n",
    "  S = ArrayStack()                 # contents: [ ]\n",
    "  S.push(5)                        # contents: [5]\n",
    "  S.push(3)                        # contents: [5, 3]\n",
    "  print(len(S))                    # contents: [5, 3];    outputs 2\n",
    "  print(S.pop())                   # contents: [5];       outputs 3\n",
    "  print(S.is_empty())              # contents: [5];       outputs False\n",
    "  print(S.pop())                   # contents: [ ];       outputs 5\n",
    "  print(S.is_empty())              # contents: [ ];       outputs True\n",
    "  S.push(7)                        # contents: [7]\n",
    "  S.push(9)                        # contents: [7, 9]\n",
    "  print(S.top())                   # contents: [7, 9];    outputs 9\n",
    "  S.push(4)                        # contents: [7, 9, 4]\n",
    "  print(len(S))                    # contents: [7, 9, 4]; outputs 3\n",
    "  print(S.pop())                   # contents: [7, 9];    outputs 4\n",
    "  S.push(6)                        # contents: [7, 9, 6]\n",
    "  S.push(8)                        # contents: [7, 9, 6, 8]\n",
    "  print(S.pop())                   # contents: [7, 9, 6]; outputs 8\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "class CircularQueue:\n",
    "  \"\"\"Queue implementation using circularly linked list for storage.\"\"\"\n",
    "\n",
    "  #---------------------------------------------------------------------------------\n",
    "  # nested _Node class\n",
    "  class _Node:\n",
    "    \"\"\"Lightweight, nonpublic class for storing a singly linked node.\"\"\"\n",
    "    __slots__ = '_element', '_next'         # streamline memory usage\n",
    "\n",
    "    def __init__(self, element, next):\n",
    "      self._element = element\n",
    "      self._next = next\n",
    "\n",
    "  # end of _Node class\n",
    "  #---------------------------------------------------------------------------------\n",
    "\n",
    "  def __init__(self):\n",
    "    \"\"\"Create an empty queue.\"\"\"\n",
    "    self._tail = None                     # will represent tail of queue\n",
    "    self._size = 0                        # number of queue elements\n",
    "\n",
    "  def __len__(self):\n",
    "    \"\"\"Return the number of elements in the queue.\"\"\"\n",
    "    return self._size\n",
    "\n",
    "  def is_empty(self):\n",
    "    \"\"\"Return True if the queue is empty.\"\"\"\n",
    "    return self._size == 0\n",
    "\n",
    "  def first(self):\n",
    "    \"\"\"Return (but do not remove) the element at the front of the queue.\n",
    "\n",
    "    Raise Empty exception if the queue is empty.\n",
    "    \"\"\"\n",
    "    if self.is_empty():\n",
    "      raise Empty('Queue is empty')\n",
    "    head = self._tail._next\n",
    "    return head._element\n",
    "\n",
    "  def dequeue(self):\n",
    "    \"\"\"Remove and return the first element of the queue (i.e., FIFO).\n",
    "\n",
    "    Raise Empty exception if the queue is empty.\n",
    "    \"\"\"\n",
    "    if self.is_empty():\n",
    "      raise Empty('Queue is empty')\n",
    "    oldhead = self._tail._next\n",
    "    if self._size == 1:                   # removing only element\n",
    "      self._tail = None                   # queue becomes empty\n",
    "    else:\n",
    "      self._tail._next = oldhead._next    # bypass the old head\n",
    "    self._size -= 1\n",
    "    return oldhead._element\n",
    "\n",
    "  def enqueue(self, e):\n",
    "    \"\"\"Add an element to the back of queue.\"\"\"\n",
    "    newest = self._Node(e, None)          # node will be new tail node\n",
    "    if self.is_empty():\n",
    "      newest._next = newest               # initialize circularly\n",
    "    else:\n",
    "      newest._next = self._tail._next     # new node points to head\n",
    "      self._tail._next = newest           # old tail points to new node\n",
    "    self._tail = newest                   # new node becomes the tail\n",
    "    self._size += 1\n",
    "\n",
    "  def rotate(self):\n",
    "    \"\"\"Rotate front element to the back of the queue.\"\"\"\n",
    "    if self._size > 0:\n",
    "      self._tail = self._tail._next       # old head becomes new tail\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedStack:\n",
    "  \"\"\"LIFO Stack implementation using a singly linked list for storage.\"\"\"\n",
    "\n",
    "  #-------------------------- nested _Node class --------------------------\n",
    "  class _Node: \n",
    "    \"\"\"Lightweight, nonpublic class for storing a singly linked node.\"\"\"\n",
    "    __slots__ = '_element', '_next'         # streamline memory usage\n",
    "\n",
    "    def __init__(self, element, next):      # initialize node's fields\n",
    "      self._element = element               # reference to user's element\n",
    "      self._next = next                     # reference to next node\n",
    "\n",
    "  #------------------------------- stack methods -------------------------------\n",
    "  def __init__(self):\n",
    "    \"\"\"Create an empty stack.\"\"\"\n",
    "    self._head = None                       # reference to the head node\n",
    "    self._size = 0                          # number of stack elements\n",
    "\n",
    "  def __len__(self):\n",
    "    \"\"\"Return the number of elements in the stack.\"\"\"\n",
    "    return self._size\n",
    "\n",
    "  def is_empty(self):\n",
    "    \"\"\"Return True if the stack is empty.\"\"\"\n",
    "    return self._size == 0\n",
    "\n",
    "  def push(self, e):\n",
    "    \"\"\"Add element e to the top of the stack.\"\"\"\n",
    "    self._head = self._Node(e, self._head)  # create and link a new node\n",
    "    self._size += 1\n",
    "\n",
    "  def top(self):\n",
    "    \"\"\"Return (but do not remove) the element at the top of the stack.\n",
    "\n",
    "    Raise Empty exception if the stack is empty.\n",
    "    \"\"\"\n",
    "    if self.is_empty():\n",
    "      raise Empty('Stack is empty')\n",
    "    return self._head._element              # top of stack is at head of list\n",
    "\n",
    "  def pop(self):\n",
    "    \"\"\"Remove and return the element from the top of the stack (i.e., LIFO).\n",
    "\n",
    "    Raise Empty exception if the stack is empty.\n",
    "    \"\"\"\n",
    "    if self.is_empty():\n",
    "      raise Empty('Stack is empty')\n",
    "    answer = self._head._element\n",
    "    self._head = self._head._next           # bypass the former top node\n",
    "    self._size -= 1\n",
    "    return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedQueue:\n",
    "  \"\"\"FIFO queue implementation using a singly linked list for storage.\"\"\"\n",
    "\n",
    "  #-------------------------- nested _Node class --------------------------\n",
    "  class _Node:\n",
    "    \"\"\"Lightweight, nonpublic class for storing a singly linked node.\"\"\"\n",
    "    __slots__ = '_element', '_next'         # streamline memory usage\n",
    "\n",
    "    def __init__(self, element, next):\n",
    "      self._element = element\n",
    "      self._next = next\n",
    "\n",
    "  #------------------------------- queue methods -------------------------------\n",
    "  def __init__(self):\n",
    "    \"\"\"Create an empty queue.\"\"\"\n",
    "    self._head = None\n",
    "    self._tail = None\n",
    "    self._size = 0                          # number of queue elements\n",
    "\n",
    "  def __len__(self):\n",
    "    \"\"\"Return the number of elements in the queue.\"\"\"\n",
    "    return self._size\n",
    "\n",
    "  def is_empty(self):\n",
    "    \"\"\"Return True if the queue is empty.\"\"\"\n",
    "    return self._size == 0\n",
    "\n",
    "  def first(self):\n",
    "    \"\"\"Return (but do not remove) the element at the front of the queue.\n",
    "\n",
    "    Raise Empty exception if the queue is empty.\n",
    "    \"\"\"\n",
    "    if self.is_empty():\n",
    "      raise Empty('Queue is empty')\n",
    "    return self._head._element              # front aligned with head of list\n",
    "\n",
    "  def dequeue(self):\n",
    "    \"\"\"Remove and return the first element of the queue (i.e., FIFO).\n",
    "\n",
    "    Raise Empty exception if the queue is empty.\n",
    "    \"\"\"\n",
    "    if self.is_empty():\n",
    "      raise Empty('Queue is empty')\n",
    "    answer = self._head._element\n",
    "    self._head = self._head._next\n",
    "    self._size -= 1\n",
    "    if self.is_empty():                     # special case as queue is empty\n",
    "      self._tail = None                     # removed head had been the tail\n",
    "    return answer\n",
    "\n",
    "  def enqueue(self, e):\n",
    "    \"\"\"Add an element to the back of queue.\"\"\"\n",
    "    newest = self._Node(e, None)            # node will be new tail node\n",
    "    if self.is_empty():\n",
    "      self._head = newest                   # special case: previously empty\n",
    "    else:\n",
    "      self._tail._next = newest\n",
    "    self._tail = newest                     # update reference to tail node\n",
    "    self._size += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "class _DoublyLinkedBase:\n",
    "  \"\"\"A base class providing a doubly linked list representation.\"\"\"\n",
    "\n",
    "  #-------------------------- nested _Node class --------------------------\n",
    "  # nested _Node class\n",
    "  class _Node:\n",
    "    \"\"\"Lightweight, nonpublic class for storing a doubly linked node.\"\"\"\n",
    "    __slots__ = '_element', '_prev', '_next'            # streamline memory\n",
    "\n",
    "    def __init__(self, element, prev, next):            # initialize node's fields\n",
    "      self._element = element                           # user's element\n",
    "      self._prev = prev                                 # previous node reference\n",
    "      self._next = next                                 # next node reference\n",
    "\n",
    "  #-------------------------- list constructor --------------------------\n",
    "\n",
    "  def __init__(self):\n",
    "    \"\"\"Create an empty list.\"\"\"\n",
    "    self._header = self._Node(None, None, None)\n",
    "    self._trailer = self._Node(None, None, None)\n",
    "    self._header._next = self._trailer                  # trailer is after header\n",
    "    self._trailer._prev = self._header                  # header is before trailer\n",
    "    self._size = 0                                      # number of elements\n",
    "\n",
    "  #-------------------------- public accessors --------------------------\n",
    "\n",
    "  def __len__(self):\n",
    "    \"\"\"Return the number of elements in the list.\"\"\"\n",
    "    return self._size\n",
    "\n",
    "  def is_empty(self):\n",
    "    \"\"\"Return True if list is empty.\"\"\"\n",
    "    return self._size == 0\n",
    "\n",
    "  #-------------------------- nonpublic utilities --------------------------\n",
    "\n",
    "  def _insert_between(self, e, predecessor, successor):\n",
    "    \"\"\"Add element e between two existing nodes and return new node.\"\"\"\n",
    "    newest = self._Node(e, predecessor, successor)      # linked to neighbors\n",
    "    predecessor._next = newest\n",
    "    successor._prev = newest\n",
    "    self._size += 1\n",
    "    return newest\n",
    "\n",
    "  def _delete_node(self, node):\n",
    "    \"\"\"Delete nonsentinel node from the list and return its element.\"\"\"\n",
    "    predecessor = node._prev\n",
    "    successor = node._next\n",
    "    predecessor._next = successor\n",
    "    successor._prev = predecessor\n",
    "    self._size -= 1\n",
    "    element = node._element                             # record deleted element\n",
    "    node._prev = node._next = node._element = None      # deprecate node\n",
    "    return element                                      # return deleted element\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedDeque(_DoublyLinkedBase):         # note the use of inheritance\n",
    "  \"\"\"Double-ended queue implementation based on a doubly linked list.\"\"\"\n",
    "\n",
    "  def first(self):\n",
    "    \"\"\"Return (but do not remove) the element at the front of the deque.\n",
    "\n",
    "    Raise Empty exception if the deque is empty.\n",
    "    \"\"\"\n",
    "    if self.is_empty():\n",
    "      raise Empty(\"Deque is empty\")\n",
    "    return self._header._next._element        # real item just after header\n",
    "\n",
    "  def last(self):\n",
    "    \"\"\"Return (but do not remove) the element at the back of the deque.\n",
    "\n",
    "    Raise Empty exception if the deque is empty.\n",
    "    \"\"\"\n",
    "    if self.is_empty():\n",
    "      raise Empty(\"Deque is empty\")\n",
    "    return self._trailer._prev._element       # real item just before trailer\n",
    "\n",
    "  def insert_first(self, e):\n",
    "    \"\"\"Add an element to the front of the deque.\"\"\"\n",
    "    self._insert_between(e, self._header, self._header._next)   # after header\n",
    "\n",
    "  def insert_last(self, e):\n",
    "    \"\"\"Add an element to the back of the deque.\"\"\"\n",
    "    self._insert_between(e, self._trailer._prev, self._trailer) # before trailer\n",
    "\n",
    "  def delete_first(self):\n",
    "    \"\"\"Remove and return the element from the front of the deque.\n",
    "\n",
    "    Raise Empty exception if the deque is empty.\n",
    "    \"\"\"\n",
    "    if self.is_empty():\n",
    "      raise Empty(\"Deque is empty\")\n",
    "    return self._delete_node(self._header._next)   # use inherited method\n",
    "\n",
    "  def delete_last(self):\n",
    "    \"\"\"Remove and return the element from the back of the deque.\n",
    "\n",
    "    Raise Empty exception if the deque is empty.\n",
    "    \"\"\"\n",
    "    if self.is_empty():\n",
    "      raise Empty(\"Deque is empty\")\n",
    "    return self._delete_node(self._trailer._prev)  # use inherited method\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CircularQueue:\n",
    "  \"\"\"Queue implementation using circularly linked list for storage.\"\"\"\n",
    "\n",
    "  #---------------------------------------------------------------------------------\n",
    "  # nested _Node class\n",
    "  class _Node:\n",
    "    \"\"\"Lightweight, nonpublic class for storing a singly linked node.\"\"\"\n",
    "    __slots__ = '_element', '_next'         # streamline memory usage\n",
    "\n",
    "    def __init__(self, element, next):\n",
    "      self._element = element\n",
    "      self._next = next\n",
    "\n",
    "  # end of _Node class\n",
    "  #---------------------------------------------------------------------------------\n",
    "\n",
    "  def __init__(self):\n",
    "    \"\"\"Create an empty queue.\"\"\"\n",
    "    self._tail = None                     # will represent tail of queue\n",
    "    self._size = 0                        # number of queue elements\n",
    "\n",
    "  def __len__(self):\n",
    "    \"\"\"Return the number of elements in the queue.\"\"\"\n",
    "    return self._size\n",
    "\n",
    "  def is_empty(self):\n",
    "    \"\"\"Return True if the queue is empty.\"\"\"\n",
    "    return self._size == 0\n",
    "\n",
    "  def first(self):\n",
    "    \"\"\"Return (but do not remove) the element at the front of the queue.\n",
    "\n",
    "    Raise Empty exception if the queue is empty.\n",
    "    \"\"\"\n",
    "    if self.is_empty():\n",
    "      raise Empty('Queue is empty')\n",
    "    return self._tail._next._element\n",
    "\n",
    "  def dequeue(self):\n",
    "    \"\"\"Remove and return the first element of the queue (i.e., FIFO).\n",
    "\n",
    "    Raise Empty exception if the queue is empty.\n",
    "    \"\"\"\n",
    "    if self.is_empty():\n",
    "      raise Empty('Queue is empty')\n",
    "    oldhead = self._tail._next\n",
    "    if self._size == 1:                   # removing only element\n",
    "      self._tail = None                   # queue becomes empty\n",
    "    else:\n",
    "      self._tail._next = oldhead._next    # bypass the old head\n",
    "    self._size -= 1\n",
    "    return oldhead._element\n",
    "\n",
    "  def enqueue(self, e):\n",
    "    \"\"\"Add an element to the back of queue.\"\"\"\n",
    "    newest = self._Node(e, None)          # node will be new tail node\n",
    "    if self.is_empty():\n",
    "      newest._next = newest               # initialize circularly\n",
    "    else:\n",
    "      newest._next = self._tail._next     # new node points to head\n",
    "      self._tail._next = newest           # old tail points to new node\n",
    "    self._tail = newest                   # new node becomes the tail\n",
    "    self._size += 1\n",
    "\n",
    "  def rotate(self):\n",
    "    \"\"\"Rotate front element to the back of the queue.\"\"\"\n",
    "    if self._size > 0:\n",
    "      self._tail = self._tail._next       # old head becomes new tail\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}