conversion_of_data_structures.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Conversion between different data strucutres\n",
    "\n",
    "## Conversion between linear data structures\n",
    "\n",
    "### Implement a queue with two stacks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyQueue:\n",
    "    \"\"\"\n",
    "    Implement a queue with two stacks.\n",
    "    The function comments come from https://leetcode.cn/problems/implement-queue-using-stacks-lcci/\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.pushStack = []\n",
    "        self.popStack = []\n",
    "\n",
    "\n",
    "    def __repr__(self):\n",
    "        \"\"\"\n",
    "        Returns the normalized string representation.\n",
    "        \"\"\"\n",
    "        while self.popStack:\n",
    "            element = self.popStack.pop()\n",
    "            self.pushStack.append(element)\n",
    "        return \"MyQueue({})\".format(self.pushStack)\n",
    "\n",
    "\n",
    "    def __len__(self):\n",
    "        \"\"\"\n",
    "        Returns the length of queue\n",
    "        \"\"\"\n",
    "        return len(self.popStack) + len(self.pushStack)\n",
    "\n",
    "\n",
    "    def push(self, x: int) -> None:\n",
    "        \"\"\"\n",
    "        Push element x to the back of queue.\n",
    "        \"\"\"\n",
    "        while self.popStack:\n",
    "            element = self.popStack.pop()\n",
    "            self.pushStack.append(element)\n",
    "        self.pushStack.append(x)\n",
    "\n",
    "\n",
    "    def pop(self) -> int:\n",
    "        \"\"\"\n",
    "        Removes the element from in front of queue and returns that element.\n",
    "        \"\"\"\n",
    "        while self.pushStack:\n",
    "            element = self.pushStack.pop()\n",
    "            self.popStack.append(element)\n",
    "        return self.popStack.pop()\n",
    "\n",
    "\n",
    "    def peek(self) -> int:\n",
    "        \"\"\"\n",
    "        Get the front element.\n",
    "        \"\"\"\n",
    "        while self.pushStack:\n",
    "            element = self.pushStack.pop()\n",
    "            self.popStack.append(element)\n",
    "        return self.popStack[-1]\n",
    "\n",
    "\n",
    "    def empty(self) -> bool:\n",
    "        \"\"\"\n",
    "        Returns whether the queue is empty.\n",
    "        \"\"\"\n",
    "        return len(self.pushStack) == 0 and len(self.popStack) == 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Case"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "MyQueue([])"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "queueInstance = MyQueue()\n",
    "queueInstance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "queueInstance.empty()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "MyQueue([2, 3, 5])"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "queueInstance.push(2)\n",
    "queueInstance.push(3)\n",
    "queueInstance.push(5)\n",
    "queueInstance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "queueInstance.peek()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "MyQueue([3, 5])"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "queueInstance.pop()\n",
    "queueInstance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "queueInstance.empty()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implement a stack with a queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyStack:\n",
    "    \"\"\"\n",
    "    Implement a stack with a queue.\n",
    "    The function comments come from https://leetcode.cn/problems/implement-stack-using-queues/solution/yong-dui-lie-shi-xian-zhan-by-leetcode-solution/\n",
    "    \"\"\"\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Returns the normalized string representation.\n",
    "        \"\"\"\n",
    "        self.queue = []\n",
    "\n",
    "\n",
    "    def __repr__(self):\n",
    "        \"\"\"\n",
    "        Returns the normalized string representation.\n",
    "        \"\"\"\n",
    "        return \"MyStack({})\".format(self.queue[::-1])\n",
    "\n",
    "\n",
    "    def __len__(self):\n",
    "        \"\"\"\n",
    "        Returns the length of stack\n",
    "        \"\"\"\n",
    "        return len(self.queue)\n",
    "\n",
    "\n",
    "    def push(self, x: int) -> None:\n",
    "        \"\"\"\n",
    "        Push element x onto stack.\n",
    "        \"\"\"\n",
    "        n = len(self.queue)\n",
    "        self.queue.append(x)\n",
    "        for _ in range(n):\n",
    "            element = self.queue.pop(0)\n",
    "            self.queue.append(element)\n",
    "\n",
    "\n",
    "    def pop(self) -> int:\n",
    "        \"\"\"\n",
    "        Removes the element on top of the stack and returns that element.\n",
    "        \"\"\"\n",
    "        return self.queue.pop(0)\n",
    "\n",
    "\n",
    "    def top(self) -> int:\n",
    "        \"\"\"\n",
    "        Get the top element.\n",
    "        \"\"\"\n",
    "        return self.queue[0]\n",
    "\n",
    "\n",
    "    def empty(self) -> bool:\n",
    "        \"\"\"\n",
    "        Returns whether the stack is empty.\n",
    "        \"\"\"\n",
    "        return not self.queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Case"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "MyStack([])"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stackInstance = MyStack()\n",
    "stackInstance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stackInstance.empty()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "MyStack([1, 2, 3])"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stackInstance.push(1)\n",
    "stackInstance.push(2)\n",
    "stackInstance.push(3)\n",
    "stackInstance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stackInstance.top()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "MyStack([1, 2])"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stackInstance.pop()\n",
    "stackInstance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stackInstance.empty()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "e83c87145cfd5d139b0a7599b26c7533043aedf92a6f420dd74299e47a5263f5"
  },
  "kernelspec": {
   "display_name": "Python 3.9.7 ('base')",
   "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.9.7"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}