{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e374e00d",
   "metadata": {},
   "source": [
    "## Filas em Python\n",
    "\n",
    "Neste notebook vamos implementar uma **Fila Circular** (queue): uma estrutura de dados do tipo **FIFO** (*First In, First Out*), em que o **primeiro** elemento inserido é o **primeiro** a ser removido.\n",
    "\n",
    "Usamos um vetor de **capacidade fixa** e três controles: `inicio` (frente da fila), `fim` (último elemento) e `quantidade`. O avanço de `inicio` e `fim` usa o operador módulo (`%`), fazendo a fila \"dar a volta\" no vetor — por isso ela é **circular**.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "acc2b8c5",
   "metadata": {},
   "source": [
    "### A classe `FilaCircular`\n",
    "\n",
    "Os principais métodos são:\n",
    "\n",
    "- `esta_vazia()`: retorna `True` quando `quantidade == 0`;\n",
    "- `esta_cheia()`: retorna `True` quando `quantidade == capacidade`;\n",
    "- `enfileirar(valor)`: insere o valor no final da fila;\n",
    "- `desenfileirar()`: remove e retorna o elemento da frente;\n",
    "- `frente()`: retorna o elemento da frente **sem** removê-lo;\n",
    "- `imprimir()`: mostra os elementos da frente até o final.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "e525f088",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:09:06.674497Z",
     "iopub.status.busy": "2026-09-28T17:09:06.674330Z",
     "iopub.status.idle": "2026-09-28T17:09:06.684279Z",
     "shell.execute_reply": "2026-09-28T17:09:06.683501Z"
    }
   },
   "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()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "330b51a2",
   "metadata": {},
   "source": [
    "### Testando a fila vazia\n",
    "\n",
    "Criamos uma fila com capacidade 5 e tentamos desenfileirar antes de inserir qualquer coisa. O método `desenfileirar()` deve avisar que a fila está vazia.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "7cd2dd25",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:09:06.687572Z",
     "iopub.status.busy": "2026-09-28T17:09:06.687245Z",
     "iopub.status.idle": "2026-09-28T17:09:06.692339Z",
     "shell.execute_reply": "2026-09-28T17:09:06.691621Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A fila está vazia? True\n",
      "Fila vazia. Não é possível desenfileirar.\n"
     ]
    }
   ],
   "source": [
    "fila = FilaCircular(5)\n",
    "print(\"A fila está vazia?\", fila.esta_vazia())\n",
    "fila.desenfileirar()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99103c0c",
   "metadata": {},
   "source": [
    "### Enfileirando os caracteres do nome\n",
    "\n",
    "Enfileiramos as letras de `RAMON` uma a uma. Repare que a frente é sempre a **primeira** letra inserida.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "1a12d9b6",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:09:06.695296Z",
     "iopub.status.busy": "2026-09-28T17:09:06.695137Z",
     "iopub.status.idle": "2026-09-28T17:09:06.699847Z",
     "shell.execute_reply": "2026-09-28T17:09:06.699020Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enfileirou R | frente: R\n",
      "R | \n",
      "Enfileirou A | frente: R\n",
      "R | A | \n",
      "Enfileirou M | frente: R\n",
      "R | A | M | \n",
      "Enfileirou O | frente: R\n",
      "R | A | M | O | \n",
      "Enfileirou N | frente: R\n",
      "R | A | M | O | N | \n"
     ]
    }
   ],
   "source": [
    "for letra in \"RAMON\":\n",
    "    fila.enfileirar(letra)\n",
    "    print(f\"Enfileirou {letra} | frente: {fila.frente()}\")\n",
    "    fila.imprimir()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a590d4b2",
   "metadata": {},
   "source": [
    "### Verificando se a fila está cheia\n",
    "\n",
    "A capacidade é 5 e já inserimos 5 letras. Uma nova inserção deve ser recusada.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "c5fb3708",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:09:06.702437Z",
     "iopub.status.busy": "2026-09-28T17:09:06.702099Z",
     "iopub.status.idle": "2026-09-28T17:09:06.706371Z",
     "shell.execute_reply": "2026-09-28T17:09:06.705443Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A fila está cheia? True\n",
      "Fila cheia. Não é possível enfileirar.\n"
     ]
    }
   ],
   "source": [
    "print(\"A fila está cheia?\", fila.esta_cheia())\n",
    "fila.enfileirar(\"X\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "41e3341d",
   "metadata": {},
   "source": [
    "### Consultando a frente\n",
    "\n",
    "O método `frente()` retorna o elemento da frente sem removê-lo. Como o primeiro valor enfileirado foi `R`, ele deve ser retornado.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "c27ce2b3",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:09:06.709140Z",
     "iopub.status.busy": "2026-09-28T17:09:06.708961Z",
     "iopub.status.idle": "2026-09-28T17:09:06.713111Z",
     "shell.execute_reply": "2026-09-28T17:09:06.712467Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Elemento na frente: R\n"
     ]
    }
   ],
   "source": [
    "print(\"Elemento na frente:\", fila.frente())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4453a5a4",
   "metadata": {},
   "source": [
    "### Desenfileirando elementos\n",
    "\n",
    "Cada `desenfileirar()` remove o elemento da frente. Após três remoções, saíram `R`, `A` e `M`, e a frente passa a ser `O`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "0a4c9094",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:09:06.715655Z",
     "iopub.status.busy": "2026-09-28T17:09:06.715456Z",
     "iopub.status.idle": "2026-09-28T17:09:06.720742Z",
     "shell.execute_reply": "2026-09-28T17:09:06.719572Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Removido: R\n",
      "Removido: A\n",
      "Removido: M\n",
      "Elemento na frente: O\n",
      "O | N | \n"
     ]
    }
   ],
   "source": [
    "print(\"Removido:\", fila.desenfileirar())\n",
    "print(\"Removido:\", fila.desenfileirar())\n",
    "print(\"Removido:\", fila.desenfileirar())\n",
    "\n",
    "print(\"Elemento na frente:\", fila.frente())\n",
    "fila.imprimir()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8afefcb8",
   "metadata": {},
   "source": [
    "### Comportamento circular\n",
    "\n",
    "Após as remoções, restam `O` e `N`. Ao enfileirar novos valores, o atributo `fim` **dá a volta** no vetor (de `4` para `0`), reaproveitando o espaço liberado no início. Esse é o comportamento **circular** da fila.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "85fa92d9",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-09-28T17:09:06.723420Z",
     "iopub.status.busy": "2026-09-28T17:09:06.723195Z",
     "iopub.status.idle": "2026-09-28T17:09:06.727112Z",
     "shell.execute_reply": "2026-09-28T17:09:06.726164Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enfileirou 1 | inicio: 3 | fim: 0\n",
      "O | N | 1 | \n",
      "Enfileirou 2 | inicio: 3 | fim: 1\n",
      "O | N | 1 | 2 | \n",
      "Enfileirou 3 | inicio: 3 | fim: 2\n",
      "O | N | 1 | 2 | 3 | \n",
      "A fila está cheia? True\n"
     ]
    }
   ],
   "source": [
    "for valor in [1, 2, 3]:\n",
    "    fila.enfileirar(valor)\n",
    "    print(f\"Enfileirou {valor} | inicio: {fila.inicio} | fim: {fila.fim}\")\n",
    "    fila.imprimir()\n",
    "\n",
    "print(\"A fila está cheia?\", fila.esta_cheia())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b183bc8",
   "metadata": {},
   "source": [
    "### Resumo\n",
    "\n",
    "- A fila segue o princípio **FIFO**: o primeiro a entrar é o primeiro a sair.\n",
    "- Sua **capacidade é fixa** e usamos `inicio`, `fim` e `quantidade` para controlá-la.\n",
    "- O operador módulo (`%`) faz a fila ser **circular**, reaproveitando posições livres.\n",
    "- Só é possível acessar e remover o elemento da **frente**.\n",
    "- Enfileirar e desenfileirar são operações **O(1)**.\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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
}