{ "cells": [ { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "5EWH_v04jmET" }, "source": [ "

\n", "IIC2233 Apunte Programación Avanzada
\n", "© 2015 Karim Pichara - Christian Pieringer. Todos los derechos reservados.\n", "
\n", " Modificado desde 2018-1 al 2025-2 por Equipo Docente IIC2233\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Tabla de contenidos\n", "\n", "1. [Stacks](#Stacks)\n", " 1. [Operaciones](#Operaciones-sobre-stacks)\n", " 2. [Implementación en Python](#Implementación-en-Python)\n", " 3. [Ejemplos de uso](#Ejemplos-reales-de-uso)\n", "2. [Colas](#Colas-(queues))\n", " 1. [Operaciones](#Operaciones-sobre-colas)\n", " 2. [Implementacion en Python](#implementación-en-python-colas-de-doble-extremo-deque)\n", " 1. [`list` vs `deque`](#Comparando-list-y-deque)\n", " 3. [Ejemplos de uso](#Ejemplo-de-uso-con-palíndromos)\n", " \n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# *Stacks*\n", "\n", "Un *stack* (o pila, en español) es una estructura de datos que funciona como si fuera una pila de objetos, uno arriba del otro. Por ejemplo, supongamos que estamos apilando platos para lavarlos. Cada vez que se agrega un plato al montón, éste se coloca arriba de la pila, y cuando queremos sacar un plato para lavarlo sacamos uno de arriba de la pila también, por lo que siempre sacaremos el último que hayamos puesto. " ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "tIuB-cVojmEU" }, "source": [ "## Operaciones sobre stacks\n", "\n", "Un *stack* tiene dos operaciones básicas:\n", "\n", "- ***Push***: Agrega un elemento al tope del *stack*.\n", "- ***Pop***: Elimina el elemento que está en el tope del *stack*. Esto siempre sacará el último elemento que haya sido agregado.\n", "\n", "Hay una tercera operación común entre varias estructuras llamada ***peek***, que sólo muestra el elemento que está en el tope sin sacarlo del *stack*. También, es posible consultar cuántos elementos tiene el *stack*, o si éste se encuentra vacío.\n", "\n", "![](img/stacks.png)\n", "\n", "El *stack* es una estructura de datos de tipo **Last In, First Out** (LIFO), es decir, lo último que entra es lo primero en salir. Como consecuencia, si queremos sacar el primer elemento, antes debemos sacar todos los demás." ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "YTEUVy6AjmEV" }, "source": [ "## Implementación en Python\n", "\n", "En Python, podemos representar *stacks* mediante listas. A continuación, vemos una tabla con las operaciones del *stack* y su implementación en Python, seguida de ejemplos para cada operación:\n", "\n", "| Operación | Código Python |Descripción |\n", "|--------------------------------------------|--------------------------|------------------------------------------------------|\n", "| Crear *stack* | `stack = []` |Crea un *stack* vacío |\n", "| *Push* | `stack.append(elemento)` |Agrega un elemento al tope del *stack* |\n", "| *Pop* | `stack.pop()` |Retorna y extrae el elemento del tope del *stack* |\n", "| *Peek* | `stack[-1]` |Retorna el elemento del tope del *stack* sin extraerlo|\n", "| *length* | `len(stack)` |Retorna la cantidad de elementos en el *stack* |\n", "| *is\\_empty* | `len(stack) == 0` |Retorna `true` si el *stack* está vacío |" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "colab": { "autoexec": { "startup": false, "wait_interval": 0 }, "base_uri": "https://localhost:8080/", "height": 34, "output_extras": [ { "item_id": 1 } ] }, "colab_type": "code", "executionInfo": { "elapsed": 620, "status": "ok", "timestamp": 1520877919147, "user": { "displayName": "Jaime Castro Retamal", "photoUrl": "//lh5.googleusercontent.com/-d7ImDI1yYBM/AAAAAAAAAAI/AAAAAAAADF4/eQh4r_ES9eE/s50-c-k-no/photo.jpg", "userId": "114351437388776670979" }, "user_tz": 180 }, "id": "ZFiQDjNajmEX", "outputId": "ea586668-7362-4188-bb6a-ada7b363a818" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 2, 3]\n" ] } ], "source": [ "# Un stack vacío\n", "stack = []\n", "\n", "# Hacemos push de tres elementos\n", "stack.append(1)\n", "stack.append(2)\n", "stack.append(3)\n", "\n", "print(stack)" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "IWLFq1FJWnOw" }, "source": [ "Ahora, si hacemos *pop* esperamos obtener el último elemento que agregamos:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "colab": { "autoexec": { "startup": false, "wait_interval": 0 }, "base_uri": "https://localhost:8080/", "height": 51, "output_extras": [ { "item_id": 1 } ] }, "colab_type": "code", "executionInfo": { "elapsed": 765, "status": "ok", "timestamp": 1520877919978, "user": { "displayName": "Jaime Castro Retamal", "photoUrl": "//lh5.googleusercontent.com/-d7ImDI1yYBM/AAAAAAAAAAI/AAAAAAAADF4/eQh4r_ES9eE/s50-c-k-no/photo.jpg", "userId": "114351437388776670979" }, "user_tz": 180 }, "id": "qFNycRYPWjsv", "outputId": "99c9fa6b-1372-4380-ab16-abe3b09d7fcd" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Hicimos pop de 3\n", "El stack quedó: [1, 2]\n" ] } ], "source": [ "# Pop\n", "elemento = stack.pop()\n", "print(f\"Hicimos pop de {elemento}\")\n", "print(f\"El stack quedó: {stack}\")" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "HuzR4L8BW9Ag" }, "source": [ "Ahora, si hacemos *peek* veremos el tope del *stack*, pero éste quedará intacto:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "colab": { "autoexec": { "startup": false, "wait_interval": 0 }, "base_uri": "https://localhost:8080/", "height": 51, "output_extras": [ { "item_id": 1 } ] }, "colab_type": "code", "executionInfo": { "elapsed": 583, "status": "ok", "timestamp": 1520877920607, "user": { "displayName": "Jaime Castro Retamal", "photoUrl": "//lh5.googleusercontent.com/-d7ImDI1yYBM/AAAAAAAAAAI/AAAAAAAADF4/eQh4r_ES9eE/s50-c-k-no/photo.jpg", "userId": "114351437388776670979" }, "user_tz": 180 }, "id": "Begzisy6XMxn", "outputId": "eba72d96-9ae0-4aef-8637-23d7a19c8b71" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Tope del stack: 2\n", "Stack: [1, 2]\n" ] } ], "source": [ "# Peek\n", "tope_stack = stack[-1]\n", "print(f\"Tope del stack: {tope_stack}\")\n", "print(f\"Stack: {stack}\")" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "xNbNi1BMXhlb" }, "source": [ "Por último, podemos ver cuántos elementos hay y si el *stack* está vacío:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "colab": { "autoexec": { "startup": false, "wait_interval": 0 }, "base_uri": "https://localhost:8080/", "height": 51, "output_extras": [ { "item_id": 1 } ] }, "colab_type": "code", "executionInfo": { "elapsed": 546, "status": "ok", "timestamp": 1520877921206, "user": { "displayName": "Jaime Castro Retamal", "photoUrl": "//lh5.googleusercontent.com/-d7ImDI1yYBM/AAAAAAAAAAI/AAAAAAAADF4/eQh4r_ES9eE/s50-c-k-no/photo.jpg", "userId": "114351437388776670979" }, "user_tz": 180 }, "id": "ebqdRU1jXqem", "outputId": "99ec91e7-2fbe-46bd-eca0-c64f83fb6fb2" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "El stack tiene 2 elementos.\n", "¿El stack está vacío? False\n" ] } ], "source": [ "# Length\n", "print(f\"El stack tiene {len(stack)} elementos.\")\n", "\n", "# Función para revisar si el stack está vacío\n", "def is_empty(s):\n", " return len(s) == 0\n", "\n", "print(f\"¿El stack está vacío? {is_empty(stack)}\")" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "colab": { "autoexec": { "startup": false, "wait_interval": 0 }, "base_uri": "https://localhost:8080/", "height": 51, "output_extras": [ { "item_id": 1 } ] }, "colab_type": "code", "executionInfo": { "elapsed": 587, "status": "ok", "timestamp": 1520877921845, "user": { "displayName": "Jaime Castro Retamal", "photoUrl": "//lh5.googleusercontent.com/-d7ImDI1yYBM/AAAAAAAAAAI/AAAAAAAADF4/eQh4r_ES9eE/s50-c-k-no/photo.jpg", "userId": "114351437388776670979" }, "user_tz": 180 }, "id": "wWqYVzTDYfY0", "outputId": "42ad8a34-af2a-4db1-f3f3-7c65479b9a66" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Stack: [1]\n", "¿El stack está vacío? False\n" ] } ], "source": [ "stack.pop()\n", "print(f\"Stack: {stack}\")\n", "print(f\"¿El stack está vacío? {is_empty(stack)}\")" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "colab": { "autoexec": { "startup": false, "wait_interval": 0 }, "base_uri": "https://localhost:8080/", "height": 51, "output_extras": [ { "item_id": 1 } ] }, "colab_type": "code", "executionInfo": { "elapsed": 681, "status": "ok", "timestamp": 1520877922580, "user": { "displayName": "Jaime Castro Retamal", "photoUrl": "//lh5.googleusercontent.com/-d7ImDI1yYBM/AAAAAAAAAAI/AAAAAAAADF4/eQh4r_ES9eE/s50-c-k-no/photo.jpg", "userId": "114351437388776670979" }, "user_tz": 180 }, "id": "aHt_gRerYiZ9", "outputId": "0150559f-2d74-4ec1-b415-637f480bbe50" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Stack: []\n", "¿El stack está vacío? True\n" ] } ], "source": [ "stack.pop()\n", "print(f\"Stack: {stack}\")\n", "print(f\"¿El stack está vacío? {is_empty(stack)}\")" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "CvYs-Za2YyYN" }, "source": [ "## Ejemplos reales de uso" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "jPES-gDYjmEd" }, "source": [ "Un ejemplo real del uso de *stacks* en una aplicación es el botón *back* (volver) en los navegadores de internet. Durante la navegación todas las direcciones van siendo ingresadas en un *stack*. Cuando el usuario presiona el botón para retroceder en la navegación, la última dirección es recuperada.\n", "\n", "![](img/back-button-stacks.png)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "colab": { "autoexec": { "startup": false, "wait_interval": 0 }, "base_uri": "https://localhost:8080/", "height": 119, "output_extras": [ { "item_id": 1 } ] }, "colab_type": "code", "executionInfo": { "elapsed": 866, "status": "ok", "timestamp": 1520878173469, "user": { "displayName": "Jaime Castro Retamal", "photoUrl": "//lh5.googleusercontent.com/-d7ImDI1yYBM/AAAAAAAAAAI/AAAAAAAADF4/eQh4r_ES9eE/s50-c-k-no/photo.jpg", "userId": "114351437388776670979" }, "user_tz": 180 }, "id": "3WQ32ljLjmEf", "outputId": "6305f17a-d6f5-4d8f-8e1d-9bf1faee551b" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Ir -> Cargando URL: http://www.uc.cl\n", "Ir -> Cargando URL: http://www.uc.cl/es/programas-de-estudio\n", "Ir -> Cargando URL: http://www.uc.cl/es/doctorado\n", "Página actual: http://www.uc.cl/es/doctorado\n", "Back-> Cargando URL: http://www.uc.cl/es/programas-de-estudio\n", "Página actual: http://www.uc.cl/es/programas-de-estudio\n", "Ir -> Cargando URL: https://stackoverflow.com/\n", "Ir -> Cargando URL: https://github.com/IIC2233/contenidos\n", "Back-> Cargando URL: https://stackoverflow.com/\n", "Página actual: https://stackoverflow.com/\n" ] } ], "source": [ "class Navegador:\n", "\n", " def __init__(self, current_url='https://www.google.com'):\n", " self.__urls_stack = []\n", " self.__current_url = current_url\n", "\n", " def __cargar_url(self, url):\n", " self.__current_url = url\n", " print(f\"Cargando URL: {url}\")\n", "\n", " def ir(self, url):\n", " self.__urls_stack.append(self.__current_url)\n", " print('Ir ->', end=' ')\n", " self.__cargar_url(url)\n", "\n", " def volver(self):\n", " last_url = self.__urls_stack.pop()\n", " print('Back->', end=' ')\n", " self.__cargar_url(last_url)\n", "\n", " def mostrar_pagina_actual(self):\n", " print(f\"Página actual: {self.__current_url}\")\n", "\n", "\n", "browser = Navegador()\n", "browser.ir('http://www.uc.cl')\n", "browser.ir('http://www.uc.cl/es/programas-de-estudio')\n", "browser.ir('http://www.uc.cl/es/doctorado')\n", "\n", "browser.mostrar_pagina_actual()\n", "browser.volver()\n", "browser.mostrar_pagina_actual()\n", "browser.ir('https://stackoverflow.com/')\n", "browser.ir('https://github.com/IIC2233/contenidos')\n", "browser.volver()\n", "browser.mostrar_pagina_actual()" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "gGDY0MasjmEk" }, "source": [ "Otro ejemplo para el uso de *stacks* es revertir secuencias. Por ejemplo, con el siguiente código:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "cellView": "code", "colab": { "autoexec": { "startup": false, "wait_interval": 0 }, "base_uri": "https://localhost:8080/", "height": 238, "output_extras": [ { "item_id": 1 } ] }, "colab_type": "code", "executionInfo": { "elapsed": 597, "status": "ok", "timestamp": 1520879167226, "user": { "displayName": "Jaime Castro Retamal", "photoUrl": "//lh5.googleusercontent.com/-d7ImDI1yYBM/AAAAAAAAAAI/AAAAAAAADF4/eQh4r_ES9eE/s50-c-k-no/photo.jpg", "userId": "114351437388776670979" }, "user_tz": 180 }, "id": "4RroPdPPaY_n", "outputId": "b735e4f7-3eb4-401c-b324-0f93594d3160", "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Entrada:\n", "The friend who can be silent with us\n", "in a moment of despair or confusion,\n", "who can stay with us in an hour of grief and bereavement,\n", "who can tolerate not knowing... not healing, not curing...\n", "that is a friend who cares.\n", "\n", "Salida:\n", "that is a friend who cares.\n", "who can tolerate not knowing... not healing, not curing...\n", "who can stay with us in an hour of grief and bereavement,\n", "in a moment of despair or confusion,\n", "The friend who can be silent with us\n" ] } ], "source": [ "class Texto:\n", "\n", " def __init__(self, original):\n", " self.pila = []\n", " self.original = original\n", "\n", " def invertir_lineas(self):\n", " print('Entrada:')\n", " for linea in self.original.split('\\n'):\n", " print(linea)\n", " self.pila.append(linea)\n", " print()\n", "\n", " print('Salida:')\n", " while len(self.pila) > 0:\n", " print(self.pila.pop())\n", "\n", "\n", "texto_original = \"\"\"The friend who can be silent with us\n", "in a moment of despair or confusion,\n", "who can stay with us in an hour of grief and bereavement,\n", "who can tolerate not knowing... not healing, not curing...\n", "that is a friend who cares.\"\"\"\n", "\n", "t = Texto(texto_original)\n", "t.invertir_lineas()\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Colas (*queues*)\n", "\n", "Una cola es una estructura de datos secuencial que mantiene objetos ordenados de acuerdo a su orden de llegada. Funciona igual a una cola para pagar las cuentas en el mundo real, pues cada vez que llega una persona ésta se coloca al final, y la persona que está al principio es atendida y sale de la fila. Es por esto que una cola es una estructura de tipo ***First-in, First-out*** (FIFO).\n", "\n", "![](img/queues.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Operaciones sobre colas\n", "\n", "Una cola tiene dos operaciones principales:\n", "- ***Enqueue***: Agrega un elemento al final de la cola.\n", "- ***Dequeue***: Saca el elemento que está al inicio de la cola. Esto siempre sacará el elemento que lleva más tiempo en la cola.\n", "\n", "Además, tiene una operación ***peek*** que permite ver el primer elemento de la cola sin sacarlo, y es posible revisar la cantidad de elementos en la cola o si ésta se encuentra vacía.\n", "\n", "Si intentamos implementar una cola usando una lista de Python utilizando una lista, encontraremos que implementar ***enqueue*** es directo, pues basta con realizar un `append` a la lista. Sin embargo, si bien implementar ***dequeue*** mediante `pop(0)` funciona correctamente, esto **no es eficiente**.\n", "\n", "Una lista de python guarda sus elementos en un segmento continuo de memoria. Esto significa que al eliminar el elemento de la posición $0$, si la lista tenía $N$ elementos, el resultado es una lista de largo $N-1$ con un espacio de memoría vacío al inicio de esta. Para solucionar este problema, todos los elementos restantes deberan ser desplazados una posición a la izquierda, es decir, el de la posición $1$ pasa a la posición $0$, el de la posición $2$ pasa a la posición $1$, $\\dots,$ hasta que el de la posición $N$ pasa a la posición $N-1$, dejando todo el espacio vacío al final de la lista. Por esto, al ejecutar `pop(0)` se estarán realizando $N$ operaciones: eliminar el elemento, y mover $N-1$ elementos a la izquierda y es fácil ver que para listas muy grandes, esta eliminación tomará una cantidad considerable de tiempo en comparación con agregar un elemento a la cola (con `append`), donde solo se realiza una operación.\n", "\n", "Dado lo anterior, para evitar problemas de eficiencia necesitamos buscar una alternativa a las listas si queremos representar colas en Python.\n" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "Q-SENzwJP6oJ" }, "source": [ "## Implementación en Python: Colas de doble extremo (*deque*)\n", "\n", "Un [*deque*](https://docs.python.org/3/library/collections.html#collections.deque) (pronunciado \"*dikiu*\" y proviniente de *double-ended queue*) es una estructura secuencial en la que es posible **agregar y sacar elementos desde ambos extremos en forma eficiente**, con un *costo constante por operación*. Esto quiere decir que, independientemente del largo de un *deque*, si éste tiene $N$ elementos, para agregar y sacar elementos siempre ejecutará *la misma* cantidad de operaciones.\n", "Como se explicó anteriormente, esto es mucho mejor que si utilizamos una *lista*, donde la cantidad de operaciones depende de la cantidad de elementos que contiene. En Python, esta estructura es provista por la clase `deque` del módulo `collections` y las principales operaciones que soporta son:\n", "\n", "| Operación | Código Python | Descripción |\n", "|----------------|------------------------------|------------------------------------------------------------------|\n", "| Crear *deque* | `deque()` | Crea un *deque* vacío |\n", "| Crear *deque* | `deque(lista)` | Crea un *deque* a partir de los elementos de una lista |\n", "| *Add first* | `deque.appendleft(elemento)` | Agrega un elemento al inicio del *deque* |\n", "| *Add last* | `deque.append(elemento)` | Agrega un elemento al final del *deque* |\n", "| *Delete first* | `deque.popleft()` | Retorna y extrae el primer elemento del *deque* |\n", "| *Delete last* | `deque.pop()` | Retorna y extrae el último elemento del *deque* |\n", "| *First* | `deque[0]` | Retorna sin extraer el primer elemento del *deque* |\n", "| *Last* | `deque[-1]` | Retorna sin extraer el último elemento del *deque* |\n", "| *length* | `len(deque)` | Retorna el número de elementos en el *deque* |\n", "| *Is empty* | `len(deque) == 0` | Retorna true si el *deque* está vacío |\n", "| *Clear* | `deque.clear()` | Limpia el *deque* |\n", "| *Remove* | `deque.remove(elemento)` | Saca el primer elemento del *deque* que sea igual a `elemento` |\n", "| *Count* | `deque.count(elemento)` | Cuenta el número de elementos iguales a `elemento` en el *deque* |\n", "\n", "El *deque* soporta acceso de lectura y escritura en el elemento de la posición `i`, con la sentencia `deque[i]`. Sin embargo, esta operación **no es eficiente** como en el caso de las listas. En un *deque*, para llegar a la posición `i` el computador inicia en la posición `0` y se va moviendo hasta encontrar la posición `i` para poder leerlo (es decir, requiere recorrer todos los elementos anteriores a `i` para llegar a `i`). \n" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "colab": { "autoexec": { "startup": false, "wait_interval": 0 }, "base_uri": "https://localhost:8080/", "height": 34, "output_extras": [ { "item_id": 1 } ] }, "colab_type": "code", "executionInfo": { "elapsed": 758, "status": "ok", "timestamp": 1520887738362, "user": { "displayName": "Jaime Castro Retamal", "photoUrl": "//lh5.googleusercontent.com/-d7ImDI1yYBM/AAAAAAAAAAI/AAAAAAAADF4/eQh4r_ES9eE/s50-c-k-no/photo.jpg", "userId": "114351437388776670979" }, "user_tz": 180 }, "id": "tFBZ0Fwd86-5", "outputId": "c48ab125-f7eb-466d-8682-024e025928a4" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "deque([1, 2, 3])\n" ] } ], "source": [ "# Importamos deque\n", "from collections import deque\n", "\n", "\n", "# Cola vacía\n", "cola = deque()\n", "\n", "# Agregamos elementos a la cola (enqueue)\n", "cola.append(1)\n", "cola.append(2)\n", "cola.append(3)\n", "\n", "print(cola)" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "liSWcd_U98MR" }, "source": [ "Ahora, mostramos como hacer *dequeue* con `popleft`." ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "colab": { "autoexec": { "startup": false, "wait_interval": 0 }, "base_uri": "https://localhost:8080/", "height": 51, "output_extras": [ { "item_id": 1 } ] }, "colab_type": "code", "executionInfo": { "elapsed": 693, "status": "ok", "timestamp": 1520887740780, "user": { "displayName": "Jaime Castro Retamal", "photoUrl": "//lh5.googleusercontent.com/-d7ImDI1yYBM/AAAAAAAAAAI/AAAAAAAADF4/eQh4r_ES9eE/s50-c-k-no/photo.jpg", "userId": "114351437388776670979" }, "user_tz": 180 }, "id": "SLsy_EuF-FbJ", "outputId": "f9fdc629-99e2-4293-b6ed-14a52bc0a229" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Hicimos dequeue de 1.\n", "La cola quedó: deque([2, 3])\n" ] } ], "source": [ "# Dequeue\n", "elemento = cola.popleft()\n", "\n", "print(f\"Hicimos dequeue de {elemento}.\")\n", "print(f\"La cola quedó: {cola}\")" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "LnaHYqxK-Zjp" }, "source": [ "Podemos ver el primer elemento de la cola sin extraerlo (*peek*)." ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "colab": { "autoexec": { "startup": false, "wait_interval": 0 }, "base_uri": "https://localhost:8080/", "height": 34, "output_extras": [ { "item_id": 1 } ] }, "colab_type": "code", "executionInfo": { "elapsed": 655, "status": "ok", "timestamp": 1520887827358, "user": { "displayName": "Jaime Castro Retamal", "photoUrl": "//lh5.googleusercontent.com/-d7ImDI1yYBM/AAAAAAAAAAI/AAAAAAAADF4/eQh4r_ES9eE/s50-c-k-no/photo.jpg", "userId": "114351437388776670979" }, "user_tz": 180 }, "id": "K--hdohN-huo", "outputId": "2202763e-efbe-4ec9-9c01-25ceefece1cf" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Primer elemento de la cola: 2\n" ] } ], "source": [ "# Peek\n", "print(f\"Primer elemento de la cola: {cola[0]}\")" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "Gi5Evy7L-tYh" }, "source": [ "Por último, podemos ver cuántos elementos hay y si la cola está vacía." ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "colab": { "autoexec": { "startup": false, "wait_interval": 0 }, "base_uri": "https://localhost:8080/", "height": 51, "output_extras": [ { "item_id": 1 } ] }, "colab_type": "code", "executionInfo": { "elapsed": 791, "status": "ok", "timestamp": 1520887898194, "user": { "displayName": "Jaime Castro Retamal", "photoUrl": "//lh5.googleusercontent.com/-d7ImDI1yYBM/AAAAAAAAAAI/AAAAAAAADF4/eQh4r_ES9eE/s50-c-k-no/photo.jpg", "userId": "114351437388776670979" }, "user_tz": 180 }, "id": "ib-4vO35-zJu", "outputId": "6bb871de-5b32-4d38-a469-f6fad2c45f14" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "La cola tiene 2 elementos.\n", "¿La cola está vacía? False\n" ] } ], "source": [ "# Length\n", "print(f\"La cola tiene {len(cola)} elementos.\")\n", "\n", "# Función para revisar si la cola está vacía\n", "def is_empty(s):\n", " return len(s) == 0\n", "\n", "print(f\"¿La cola está vacía? {is_empty(cola)}\")" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "colab": { "autoexec": { "startup": false, "wait_interval": 0 }, "base_uri": "https://localhost:8080/", "height": 51, "output_extras": [ { "item_id": 1 } ] }, "colab_type": "code", "executionInfo": { "elapsed": 656, "status": "ok", "timestamp": 1520887952487, "user": { "displayName": "Jaime Castro Retamal", "photoUrl": "//lh5.googleusercontent.com/-d7ImDI1yYBM/AAAAAAAAAAI/AAAAAAAADF4/eQh4r_ES9eE/s50-c-k-no/photo.jpg", "userId": "114351437388776670979" }, "user_tz": 180 }, "id": "Ss3beS5S-9eJ", "outputId": "4370826b-b394-4dd6-c2f2-af5215fb46ad" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Cola: deque([3])\n", "¿La cola está vacía? False\n" ] } ], "source": [ "cola.popleft()\n", "print(f\"Cola: {cola}\")\n", "print(f\"¿La cola está vacía? {is_empty(cola)}\")" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "colab": { "autoexec": { "startup": false, "wait_interval": 0 }, "base_uri": "https://localhost:8080/", "height": 51, "output_extras": [ { "item_id": 1 } ] }, "colab_type": "code", "executionInfo": { "elapsed": 709, "status": "ok", "timestamp": 1520887960846, "user": { "displayName": "Jaime Castro Retamal", "photoUrl": "//lh5.googleusercontent.com/-d7ImDI1yYBM/AAAAAAAAAAI/AAAAAAAADF4/eQh4r_ES9eE/s50-c-k-no/photo.jpg", "userId": "114351437388776670979" }, "user_tz": 180 }, "id": "OHvB3nmC_ICu", "outputId": "7f6b9d42-e8eb-4706-d9dd-d7410dca5543" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Cola: deque([])\n", "¿La cola está vacía? True\n" ] } ], "source": [ "cola.popleft()\n", "print(f\"Cola: {cola}\")\n", "print(f\"¿La cola está vacía? {is_empty(cola)}\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Comparando `list` y `deque`\n", "\n", "En el siguiente código vamos a comparar el tiempo que demoran algunas operaciones en un `deque` y en un `list`. Vamos a crear un `deque` y un `list` de 10 millones de enteros cada uno, y luego vamos a comparar (1) el tiempo que toma encontrar el elemento que está en la mitad de cada uno, y (2) el tiempo que toma sacar 1000 elementos del inicio." ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "colab": { "autoexec": { "startup": false, "wait_interval": 0 }, "base_uri": "https://localhost:8080/", "height": 51, "output_extras": [ { "item_id": 1 } ] }, "colab_type": "code", "executionInfo": { "elapsed": 2116, "status": "ok", "timestamp": 1520896161287, "user": { "displayName": "Jaime Castro Retamal", "photoUrl": "//lh5.googleusercontent.com/-d7ImDI1yYBM/AAAAAAAAAAI/AAAAAAAADF4/eQh4r_ES9eE/s50-c-k-no/photo.jpg", "userId": "114351437388776670979" }, "user_tz": 180 }, "id": "PXm1mt3YZavn", "outputId": "98af06d3-f90c-418d-ff40-240e6374def5" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Buscar el elemento 5000000 en el deque se demoró 0.017002 segundos.\n", "Buscar el elemento 5000000 en la lista se demoró 0.000000 segundos.\n", "Ups, tu computador es demasiado rápido.\n", "\n", "Sacar los primeros 1000 elementos del deque se demoró 0.000999 segundos.\n", "Sacar los primeros 1000 elementos de la lista se demoró 17.158514 segundos.\n", "La extracción en list fue 17172.04 veces el tiempo de deque.\n", "\n" ] } ], "source": [ "from collections import deque\n", "from time import time\n", "\n", "\n", "ELEMENTS = 10_000_000\n", "\n", "# Creamos un deque y una lista con 10.000.000 de enteros\n", "number_deque = deque(range(ELEMENTS))\n", "number_list = list(range(ELEMENTS))\n", "\n", "# Vemos el time actual\n", "start_time = time()\n", "# Buscamos el elemento del medio\n", "number_deque[ELEMENTS // 2]\n", "finish_time = time()\n", "deque_time = finish_time - start_time\n", "# Imprimimos el tiempo transcurrido\n", "print(f\"\"\"Buscar el elemento {ELEMENTS // 2} en el deque se demoró \"\"\"\n", " f\"\"\"{deque_time:.6f} segundos.\"\"\")\n", "\n", "\n", "# Vemos el time actual\n", "start_time = time()\n", "# Buscamos el elemento del medio\n", "number_list[ELEMENTS // 2]\n", "finish_time = time()\n", "list_time = finish_time - start_time\n", "# Imprimimos el tiempo transcurrido\n", "print(f\"\"\"Buscar el elemento {ELEMENTS // 2} en la lista se demoró \"\"\"\n", " f\"\"\"{list_time:.6f} segundos.\"\"\")\n", "if list_time > 0.0:\n", " print(f\"La búsqueda en deque fue {deque_time/list_time:.2f} veces el tiempo de list.\")\n", "else:\n", " print(\"Ups, tu computador es demasiado rápido.\")\n", "print()\n", "\n", "# Vamos a hacer pop de los primeros 1000 elementos del deque\n", "start_time = time()\n", "N = 1000\n", "for i in range(0, N):\n", " number_deque.popleft()\n", "finish_time = time()\n", "deque_time = finish_time - start_time\n", "print(f\"Sacar los primeros {N} elementos del deque se demoró {deque_time:.6f} segundos.\")\n", "\n", "# Vamos a hacer pop de los primeros 1000 elementos de la lista\n", "start_time = time()\n", "N = 1000\n", "for i in range(0, N):\n", " number_list.pop(0)\n", "finish_time = time()\n", "list_time = finish_time - start_time\n", "print(f\"Sacar los primeros {N} elementos de la lista se demoró {list_time:.6f} segundos.\")\n", "if deque_time > 0.0:\n", " print(f\"La extracción en list fue {list_time/deque_time:.2f} veces el tiempo de deque.\")\n", "else:\n", " print(\"Ups, tu computador es demasiado rápido.\")\n", "print()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Nuestro experimento nos permite apreciar que (1) **acceder a un elemento de la mitad** de una cola implementada con `list` es mucho más rápido que con `deque`, y (2) **extraer un elemento del inicio** de una cola implementada con `deque` es mucho más rápido que con `list`. Es importante conocer estas diferencias al momento de elegir una estructura de datos adecuada para nuestros programas." ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "jS8OwLGScvyp" }, "source": [ "Se puede ver que con un *deque* es posible simular un *stack* o una cola como las que ya hemos visto. Esto pues un *deque* puede hacer todas las operaciones que requieren ambas estructuras con la misma eficiencia. Es por eso que se dice que esta estructura es una **generalización de los *stacks* y colas**." ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "KIbF_OHcP6oc" }, "source": [ "## Ejemplo de uso con palíndromos\n", "\n", "A continuación un ejemplo simple de chequeo de palabras palíndromas usando un *deque*. La palabra es almacenada en un *deque* y las letras de los extremos son extraídas simultáneamente comparadas hasta que quede una sola letra. El recorrido se hace de manera **recursiva**." ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "colab": { "autoexec": { "startup": false, "wait_interval": 0 }, "base_uri": "https://localhost:8080/", "height": 68, "output_extras": [ { "item_id": 1 } ] }, "colab_type": "code", "executionInfo": { "elapsed": 1426, "status": "ok", "timestamp": 1520895878616, "user": { "displayName": "Jaime Castro Retamal", "photoUrl": "//lh5.googleusercontent.com/-d7ImDI1yYBM/AAAAAAAAAAI/AAAAAAAADF4/eQh4r_ES9eE/s50-c-k-no/photo.jpg", "userId": "114351437388776670979" }, "user_tz": 180 }, "id": "JSicQvZlP6oc", "outputId": "c8fe1ca3-0f98-448f-a6f9-ee142d58c1d3" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "True\n", "False\n", "True\n", "False\n", "True\n" ] } ], "source": [ "from collections import deque\n", "\n", "\n", "def es_palindrome(palabra):\n", " cola = deque(palabra)\n", " return es_palindrome_rec(cola)\n", "\n", "\n", "def es_palindrome_rec(palabra):\n", " if len(palabra) <= 1:\n", " return True\n", " else:\n", " return palabra.popleft() == palabra.pop() \\\n", " and es_palindrome_rec(palabra)\n", "\n", "\n", "print(es_palindrome(\"reconocer\"))\n", "print(es_palindrome(\"espectaculo\"))\n", "print(es_palindrome(\"ana\"))\n", "print(es_palindrome(\"OssA\"))\n", "print(es_palindrome(\"OssO\"))" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "IEkGfLLtP6og" }, "source": [ "**Nota**: En Python lo más directo para chequear si un *string* es palíndromo es simplemente comparar `palabra == palabra[::-1]`" ] } ], "metadata": { "colab": { "collapsed_sections": [], "default_view": {}, "name": "02-pilas.ipynb", "provenance": [], "version": "0.3.2", "views": {} }, "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.12.9" } }, "nbformat": 4, "nbformat_minor": 4 }