cs_stacks_queues.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Data Structures: Stacks, Queues",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Y9l9lBl7QmHe"
      },
      "source": [
        "<table align=\"left\" width=\"590\" height=\"144\" style=\"height: 67px; width: 565px;\">\n",
        "<tbody>\n",
        "<tr>\n",
        "<td width=\"82\"><img src=\"https://static1.squarespace.com/static/5992c2c7a803bb8283297efe/t/59c803110abd04d34ca9a1f0/1530629279239/\" /></td>\n",
        "<td style=\"width: 422px; height: 67px;\">\n",
        "<h1 style=\"text-align: left;\">Data Structures: Stacks, Queues</h1>\n",
        "<p><a href=\"https://colab.research.google.com/github/KenzieAcademy/python-notebooks/blob/master/cs_stacks_queues.ipynb\"> <img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\" align=\"left\" width=\"188\" height=\"32\" /> </a></p>\n",
        "</td>\n",
        "</tr>\n",
        "</tbody>\n",
        "</table>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6iF_YsnmZWMF"
      },
      "source": [
        "### Stacks"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5eVwpyW3Qhcl"
      },
      "source": [
        "class Stack:\n",
        "    \"\"\"\n",
        "    A Last In, First Out (LIFO) Stack implementation.\n",
        "\n",
        "    [1, 2, 3] in (push) <--> (pop) out\n",
        "    \"\"\"\n",
        "    def __init__(self):\n",
        "        self.items = []\n",
        "\n",
        "    def is_empty(self):\n",
        "        return self.items == []\n",
        "\n",
        "    def peek(self):\n",
        "        if self.is_empty():\n",
        "            return \"Stack is empty.\"\n",
        "        return self.items[-1]\n",
        "\n",
        "    def push(self, item):\n",
        "        self.items.append(item)  # O(1) -- constant time\n",
        "\n",
        "    def pop(self):\n",
        "        return self.items.pop()  # O(1) -- constant time\n",
        "\n",
        "    def size(self):\n",
        "        return len(self.items)\n",
        "\n",
        "    def __repr__(self):\n",
        "        return str(self.items)\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jpxD__ynkl8m"
      },
      "source": [
        "import random\n",
        "\n",
        "s = Stack()\n",
        "print(f\"Current stack of {s.size()} items: {s}\")\n",
        "\n",
        "# fill the stack with 10 random numbers from 1 to 20\n",
        "for i in random.sample(range(1, 21), 10):\n",
        "  s.push(i)\n",
        "\n",
        "print(f\"Current stack of {s.size()} items: {s}\")\n",
        "print(f\"Pop from the top of the stack: {s.pop()}\")\n",
        "print(f\"Current stack of {s.size()} items: {s}\")\n",
        "\n",
        "# let's see the rest of the items while we empty the stack\n",
        "print(\"\\nEmptying the stack...\")\n",
        "while not s.is_empty():\n",
        "  print(s.pop(), end=\", \")\n",
        "print(\"\\n\")\n",
        "\n",
        "print(f\"Current stack of {s.size()} items: {s}\")\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NYkl0zkcZYzk"
      },
      "source": [
        "### Queues"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3UVwzD2wRb00"
      },
      "source": [
        "class Queue:\n",
        "    \"\"\"\n",
        "    A First In, First Out (FIFO) Queue implementation.\n",
        "\n",
        "    (dequeue) out <-- [1, 2, 3] <-- in (enqueue)\n",
        "    \"\"\"\n",
        "    def __init__(self):\n",
        "        self.items = []\n",
        "\n",
        "    def is_empty(self):\n",
        "        return self.items == []\n",
        "\n",
        "    def enqueue(self, item):\n",
        "        self.items.append(item)  # O(1) -- constant time\n",
        "\n",
        "    def dequeue(self):\n",
        "        return self.items.pop(0)  # O(n) -- linear time\n",
        "\n",
        "    def size(self):\n",
        "        return len(self.items)\n",
        "\n",
        "    def __repr__(self):\n",
        "        return str(self.items)\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WRWqx4czhnXK"
      },
      "source": [
        "import random\n",
        "\n",
        "q = Queue()\n",
        "print(f\"Current queue of {q.size()} items: {q}\")\n",
        "\n",
        "# fill the queue with 10 random numbers from 1 to 20\n",
        "for i in random.sample(range(1, 21), 10):\n",
        "  q.enqueue(i)\n",
        "\n",
        "print(f\"Current queue of {q.size()} items: {q}\")\n",
        "print(f\"Next item out of the queue: {q.dequeue()}\")\n",
        "print(f\"Current queue of {q.size()} items: {q}\")\n",
        "\n",
        "# let's see the rest of the items while we empty the queue\n",
        "print(\"\\nEmptying the queue...\")\n",
        "while not q.is_empty():\n",
        "  print(q.dequeue(), end=\", \")\n",
        "print(\"\\n\")\n",
        "\n",
        "print(f\"Current queue of {q.size()} items: {q}\")"
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}