stacks_and_queues.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyPMtlAhF700A1K7AvyqtNdK"
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "# TAREA STACKS AND QUEUES\n",
        "<p>BY ANDRES HERNANDEZ MAGAÑA<p>\n",
        "\n",
        "## In this first section i'm going to implement a stack using a Linked-List\n",
        "<p>to do this im not exactly going to use an stack, im just going to simulate its actual working, we need to create the methods of an stack by defining functions such as push and pop, itself the stack has more funtionalities, but due resons as not making this work overextended im not creating everyone of them\n",
        "<p>"
      ],
      "metadata": {
        "id": "HRXfnUEmx-kU"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# here i created the nodes of the linked list\n",
        "class node:\n",
        "  def __init__(self, value):\n",
        "    self.value = value\n",
        "    self.next = None\n",
        "\n",
        "# we need to specify the begining\n",
        "class LinkedList:\n",
        "  def __init__(self):\n",
        "    self.head = None\n",
        "#push method\n",
        "  def push(self, value):\n",
        "    stack = node(value)\n",
        "    if self.head is None:\n",
        "      self.head = stack\n",
        "      return\n",
        "    current = self.head\n",
        "    while(current.next):\n",
        "      current = current.next\n",
        "    current.next = stack\n",
        "#pop method\n",
        "  def pop(self):\n",
        "    if self.head is None:\n",
        "      return\n",
        "    if self.head.next is None:\n",
        "      self.head = None\n",
        "      return\n",
        "    current = self.head\n",
        "    while(current.next.next):\n",
        "      current = current.next\n",
        "    current.next = None\n",
        "\n",
        "#print method\n",
        "  def printStack(self):\n",
        "    current = self.head\n",
        "    while(current):\n",
        "      print(current.value)\n",
        "      current = current.next"
      ],
      "metadata": {
        "id": "pn5V_p7EyA84"
      },
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "###lets give it some values"
      ],
      "metadata": {
        "id": "rSKIVHSvyFYW"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "newStack = LinkedList()\n",
        "newStack.push(1)\n",
        "newStack.push(2)\n",
        "newStack.push(3)\n",
        "newStack.printStack()\n",
        ""
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "7-zStThAyKJG",
        "outputId": "4f5227f0-6148-477f-cc0a-293d27d4efe4"
      },
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1\n",
            "2\n",
            "3\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "<p>as you can see it works by adding at the end, now lets pop <p>"
      ],
      "metadata": {
        "id": "s25EjobHySLI"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "newStack.pop()\n",
        "newStack.printStack()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "waue-POuylmb",
        "outputId": "8ac02f2f-a3aa-4251-f077-6836d94fe2c3"
      },
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1\n",
            "2\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## in this next section im implementing the usual stack, but with a method for obtaining the mimimum number in\n",
        "<p>first is to set the usuals push and pop, and to aproach a correct minumum number i did a extra stack and in the both metods compare to see the minimum number<p>"
      ],
      "metadata": {
        "id": "zkj79ciOyu0x"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class stack:\n",
        "    def __init__(self):\n",
        "        self.newStack = []\n",
        "        self.minimum = []\n",
        "\n",
        "    def push(self, num):\n",
        "        self.newStack.append(num)\n",
        "        if not self.minimum:\n",
        "            self.minimum.append(num)\n",
        "        elif self.minimum[-1] >= num:\n",
        "            self.minimum.append(num)\n",
        "\n",
        "    def pop(self):\n",
        "        if self.newStack[-1] == self.minimum[-1]:\n",
        "            self.minimum.pop()\n",
        "        self.newStack.pop()\n",
        "    def min(self):\n",
        "        if not self.minimum:\n",
        "            return None\n",
        "        else:\n",
        "            return self.minimum[-1]"
      ],
      "metadata": {
        "id": "50JeuFUzzN7e"
      },
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "###lets give it some values and pops"
      ],
      "metadata": {
        "id": "GIIgTyS-zqHK"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "stack1 = stack()\n",
        "stack1.push(4)\n",
        "stack1.push(3)\n",
        "stack1.push(1)\n",
        "stack1.push(5)\n",
        "print(stack1.newStack)\n",
        "print(stack1.minimum)\n",
        "print(stack1.min())\n",
        "stack1.pop()\n",
        "stack1.pop()\n",
        "print(stack1.newStack)\n",
        "print(stack1.minimum)\n",
        "print(stack1.min())"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "oyl2CConzpaS",
        "outputId": "28f51ef4-3d1b-4f6f-e93f-adbdb12d6187"
      },
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[4, 3, 1, 5]\n",
            "[4, 3, 1]\n",
            "1\n",
            "[4, 3]\n",
            "[4, 3]\n",
            "3\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#implementing a n numbers of stacks in a single list\n",
        "<p>originaly this was meant to be for 2 or 3 stacks but i save time and made it for n numbers, to achieve this i did not assign a number of stacks neither a maximum number of elements to save (size), and that is made by de user <p>"
      ],
      "metadata": {
        "id": "LrnidO8Kqe1q"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class lists:\n",
        "    def __init__(self, stackNum, size):\n",
        "        self.listsRet = []\n",
        "        self.size = size\n",
        "        self.stackNum = stackNum\n",
        "        for _ in range(stackNum):\n",
        "            self.new_list = []\n",
        "            self.listsRet.append(self.new_list)\n",
        "    # push value to a determined stack\n",
        "    def push(self, value, pos):\n",
        "        tot = 0\n",
        "        for j in range(self.stackNum):\n",
        "            tot += int((len(self.listsRet[j])))\n",
        "        if tot <= self.size:\n",
        "            self.listsRet[pos - 1].append(value)\n",
        "        else:\n",
        "            return print(\"list is full\")\n",
        "\n",
        "    def pop(self, pos):\n",
        "        if not self.listsRet[pos - 1]:\n",
        "            return None\n",
        "        else:\n",
        "            self.listsRet[pos - 1].pop()\n",
        "\n",
        "    def show(self):\n",
        "        print(self.listsRet)"
      ],
      "metadata": {
        "id": "JxvrN2FQrbw0"
      },
      "execution_count": 18,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "<p>i made some basic methods, but very functional im going to show how with a number of stacks and a maximum number of elements it gets what we needed<p>"
      ],
      "metadata": {
        "id": "Zkb3twXsr-al"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "newlist = lists(3, 5)\n",
        "newlist.push(1, 1)\n",
        "newlist.push(2, 2)\n",
        "newlist.push(3, 3)\n",
        "newlist.show()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "De7eNdNAscoq",
        "outputId": "77c274c6-44da-4380-b71d-6389815de07b"
      },
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[[1], [2], [3]]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "newlist.pop(3)\n",
        "newlist.show()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "aEC0YHvLsx0O",
        "outputId": "6ce467e1-6c4d-4ec0-eba3-a7e77b159361"
      },
      "execution_count": 20,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[[1], [2], []]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#lets overflow it\n",
        "newlist.push(2, 2)\n",
        "newlist.push(2, 2)\n",
        "newlist.push(3, 3)\n",
        "newlist.push(3, 3)\n",
        "newlist.push(3, 3)\n",
        "newlist.show()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "cm_2K9OntE1_",
        "outputId": "6ab96900-bc00-44da-a5bb-c2b06e59f6fc"
      },
      "execution_count": 22,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "list is full\n",
            "list is full\n",
            "list is full\n",
            "list is full\n",
            "list is full\n",
            "[[1], [2, 2, 2], [3, 3]]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "<p> instead of saving extra number over the limit i could send an error but in this way we can see graphicly is is over the limit"
      ],
      "metadata": {
        "id": "q4haJh9Nuf8t"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Priority queue\n",
        "<p>in this last section im coding a priority queue, using a linked list, the priority of the elements could be diferent, but in this example its priority is te value itself<p>"
      ],
      "metadata": {
        "id": "Riqs6H829_iX"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class PriorityQueueNode:\n",
        "    def __init__(self, item):\n",
        "        self.item = item\n",
        "        self.next = None\n",
        "\n",
        "class PriorityQueue:\n",
        "    def __init__(self):\n",
        "        self.head = None\n",
        "\n",
        "    def push(self, item):\n",
        "        new_node = PriorityQueueNode(item)\n",
        "        if not self.head or item > self.head.item:\n",
        "            new_node.next = self.head\n",
        "            self.head = new_node\n",
        "        else:\n",
        "            current = self.head\n",
        "            while current.next and item <= current.next.item:\n",
        "                current = current.next\n",
        "            new_node.next = current.next\n",
        "            current.next = new_node\n",
        "\n",
        "    def pop(self):\n",
        "        if not self.head:\n",
        "            raise IndexError(\"Priority queue is empty\")\n",
        "        item = self.head.item\n",
        "        self.head = self.head.next\n",
        "        return item\n",
        "newQueue = PriorityQueue()\n",
        "\n",
        "newQueue.push(3)\n",
        "newQueue.push(1)\n",
        "newQueue.push(2)\n",
        "\n",
        "print(newQueue.pop())\n",
        "print(newQueue.pop())\n",
        "print(newQueue.pop())"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "PPwE2p3H-XUT",
        "outputId": "e24e3219-289d-42ca-a683-7e37fb4167af"
      },
      "execution_count": 24,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "3\n",
            "2\n",
            "1\n"
          ]
        }
      ]
    }
  ]
}