data-structure/queue-python3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Queue\n",
    " - python 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## queue library 사용"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from queue import Queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('queue', deque([1]))\n",
      "('queue', deque([1, 2]))\n",
      "('queue', deque([1, 2, 3]))\n",
      "('queue', deque([2, 3]))\n"
     ]
    }
   ],
   "source": [
    "queue = Queue()\n",
    "queue.put(1)\n",
    "print(\"queue\", queue.queue)\n",
    "queue.put(2)\n",
    "print(\"queue\", queue.queue)\n",
    "queue.put(3)\n",
    "print(\"queue\", queue.queue)\n",
    "queue.get()\n",
    "print(\"queue\", queue.queue)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LIFO Queue\n",
    " - Queue지만, Stack과 비슷하게 후입선출 구조로 나갑니다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from queue import LifoQueue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('queue', [1])\n",
      "('queue', [1, 2])\n",
      "('queue', [1, 2, 3])\n",
      "('queue', [1, 2])\n"
     ]
    }
   ],
   "source": [
    "queue = LifoQueue()\n",
    "queue.put(1)\n",
    "print(\"queue\", queue.queue)\n",
    "queue.put(2)\n",
    "print(\"queue\", queue.queue)\n",
    "queue.put(3)\n",
    "print(\"queue\", queue.queue)\n",
    "queue.get()\n",
    "print(\"queue\", queue.queue) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Priority Queue\n",
    " - 우선 순위 큐로 데이터는 Tuple로 저장됩니다. \n",
    " - 우선 순위는 값에 따라 오름차순으로 정렬되며, 낮은 값 부터 빠져나갑니다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from queue import PriorityQueue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('queue', [(10, 'mango')])\n",
      "('queue', [(4, 'banana'), (10, 'mango')])\n",
      "('queue', [(2, 'watermelon'), (10, 'mango'), (4, 'banana')])\n",
      "('dequque', (2, 'watermelon'))\n",
      "('queue', [(4, 'banana'), (10, 'mango')])\n",
      "('queue', [(3, 'strawberry'), (10, 'mango'), (4, 'banana')])\n",
      "('dequque', (3, 'strawberry'))\n",
      "('queue', [(4, 'banana'), (10, 'mango')])\n"
     ]
    }
   ],
   "source": [
    "queue = PriorityQueue()\n",
    "queue.put((10, \"mango\"))\n",
    "print(\"queue\", queue.queue)\n",
    "queue.put((4, \"banana\"))\n",
    "print(\"queue\", queue.queue)\n",
    "queue.put((2, \"watermelon\"))\n",
    "print(\"queue\", queue.queue)\n",
    "print(\"dequque\", queue.get())\n",
    "print(\"queue\", queue.queue) \n",
    "queue.put((3, \"strawberry\"))\n",
    "print(\"queue\", queue.queue)\n",
    "print(\"dequque\", queue.get())\n",
    "print(\"queue\", queue.queue) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Queue class 구현\n",
    "python의 list 자체에 queue의 push(append)와 pop을 이용해 구현합니다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue(list):\n",
    "    enqueue = list.append # push, enquque\n",
    "    \n",
    "    def dequeue(self):\n",
    "        return self.pop(0)\n",
    "    \n",
    "    def is_empty(self):\n",
    "        if not self:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('queue', [1])\n",
      "('queue', [1, 2])\n",
      "('queue', [1, 2, 3])\n",
      "('queue', [2, 3])\n"
     ]
    }
   ],
   "source": [
    "queue = Queue()\n",
    "queue.enqueue(1)\n",
    "print(\"queue\", queue)\n",
    "queue.enqueue(2)\n",
    "print(\"queue\", queue)\n",
    "queue.enqueue(3)\n",
    "print(\"queue\", queue)\n",
    "queue.dequeue()\n",
    "print(\"queue\", queue)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Queue class를 list 없이 구현"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "    \n",
    "    def is_empty(self):\n",
    "        if not self.head:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    def enqueue(self, data):\n",
    "        node = Node(data)\n",
    "        \n",
    "        if self.is_empty():\n",
    "            self.head = node\n",
    "            self.tail = node\n",
    "            return\n",
    "        \n",
    "        self.tail.next = node\n",
    "        self.tail = node\n",
    "        \n",
    "    def dequeue(self):\n",
    "        if self.is_empty():\n",
    "            return None\n",
    "        \n",
    "        result = self.head.data\n",
    "        self.head = self.head.next\n",
    "        return result\n",
    "    \n",
    "    def element(self):\n",
    "        top = self.head\n",
    "        head = self.head\n",
    "        result = [head.data]\n",
    "        while head.next != None:\n",
    "            head = head.next\n",
    "            result.append(head.data)\n",
    "        self.head = top\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('queue', [1])\n",
      "('queue', [1, 2])\n",
      "('queue', [1, 2, 3])\n",
      "('queue', [2, 3])\n"
     ]
    }
   ],
   "source": [
    "queue = Queue()\n",
    "queue.enqueue(1)\n",
    "print(\"queue\", queue.element())\n",
    "queue.enqueue(2)\n",
    "print(\"queue\", queue.element())\n",
    "queue.enqueue(3)\n",
    "print(\"queue\", queue.element())\n",
    "queue.dequeue()\n",
    "print(\"queue\", queue.element())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}