{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercício 01: Implementar em linguagem Python o pseudocódigo do algoritmo ``Fila`` visto em sala de aula."
   ],
   "id": "d78339f5"
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class FilaCircular:\n",
    "    def __init__(self, capacidade):\n",
    "        self.capacidade = capacidade\n",
    "        self.inicio = 0\n",
    "        self.fim = -1\n",
    "        self.quantidade = 0\n",
    "        self.valores = [0] * capacidade\n",
    "\n",
    "    def esta_vazia(self):\n",
    "        return self.quantidade == 0\n",
    "\n",
    "    def esta_cheia(self):\n",
    "        return self.quantidade == self.capacidade\n",
    "\n",
    "    def enfileirar(self, valor):\n",
    "        if self.esta_cheia():\n",
    "            return print(\"Fila cheia. Não é possível enfileirar.\")\n",
    "        self.fim = (self.fim + 1) % self.capacidade\n",
    "        self.valores[self.fim] = valor\n",
    "        self.quantidade += 1\n",
    "\n",
    "    def desenfileirar(self):\n",
    "        if self.esta_vazia():\n",
    "            return print(\"Fila vazia. Não é possível desenfileirar.\")\n",
    "        valor = self.valores[self.inicio]\n",
    "        self.inicio = (self.inicio + 1) % self.capacidade\n",
    "        self.quantidade -= 1\n",
    "        return valor\n",
    "\n",
    "    def frente(self):\n",
    "        if self.esta_vazia():\n",
    "            return print(\"Fila vazia.\")\n",
    "        return self.valores[self.inicio]\n",
    "\n",
    "    def imprimir(self):\n",
    "        for i in range(self.quantidade):\n",
    "            print(self.valores[(self.inicio + i) % self.capacidade], end=' | ')\n",
    "        print()"
   ],
   "id": "d2f806fb"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1. Teste o método ``esta_vazia()`` através do método ``desenfileirar()``;"
   ],
   "id": "fb0f635b"
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "Fila vazia. Não é possível desenfileirar.\n"
     ]
    }
   ],
   "source": [
    "fila = FilaCircular(9)\n",
    "\n",
    "print(fila.esta_vazia())\n",
    "fila.desenfileirar()"
   ],
   "id": "9abcc7ba"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2. Demonstre o enfileiramento de cada um dos caracteres que compõem o seu primeiro nome;"
   ],
   "id": "1ae65aff"
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "P | R | O | F | E | S | S | O | R | \n"
     ]
    }
   ],
   "source": [
    "for letra in \"PROFESSOR\":\n",
    "    fila.enfileirar(letra)\n",
    "\n",
    "fila.imprimir()"
   ],
   "id": "153da8be"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3. Teste o método ``esta_cheia()`` através do método ``enfileirar(valor)``;"
   ],
   "id": "ae98a216"
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "Fila cheia. Não é possível enfileirar.\n"
     ]
    }
   ],
   "source": [
    "print(fila.esta_cheia())\n",
    "fila.enfileirar('X')"
   ],
   "id": "0bf7891b"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4. Após executar as operações anteriores, demonstre qual elemento está na frente da fila;"
   ],
   "id": "44aed286"
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Elemento na frente: P\n"
     ]
    }
   ],
   "source": [
    "print(f\"Elemento na frente: {fila.frente()}\")"
   ],
   "id": "d4596153"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.5. Execute o método ``desenfileirar()`` por três vezes e verifique qual elemento está na frente da fila."
   ],
   "id": "3f822024"
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "P\n",
      "R\n",
      "O\n",
      "Elemento na frente: F\n"
     ]
    }
   ],
   "source": [
    "print(fila.desenfileirar())\n",
    "print(fila.desenfileirar())\n",
    "print(fila.desenfileirar())\n",
    "\n",
    "print(f\"Elemento na frente: {fila.frente()}\")"
   ],
   "id": "aadda9ee"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercício 02: Considere uma fila circular com capacidade igual a 5 elementos contendo em seu interior a sequência ``S, A``."
   ],
   "id": "6589f087"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1. Insira a sequência ``T, C`` na fila e demonstre esse procedimento;"
   ],
   "id": "84c17a5b"
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Fila inicial:\n",
      "S | A | \n",
      "Fila após enfileirar T e C:\n",
      "S | A | T | C | \n",
      "inicio: 0 | fim: 3 | quantidade: 4\n"
     ]
    }
   ],
   "source": [
    "exercicio2 = FilaCircular(5)\n",
    "\n",
    "exercicio2.enfileirar('S')\n",
    "exercicio2.enfileirar('A')\n",
    "\n",
    "print(\"Fila inicial:\")\n",
    "exercicio2.imprimir()\n",
    "\n",
    "exercicio2.enfileirar('T')\n",
    "exercicio2.enfileirar('C')\n",
    "\n",
    "print(\"Fila após enfileirar T e C:\")\n",
    "exercicio2.imprimir()\n",
    "\n",
    "print(f\"inicio: {exercicio2.inicio} | fim: {exercicio2.fim} | quantidade: {exercicio2.quantidade}\")"
   ],
   "id": "4f9c14af"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Estado da fila após a inserção de ``T, C``:\n",
    "\n",
    "| índice | 0 | 1 | 2 | 3 | 4 |\n",
    "|---|---|---|---|---|---|\n",
    "| ``valores`` | ``S`` | ``A`` | ``T`` | ``C`` | ``-`` |\n",
    "\n",
    "- ``inicio = 0`` (frente da fila, elemento ``S``);\n",
    "- ``fim = 3`` (último elemento inserido, ``C``);\n",
    "- ``quantidade = 4``."
   ],
   "id": "60b91394"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2. Qual o valor do atributo ``fim`` após a inserção da sequência descrita no item 1?"
   ],
   "id": "672ae96e"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "O valor do atributo ``fim`` é ``3``, pois ``T`` e ``C`` foram gravados nas posições ``2`` e ``3``."
   ],
   "id": "4cfc5158"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3. Se você fosse ``desenfileirar()`` um elemento da fila, qual seria esse elemento?"
   ],
   "id": "c66fa11f"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Seria o elemento ``S``, pois ``desenfileirar()`` sempre remove o elemento da **frente** da fila (o primeiro que entrou)."
   ],
   "id": "d77b6b24"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4. Desenfileirar dois elementos da fila e demonstrar esse procedimento;"
   ],
   "id": "6179b568"
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Removido: S\n",
      "Removido: A\n",
      "Fila após dois desenfileiramentos:\n",
      "T | C | \n",
      "inicio: 2 | fim: 3 | quantidade: 2\n"
     ]
    }
   ],
   "source": [
    "print(\"Removido:\", exercicio2.desenfileirar())\n",
    "print(\"Removido:\", exercicio2.desenfileirar())\n",
    "\n",
    "print(\"Fila após dois desenfileiramentos:\")\n",
    "exercicio2.imprimir()\n",
    "\n",
    "print(f\"inicio: {exercicio2.inicio} | fim: {exercicio2.fim} | quantidade: {exercicio2.quantidade}\")"
   ],
   "id": "beffa922"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Estado da fila após remover ``S`` e ``A``:\n",
    "\n",
    "| índice | 0 | 1 | 2 | 3 | 4 |\n",
    "|---|---|---|---|---|---|\n",
    "| ``valores`` | ``-`` | ``-`` | ``T`` | ``C`` | ``-`` |\n",
    "\n",
    "- ``inicio = 2`` (frente passou a ser ``T``);\n",
    "- ``fim = 3``;\n",
    "- ``quantidade = 2``."
   ],
   "id": "8e9b1c54"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.5. Considerando a fila resultante do item 4, insira um novo elemento e demonstre o comportamento circular da fila (quando o atributo ``fim`` retorna à posição ``0``)."
   ],
   "id": "fae627da"
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Após enfileirar D -> inicio: 2 | fim: 4 | quantidade: 3\n",
      "T | C | D | \n",
      "Após enfileirar E -> inicio: 2 | fim: 0 | quantidade: 4\n",
      "T | C | D | E | \n"
     ]
    }
   ],
   "source": [
    "exercicio2.enfileirar('D')\n",
    "print(f\"Após enfileirar D -> inicio: {exercicio2.inicio} | fim: {exercicio2.fim} | quantidade: {exercicio2.quantidade}\")\n",
    "exercicio2.imprimir()\n",
    "\n",
    "exercicio2.enfileirar('E')\n",
    "print(f\"Após enfileirar E -> inicio: {exercicio2.inicio} | fim: {exercicio2.fim} | quantidade: {exercicio2.quantidade}\")\n",
    "exercicio2.imprimir()"
   ],
   "id": "c1e112a8"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ao enfileirar ``D``, ``fim`` avança de ``3`` para ``4``. Ao enfileirar ``E``, ``fim = (4 + 1) % 5 = 0``, ou seja, **dá a volta** no vetor e reaproveita a posição ``0`` que havia sido liberada por ``S``. É exatamente esse comportamento que caracteriza a fila **circular**.\n",
    "\n",
    "| índice | 0 | 1 | 2 | 3 | 4 |\n",
    "|---|---|---|---|---|---|\n",
    "| ``valores`` | ``E`` | ``-`` | ``T`` | ``C`` | ``D`` |\n",
    "\n",
    "- ``inicio = 2``;\n",
    "- ``fim = 0``;\n",
    "- ``quantidade = 4``."
   ],
   "id": "efe8ee56"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercício 03\n",
    "\n",
    "1. Inserir (``enfileirar``) elementos em uma fila envolve gravar o valor na posição ``fim`` e avançar ``fim`` de forma circular: ``fim = (fim + 1) % capacidade``, além de incrementar ``quantidade``. É uma operação **O(1)**.\n",
    "2. Retirar (``desenfileirar``) elementos envolve ler o valor na posição ``inicio`` e avançar ``inicio`` de forma circular: ``inicio = (inicio + 1) % capacidade``, além de decrementar ``quantidade``. Também é **O(1)**.\n",
    "3. Uma fila está vazia quando ``quantidade == 0``.\n",
    "4. Uma fila está cheia quando ``quantidade == capacidade``.\n",
    "5. Quando a fila está vazia: ``inicio = 0``, ``fim = -1`` e ``quantidade = 0``.\n",
    "6. Quando a fila contém apenas um elemento: ``inicio = 0``, ``fim = 0`` e ``quantidade = 1``.\n",
    "7. Quando a fila está cheia: ``quantidade = capacidade`` e ``fim = (inicio + capacidade - 1) % capacidade``."
   ],
   "id": "ddc53dbc"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercício 04: Preencha a tabela abaixo com os nomes em inglês correspondentes aos nomes em português:\n",
    "\n",
    "| Nome em Português | Nome comum usado em Inglês |\n",
    "|---|---|\n",
    "| ``Fila`` | ``Queue`` |\n",
    "| ``enfileirar`` | ``enqueue`` |\n",
    "| ``desenfileirar`` | ``dequeue`` |\n",
    "| ``esta_vazia`` | ``is_empty`` / ``isEmpty`` |\n",
    "| ``esta_cheia`` | ``is_full`` / ``isFull`` |\n",
    "| ``frente`` | ``front`` / ``peek`` |\n",
    "| ``capacidade`` | ``capacity`` |"
   ],
   "id": "8b0898bc"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercício 05: Utilizando a classe ``FilaCircular`` implementada no Exercício 01, resolva os desafios abaixo:"
   ],
   "id": "f7832775"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.1. **Ordem de Atendimento**: receba uma sequência de clientes e utilize a Fila para atendê-los na ordem de chegada;"
   ],
   "id": "11282423"
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Atendendo: Ana\n",
      "Atendendo: Bruno\n",
      "Atendendo: Carla\n",
      "Atendendo: Diego\n"
     ]
    }
   ],
   "source": [
    "def atender(clientes):\n",
    "    fila = FilaCircular(len(clientes))\n",
    "    for cliente in clientes:\n",
    "        fila.enfileirar(cliente)\n",
    "\n",
    "    while not fila.esta_vazia():\n",
    "        print(f\"Atendendo: {fila.desenfileirar()}\")\n",
    "\n",
    "atender([\"Ana\", \"Bruno\", \"Carla\", \"Diego\"])"
   ],
   "id": "8a479ab4"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.2. **Inversão de Fila**: receba uma sequência de elementos e utilize uma Pilha auxiliar para exibir a fila invertida;"
   ],
   "id": "eec76920"
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 4, 3, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "class Pilha:\n",
    "    def __init__(self, capacidade):\n",
    "        self.capacidade = capacidade\n",
    "        self.topo = -1\n",
    "        self.valores = [0] * capacidade\n",
    "\n",
    "    def esta_vazia(self):\n",
    "        return self.topo == -1\n",
    "\n",
    "    def esta_cheia(self):\n",
    "        return self.topo == self.capacidade - 1\n",
    "\n",
    "    def empilhar(self, valor):\n",
    "        if self.esta_cheia():\n",
    "            return print(\"Pilha cheia. Não é possível empilhar.\")\n",
    "        self.topo += 1\n",
    "        self.valores[self.topo] = valor\n",
    "\n",
    "    def desempilhar(self):\n",
    "        if self.esta_vazia():\n",
    "            return print(\"Pilha vazia. Não é possível desempilhar.\")\n",
    "        valor = self.valores[self.topo]\n",
    "        self.topo -= 1\n",
    "        return valor\n",
    "\n",
    "\n",
    "def inverter_fila(valores):\n",
    "    fila = FilaCircular(len(valores))\n",
    "    for valor in valores:\n",
    "        fila.enfileirar(valor)\n",
    "\n",
    "    pilha = Pilha(len(valores))\n",
    "    while not fila.esta_vazia():\n",
    "        pilha.empilhar(fila.desenfileirar())\n",
    "\n",
    "    invertida = []\n",
    "    while not pilha.esta_vazia():\n",
    "        invertida.append(pilha.desempilhar())\n",
    "    return invertida\n",
    "\n",
    "print(inverter_fila([1, 2, 3, 4, 5]))"
   ],
   "id": "88e32f2c"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.3. **Intercalação de Filas**: receba duas filas e utilize uma terceira Fila para intercalar seus elementos alternadamente (se uma fila terminar antes, os elementos restantes da outra vão ao final);"
   ],
   "id": "dd7c61dd"
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6]\n",
      "[1, 2, 3, 4, 6]\n"
     ]
    }
   ],
   "source": [
    "def intercalar(fila1, fila2):\n",
    "    resultado = FilaCircular(len(fila1) + len(fila2))\n",
    "\n",
    "    i = 0\n",
    "    j = 0\n",
    "    while i < len(fila1) or j < len(fila2):\n",
    "        if i < len(fila1):\n",
    "            resultado.enfileirar(fila1[i])\n",
    "            i += 1\n",
    "        if j < len(fila2):\n",
    "            resultado.enfileirar(fila2[j])\n",
    "            j += 1\n",
    "\n",
    "    saida = []\n",
    "    while not resultado.esta_vazia():\n",
    "        saida.append(resultado.desenfileirar())\n",
    "    return saida\n",
    "\n",
    "print(intercalar([1, 3, 5], [2, 4, 6]))\n",
    "print(intercalar([1, 3], [2, 4, 6]))"
   ],
   "id": "35d1d95f"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Resumo\n",
    "\n",
    "- A fila segue o princípio **FIFO**: o primeiro a entrar é o primeiro a sair.\n",
    "- ``enfileirar`` ocorre no ``fim`` e ``desenfileirar`` ocorre no ``inicio``.\n",
    "- O operador módulo (``%``) torna a fila **circular**, reaproveitando posições livres.\n",
    "- Usamos ``inicio``, ``fim`` e ``quantidade`` para controlar os estados de vazia/cheia.\n",
    "- Enfileirar e desenfileirar são operações **O(1)**."
   ],
   "id": "bd9ddbb3"
  }
 ],
 "metadata": {
  "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.13.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}