{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack:\n",
    "\n",
    "    # Python list implementation of stacks\n",
    "\n",
    "    def __init__(self):\n",
    "        # construct an empty stack\n",
    "        self._data = []\n",
    "\n",
    "    def __str__(self):\n",
    "        # string representation of stack\n",
    "        return str(self._data)\n",
    "        # Left as homework; Use accumulator pattern\n",
    "        # self._data = [10,20,30,40,50] should be converted to the string \"TOP: 10 20 30 40 50 :BOTTOM\"\n",
    "        #return \"HELLO\"\n",
    "        \n",
    "    def __len__(self):\n",
    "        # returns number of items in stack\n",
    "        return len(self._data)\n",
    "\n",
    "    def is_empty(self):\n",
    "        # returns True if stack is empty and False otherwise\n",
    "        return len(self._data) == 0\n",
    "\n",
    "    def top(self):\n",
    "        # returns top item of stack it stack is not empty; otherwise returns None\n",
    "        if len(self._data) != 0:\n",
    "            return self._data[0]\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "    def pop(self):\n",
    "        # similar to top, except this also deletes top item from stack.\n",
    "        if len(self._data) != 0:\n",
    "            return self._data.pop(0)\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "    def push(self,e):\n",
    "        # puts new item e on top of stack\n",
    "        self._data.insert(0,e)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "reverse of string: fedcba\n",
      "reverse of string: madam\n",
      "reverse of string: ?uoy era woh olleh\n"
     ]
    }
   ],
   "source": [
    "def reverse():\n",
    "    # implements the Reverse program\n",
    "    while True:\n",
    "        s = input(\"input a string (q to quit): \")\n",
    "        if s == \"q\":\n",
    "            break\n",
    "        stack = Stack()\n",
    "        for c in s:\n",
    "            stack.push(c)\n",
    "        result = \"reverse of string: \"\n",
    "        for i in range(len(s)):\n",
    "            c = stack.pop()\n",
    "            result = result + c\n",
    "        print(result)\n",
    "\n",
    "reverse()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[8, 7, 5]\n"
     ]
    }
   ],
   "source": [
    "$ python3 Reverse.py\n",
    "input a string (q to quit): abcdef\n",
    "reverse of string: fedcba\n",
    "input a string (q to quit): madam\n",
    "reverse of string: madam\n",
    "input a string (q to quit): q\n",
    "\n",
    "\n",
    "s1 = Stack()\n",
    "s1.push(5)\n",
    "s1.push(7)\n",
    "s1.push(2)\n",
    "e = s1.pop()\n",
    "s1.push(8)\n",
    "print(s1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[10, 20, 30, 40]\n",
      "20\n",
      "90\n"
     ]
    }
   ],
   "source": [
    "x = [20, 30, 40]\n",
    "x.insert(0,10)\n",
    "x.insert(0,90)\n",
    "item = x.pop(0)\n",
    "print(x)\n",
    "print(x[1])\n",
    "print(item)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "nums = []\n",
    "for i in range(10):\n",
    "    nums.insert(0,i)\n",
    "print(nums)\n",
    "print(len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (<ipython-input-15-29214696102e>, line 1)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-15-29214696102e>\"\u001b[0;36m, line \u001b[0;32m1\u001b[0m\n\u001b[0;31m    if ????:\u001b[0m\n\u001b[0m       ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "if ????:\n",
    "    return True\n",
    "else:\n",
    "    return False\n",
    "same as\n",
    "????"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'[10, 20, 30]'"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[None,None,30,40,50,60,None,None,None,None]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"TOP: 10 20 30 40 50 :BOTTOM\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "GRACEFUL EXIT\n",
    "NON-GRACEFUL EXIT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    # Circular List Implementation\n",
    "\n",
    "    CAPACITY = 10\n",
    "\n",
    "    def __init__(self):\n",
    "        # instance variables: _data, _size, _front\n",
    "        self._data = [None]*CAPACITY\n",
    "        self._front = 0\n",
    "        self._size = 0\n",
    "        \n",
    "    def __str__(self):\n",
    "        # string representation of queue\n",
    "        return str(self._data)+\" \"+str(self._front) + \" \"+str(self._size)\n",
    "        # modify this to show \"FRONT: 20 30 50 :BACK\"\n",
    "    \n",
    "    def __len__(self):\n",
    "        # return length of queue\n",
    "        return self._size\n",
    "\n",
    "    def is_empty(self):\n",
    "        # return True if queue is empty otherwise return False\n",
    "        return self._size == 0\n",
    "    \n",
    "    def first(self):\n",
    "        # return first item of queue if it is not empty; otherwise return None\n",
    "        if self._size != 0:\n",
    "            return self._data[self._front]\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "    def dequeue(self):\n",
    "        # remove and return first item in queue; return None if queue is empty\n",
    "        if self._size == 0:\n",
    "            return None\n",
    "        item = self._data[self._front]\n",
    "        self._data[self._front] = None\n",
    "        self._size = self._size = 1\n",
    "        self._front = (self._front + 1)%len(self._data)\n",
    "        return item\n",
    "\n",
    "    def enqueue(self,e):\n",
    "        # add item e to the end of queue. If list is full, resize the list by\n",
    "        # creating a new list of twice the size and moving items from old list \n",
    "        # to new list; Do not forget to adjust _size and _front\n",
    "        if self._size == len(self._data):\n",
    "            self._resizeUp(2*len(self._data))\n",
    "        pos = (self._front + self._size)%len(self._data) # please verify that pos is the position of the None after the last item in queue\n",
    "        self._data[pos] = e\n",
    "        self._size = self._size + 1\n",
    "        \n",
    "    def _resizeUp(self,cap):\n",
    "        # method to resize\n",
    "        ???\n",
    "        ???"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 1, 2, 1, 2, 1, 2, 1, 2]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[1,2]*5"
   ]
  },
  {
   "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}