Queue - Stack - BFS - DFS.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Queue\n",
    "### First In First Out (FIFO)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__ (self, maximum_size):\n",
    "        self.maximum_size = maximum_size\n",
    "        self.content = []\n",
    "        self.size = 0\n",
    "    \n",
    "    def isFull(self):\n",
    "        if self.size == self.maximum_size:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "    def isEmpty(self):\n",
    "        if self.size == 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    def add(self, element):\n",
    "        if self.isFull():\n",
    "            print(\"Error!\\nQueue is Full\")\n",
    "        else:\n",
    "            self.content.append(element)\n",
    "            self.size += 1\n",
    "            \n",
    "    def remove(self):\n",
    "        if self.isEmpty():\n",
    "            print(\"Error!\\nQueue is Empty\")\n",
    "        else:\n",
    "            self.content.remove(self.content[0])\n",
    "            self.size -= 1\n",
    "        \n",
    "    def clear(self):\n",
    "        self.content.clear()\n",
    "        self.size = 0\n",
    "        \n",
    "    def getHead(self):\n",
    "        return self.content[0]\n",
    "    \n",
    "    def getTail(self):\n",
    "        return self.content[-1]\n",
    "    \n",
    "    def getFullQueue(self):\n",
    "        return self.content"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "q = Queue(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "q.add(1)\n",
    "q.add(2)\n",
    "q.add(3)\n",
    "q.add(4)\n",
    "q.add(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Error!\n",
      "Queue is Full\n"
     ]
    }
   ],
   "source": [
    "q.add(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.getFullQueue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 5]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.remove()\n",
    "q.getFullQueue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.isFull()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[]\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "q.clear()\n",
    "print(q.getFullQueue())\n",
    "print(q.isEmpty())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Stack\n",
    "### Last In First Out (LIFO)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack:\n",
    "    def __init__ (self, maximum_size):\n",
    "        self.maximum_size = maximum_size\n",
    "        self.content = []\n",
    "        self.size = 0\n",
    "    \n",
    "    def isFull(self):\n",
    "        if self.size == self.maximum_size:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "    def isEmpty(self):\n",
    "        if self.size == 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    def push(self, element):\n",
    "        if self.isFull():\n",
    "            print(\"Error!\\nStack is Full\")\n",
    "        else:\n",
    "            self.content.append(element)\n",
    "            self.size += 1\n",
    "            \n",
    "    def pop(self):\n",
    "        if self.isEmpty():\n",
    "            print(\"Error!\\nStack is Empty\")\n",
    "        else:\n",
    "            self.content.pop()\n",
    "            self.size -= 1\n",
    "        \n",
    "    def clear(self):\n",
    "        self.content.clear()\n",
    "        self.size = 0\n",
    "        \n",
    "    def getTop(self):\n",
    "        return self.content[-1]\n",
    "    \n",
    "    def getFullStack(self):\n",
    "        return self.content"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = Stack(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "s.push(1)\n",
    "s.push(2)\n",
    "s.push(3)\n",
    "s.push(4)\n",
    "s.push(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Error!\n",
      "Stack is Full\n"
     ]
    }
   ],
   "source": [
    "s.push(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.getFullStack()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.pop()\n",
    "s.getFullStack()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.isFull()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[]\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "s.clear()\n",
    "print(s.getFullStack())\n",
    "print(s.isEmpty())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# BFS & DFS\n",
    "## BFS : Breadth First Search Algorithm\n",
    "## DFS : Depth First Search Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree = {\n",
    "    'A' : [ 'B' , 'C' ],\n",
    "    'B' : [ 'A' , 'D', 'E' ],\n",
    "    'C' : [ 'A' , 'F', 'G' ],\n",
    "    'D' : [ 'B' ],\n",
    "    'E' : [ 'B' ],\n",
    "    'F' : [ 'C' ],\n",
    "    'G' : [ 'C', 'H' ],\n",
    "    'H' : [ 'C' ],\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "class graph:\n",
    "    def __init__ (self, tree):\n",
    "        self.tree = tree\n",
    "        \n",
    "           \n",
    "    def BFS(self, root):\n",
    "        \n",
    "        #Need to 3 data structures:\n",
    "        # 1- Array for the visited vetrex to not visit it again\n",
    "        # 2- Queue for the BFS Process\n",
    "        # 3- Queue for the Final Result\n",
    "        self.visited = []\n",
    "        self.queue = Queue(len(tree))\n",
    "        self.final = Queue(len(tree))\n",
    "        \n",
    "        if root not in self.tree:\n",
    "            print(\"Error!\\nRoot not found\")\n",
    "        \n",
    "        else:\n",
    "            #In each step starting from the root when we visit a vertex:\n",
    "            # 1- we add it to the visited array to not visit it again and be in an infinite loop\n",
    "            # 2- The vertex is added to the Process queue\n",
    "            # 3- we add the children of the vertex one by one in the same level to the visited array and process queue\n",
    "            # 4- After Ending visiting the children of a vertex it's removed from the Process Stack and added to the Final queue\n",
    "            # 5- The process is repeated with the head vertex in Process queue till it becomes empty\n",
    "            \n",
    "            self.visited.append(root)\n",
    "            self.queue.add(root)\n",
    "            \n",
    "            for i in range(len(tree[root])):\n",
    "                self.visited.append(tree[root][i])\n",
    "                self.queue.add(tree[root][i])\n",
    "            \n",
    "            self.final.add(self.queue.getHead())\n",
    "            self.queue.remove()\n",
    "            \n",
    "            while not self.queue.isEmpty():\n",
    "                top = self.queue.getHead()\n",
    "                \n",
    "                for i in range(len(tree[top])):\n",
    "                    if tree[top][i] not in self.visited:\n",
    "                        self.visited.append(tree[top][i])\n",
    "                        self.queue.add(tree[top][i])\n",
    "                \n",
    "                self.final.add(top)\n",
    "                self.queue.remove()\n",
    "                \n",
    "            \n",
    "            return self.final.getFullQueue()\n",
    "        \n",
    "        \n",
    "    def DFS(self, root):\n",
    "        \n",
    "        #Need to 3 data structures:\n",
    "        # 1- Array for the visited vetrex to not visit it again\n",
    "        # 2- Stack for the DFS Process\n",
    "        # 3- Queue for the Final Result\n",
    "        \n",
    "        self.visited = []\n",
    "        self.stack = Stack(len(tree))\n",
    "        self.final = Queue(len(tree))\n",
    "        \n",
    "        if root not in self.tree:\n",
    "            print(\"Error!\\nRoot not found\")\n",
    "        \n",
    "        else:\n",
    "            #In each step starting from the root when we visit a vertex:\n",
    "            # 1- we add it to the visited array to not visit it again and be in an infinite loop\n",
    "            # 2- The vertex is pushed to the Process stack\n",
    "            # 3- we add all the children of the vertex to the deepest child and to visited array and process stack\n",
    "            # 4- After Ending visiting the children of a vertex it's removed from the Process Stack and added to the Final queue\n",
    "            # 5- The process is repeated with the Top vertex in Process stack till it becomes empty\n",
    "            \n",
    "            self.visited.append(root)\n",
    "            self.stack.push(root)\n",
    "            \n",
    "            while not self.stack.isEmpty():\n",
    "                finished = self.stack.getTop()\n",
    "                self.stack.pop()\n",
    "                self.final.add(finished)\n",
    "                \n",
    "                for i in range(len(tree[finished])):\n",
    "                    if tree[finished][i] not in self.visited:\n",
    "                        self.visited.append(tree[finished][i])\n",
    "                        self.stack.push(tree[finished][i])\n",
    "                \n",
    "            \n",
    "            return self.final.getFullQueue()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_class = graph(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree_class.BFS('A')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['A', 'C', 'G', 'H', 'F', 'B', 'E', 'D']"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree_class.DFS('A')"
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}