{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "## STACK IMPLEMENTATION (simple list implementation)\n",
    "## Stack.py\n",
    "class Stack:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._data = []  # first item is bottom; last item is top\n",
    "        \n",
    "    def is_empty(self):\n",
    "    # returns True for an empty stack False otherwise\n",
    "        return len(self._data) == 0\n",
    "    \n",
    "    def size(self):\n",
    "    # returns size of the stack; i.e. number of elements in stack\n",
    "        return len(self._data)\n",
    "        \n",
    "    def push(self,e):\n",
    "    # add item e to top of stack\n",
    "    # no error check for FULL stack because we are assuming\n",
    "    # \"unlimited\" Python list\n",
    "        self._data.append(e)\n",
    "        \n",
    "    def pop(self):\n",
    "    # remove AND return the top item on stack\n",
    "        if not self.empty():\n",
    "            x = self._data[-1]\n",
    "            self._data = self._data[0:len(self._data)-1]\n",
    "            return x\n",
    "        else:\n",
    "            return None\n",
    "        \n",
    "    def top(self):\n",
    "    # return the top item on stack\n",
    "        if not self.empty():\n",
    "            return self._data[-1]\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "    def __str__(self):\n",
    "        #result = \"BOTTOM \"\n",
    "        #for x in self._data:\n",
    "        #    result = result + str(x) + \" \"\n",
    "        #result = result + \"TOP\"\n",
    "        #return result\n",
    "        result = \"\"\n",
    "        for i in range(-1,-len(self._data)-1,-1):\n",
    "            result = result + str(self._data[i]) + \"\\n\"\n",
    "        result = result + \"-BOTTOM-\\n\"\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-BOTTOM-\n",
      "\n",
      "10\n",
      "-BOTTOM-\n",
      "\n",
      "20\n",
      "10\n",
      "-BOTTOM-\n",
      "\n",
      "30\n",
      "20\n",
      "10\n",
      "-BOTTOM-\n",
      "\n",
      "Alice\n",
      "John\n",
      "-BOTTOM-\n",
      "\n",
      "3\n",
      "2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'30\\n20\\n10\\n-BOTTOM-\\n'"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s1 = Stack()\n",
    "print(s1)\n",
    "s1.push(10)\n",
    "print(s1)\n",
    "s1.push(20)\n",
    "print(s1)\n",
    "s1.push(30)\n",
    "print(s1)\n",
    "#x = s1.pop()\n",
    "#print(x,s1)\n",
    "s2 = Stack()\n",
    "s2.push(\"John\")\n",
    "s2.push(\"Alice\")\n",
    "print(s2)\n",
    "print(s1.size())\n",
    "print(s2.size())\n",
    "str(s1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'[1, 2, 3, 4, 5, 6]'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "xs = [1,2,3,4,5,6]\n",
    "xs[0:len(xs)-1]\n",
    "str(xs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"{'a': 10, 'b': 20}\""
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "str({'a':10,'b':20})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(30)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "BOTTOM 10 20 30 TOP\n",
    "\n",
    "30\n",
    "20\n",
    "10\n",
    "-BOTTOM-"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 2, 1]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [1,2,3]\n",
    "x.reverse()\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-1\n",
      "-2\n",
      "-3\n",
      "-4\n"
     ]
    }
   ],
   "source": [
    "xs = [1,2,3,4]\n",
    "for x in range(-1,-len(xs)-1,-1):\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "xs[-4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Circular List Implementation of a Queue\n",
    "class Queue:\n",
    "    \n",
    "    CAPACITY = 10\n",
    "    \n",
    "    def __init__(self):\n",
    "        self._data = [None]*Queue.CAPACITY\n",
    "        self._front = 0\n",
    "        self._size = 0\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self._size == 0\n",
    "    \n",
    "    def first(self):\n",
    "        if self.is_empty():\n",
    "            return None\n",
    "        else:\n",
    "            return self._data[self._front]\n",
    "    \n",
    "    def size(self):\n",
    "        return self._size\n",
    "    \n",
    "    def dequeue(self):\n",
    "    # returns AND removes item from front of queue\n",
    "        if self.is_empty():\n",
    "            return None\n",
    "        else:\n",
    "            x = self._data[self._front]\n",
    "            self._data[self._front] = None\n",
    "            self._front = (self._front + 1)%len(self._data)\n",
    "            self._size = self._size - 1\n",
    "            return x\n",
    "    \n",
    "    def enqueue(self,e):\n",
    "        # adds e to end of queue\n",
    "        if self._size == len(self._data):\n",
    "            self.resizeUp(2*len(self._data))\n",
    "        # back = front + size %\n",
    "        back = (self._front + self._size)%len(self._data)\n",
    "        self._data[back] = e\n",
    "        self._size = self._size + 1\n",
    "        \n",
    "    def resizeUp(self,cap):\n",
    "        #Step 1 Create a new bigger list of None\n",
    "        temp = [None]*cap\n",
    "        #Step 2: Transfer all items from self._data into temp\n",
    "        i = self._front\n",
    "        j = 0\n",
    "        for x in range(self._size):\n",
    "            temp[j] = self._data[i]\n",
    "            i = (i+1)%len(self._data)\n",
    "            j = (j+1)%len(temp)\n",
    "        self._data = temp\n",
    "        self._front = 0\n",
    "    \n",
    "    def __str__(self):\n",
    "        return str(self._data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[None, None, None, None, None, None, None, None, None, None]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[None]*10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[10, 20, 30, None, None, None, None, None, None, None]\n"
     ]
    }
   ],
   "source": [
    "q1 = Queue()\n",
    "q1.enqueue(10)\n",
    "q1.enqueue(20)\n",
    "q1.enqueue(30)\n",
    "print(q1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[None, 20, 30, None, None, None, None, None, None, None]\n"
     ]
    }
   ],
   "source": [
    "q1.dequeue()\n",
    "print(q1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q1._front"
   ]
  },
  {
   "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.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}