Stack/Stack.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Author: OMKAR PATHAK"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What is Stack?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* A stack is a simple data structure used for storing data (similar to Linked Lists). In a stack, the order in which the data arrives is important.\n",
    "* A stack is an ordered list in which insertion and deletion are done at one end, called top. The last element inserted is the first one to be deleted. Hence, it is called the Last in First out (LIFO) or First in Last out(FILO) list.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Applications of Stack:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Balancing of symbols\n",
    "* lnfix-to-postfix conversion\n",
    "* Evaluation of postfix expression\n",
    "* Implementing function calls (including recursion)\n",
    "* Page-visited history in a Web browser [Back Buttons]\n",
    "* Undo sequence in a text editor\n",
    "* Matching Tags in HTML and XML\n",
    "* Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementing Stack using Python Lists:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9\n",
      "0 1 2 3 4 5 6 7 8\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Stack(object):\n",
    "    def __init__(self, limit = 10):\n",
    "        self.stack = []\n",
    "        self.limit = limit\n",
    "    \n",
    "    # for printing the stack contents\n",
    "    def __str__(self):\n",
    "        return ' '.join([str(i) for i in self.stack])\n",
    "    \n",
    "    # for pushing an element on to the stack\n",
    "    def push(self, data):\n",
    "        if len(self.stack) >= self.limit:\n",
    "            print('Stack Overflow')\n",
    "        else:\n",
    "            self.stack.append(data)\n",
    "            \n",
    "    # for popping the uppermost element\n",
    "    def pop(self):\n",
    "        if len(self.stack) <= 0:\n",
    "            print('Stack Underflow')\n",
    "        else:\n",
    "            self.stack.pop()\n",
    "            \n",
    "    # for peeking the top-most element of the stack\n",
    "    def peek(self):\n",
    "        if len(self.stack) <= 0:\n",
    "            print('Stack Underflow')\n",
    "        else:\n",
    "            return self.stack[-1]\n",
    "        \n",
    "    # to check if stack is empty\n",
    "    def isEmpty(self):\n",
    "        return len(self.stack) == 0\n",
    "    \n",
    "    # for checking the size of stack\n",
    "    def size(self):\n",
    "        return len(self.stack)\n",
    "\n",
    "myStack = Stack()\n",
    "for i in range(10):\n",
    "    myStack.push(i)\n",
    "print(myStack)\n",
    "myStack.pop()            # popping the top element\n",
    "print(myStack)\n",
    "myStack.peek()          # printing the top element\n",
    "myStack.isEmpty()\n",
    "myStack.size()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Time Complexities:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Push: O(1)\n",
    "* Pop: O(1)\n",
    "* Peek: O(1)\n",
    "* isEmpty: O(1)\n",
    "* Size: O(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Limitations:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Stack size is to be defined first and cannot be changed.\n",
    "* Trying to push a new element into a full stack causes an implementation-specific exception.\n"
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}