Aplicações Informáticas B · 12.º Ano · Algoritmia e Estruturas de Dados · 1o Periodo

Estruturas de Dados Avançadas: Pilhas e Filas

Os alunos exploram as estruturas de dados de pilha (LIFO) e fila (FIFO) e as suas aplicações práticas.

• Aprendizagens Essenciais
• DGE: Secundário - Algoritmia e Programação
• DGE: Secundário - Dados e Análise

Sobre este tópico

As estruturas de dados pilha e fila são fundamentais no pensamento computacional avançado. A pilha opera pelo princípio LIFO (Last In, First Out), onde o último elemento inserido é o primeiro removido, como uma pilha de pratos. A fila segue o FIFO (First In, First Out), semelhante a uma fila de supermercado, com inserções no fim e remoções no início. Os alunos do 12.º ano exploram operações como push, pop, enqueue e dequeue, comparando o seu comportamento em cenários variados.

No currículo nacional, este tema integra-se na unit Algoritmia e Estruturas de Dados, alinhando-se com os standards DGE para Algoritmia e Programação e Dados e Análise. Os alunos analisam como a escolha entre pilha e fila otimiza a gestão de tarefas em sistemas operativos, como o undo em editores de texto ou a impressão em filas de spool. Compreender estas estruturas prepara para o desenvolvimento de compiladores e simuladores, fomentando competências em otimização e modelação de problemas reais.

O ensino ativo beneficia particularmente este tópico porque as simulações físicas e implementações em pseudocódigo tornam conceitos abstractos concretos. Quando os alunos manipulam objectos reais ou codificam exemplos colaborativos, internalizam diferenças operacionais e aplicações, melhorando a retenção e a capacidade de aplicação em contextos complexos.

Questões-Chave

1. Compare as operações e o comportamento de pilhas e filas em diferentes cenários.
2. Analise como a escolha entre pilha e fila pode otimizar a gestão de tarefas em sistemas operativos.
3. Explique a importância de compreender estas estruturas para o desenvolvimento de compiladores e simuladores.

Objetivos de Aprendizagem

• Comparar as operações de inserção e remoção em pilhas (push/pop) e filas (enqueue/dequeue) através de simulações.
• Analisar a aplicabilidade de pilhas e filas na resolução de problemas computacionais específicos, como a gestão de chamadas de função ou o processamento de pedidos.
• Avaliar a eficiência de cada estrutura de dados em cenários de acesso sequencial e em profundidade.
• Explicar como a ordem de processamento (LIFO vs. FIFO) afeta o resultado de algoritmos que utilizam pilhas ou filas.
• Implementar as operações básicas de uma pilha e de uma fila utilizando arrays ou listas ligadas em pseudocódigo.

Antes de Começar

Conceitos Fundamentais de Algoritmos

Porquê: Os alunos precisam de uma base sólida em algoritmos para compreender como as estruturas de dados são utilizadas para resolver problemas.

Tipos de Dados Abstratos (TDA)

Porquê: A compreensão de TDAs é essencial para distinguir entre a interface de uma estrutura de dados (operações) e a sua implementação.

Estruturas de Dados Básicas (Arrays e Listas Ligadas)

Porquê: O conhecimento sobre como implementar pilhas e filas requer familiaridade com as estruturas de dados subjacentes.

Vocabulário-Chave

Pilha (Stack)	Estrutura de dados linear que segue o princípio LIFO (Last In, First Out). O último elemento adicionado é o primeiro a ser removido.
Fila (Queue)	Estrutura de dados linear que segue o princípio FIFO (First In, First Out). O primeiro elemento adicionado é o primeiro a ser removido.
Push	Operação para adicionar um elemento ao topo de uma pilha.
Pop	Operação para remover e retornar o elemento do topo de uma pilha.
Enqueue	Operação para adicionar um elemento ao fim de uma fila.
Dequeue	Operação para remover e retornar o elemento do início de uma fila.

Atenção a estes erros comuns

Erro comum

Pilha e fila são intercambiáveis em todos os cenários.

O que ensinar em alternativa

Pilhas usam LIFO para reversão de acções, como undo; filas usam FIFO para processamento sequencial, como tarefas em SO. Discussões em grupo com simulações físicas ajudam os alunos a visualizar diferenças e escolher a estrutura correcta.

Erro comum

Estas estruturas só servem para armazenamento de memória.

O que ensinar em alternativa

Aplicam-se em compiladores (pilhas para expressões) e simuladores (filas para eventos). Actividades colaborativas com cenários reais revelam optimizações, corrigindo visões limitadas através de debate e testes práticos.

Erro comum

As operações push/pop são mais eficientes que enqueue/dequeue.

O que ensinar em alternativa

Ambas têm complexidade O(1) em implementações adequadas. Experiências hands-on com temporizadores mostram equivalência, fomentando análise rigorosa em vez de suposições.

Ideias de aprendizagem ativa

Simulação Física: Pilha vs Fila

Distribua cartões numerados aos alunos. Para a pilha, empilhem e retirem do topo; para a fila, adicionem ao fim e retirem da frente. Registem a ordem de remoção em folhas de registo e comparem resultados em grupo.

30 min·Pequenos grupos

Pseudocódigo Colaborativo: Operações Básicas

Em pares, escrevam pseudocódigo para push/pop numa pilha e enqueue/dequeue numa fila. Testem com sequências de 5 elementos e depurem erros comuns como overflow.

25 min·Pares

Análise de Cenários: Sistemas Operativos

Apresente casos como gestão de impressoras (fila) ou histórico de navegação (pilha). Grupos discutem e justificam a estrutura adequada, depois partilham com a turma.

35 min·Pequenos grupos

Implementação Individual: Mini-Projeto

Cada aluno codifica uma pilha ou fila simples em Python ou pseudocódigo, testando com inputs variados. Submetam para revisão rápida em plenário.

40 min·Individual

Ligações ao Mundo Real

• Em sistemas operativos, as filas são usadas para gerir tarefas de impressão (spooling), onde os trabalhos são processados pela ordem em que chegam. As pilhas são cruciais para gerir o histórico de navegação ou a funcionalidade 'desfazer' em aplicações como editores de texto.
• Compiladores utilizam pilhas para analisar a sintaxe de expressões matemáticas e para gerir chamadas de funções recursivas. Simuladores de sistemas, como os usados em engenharia aeroespacial para modelar o tráfego aéreo, empregam filas para sequenciar eventos e processar informações de forma ordenada.

Ideias de Avaliação

Bilhete de Saída

Entregue a cada aluno um pequeno cartão com um cenário (ex: 'processamento de chamadas telefónicas', 'navegação em páginas web'). Peça-lhes para identificarem se uma pilha ou fila seria mais apropriada e justificarem a escolha em 1-2 frases, mencionando as operações chave.

Verificação Rápida

Apresente um pequeno trecho de pseudocódigo que implementa operações de pilha ou fila. Pergunte aos alunos: 'Qual o valor final desta variável após a execução destas linhas?' ou 'Qual o próximo elemento a ser removido?'. Verifique as respostas rapidamente para identificar dificuldades.

Questão para Discussão

Coloque a seguinte questão para discussão em pequenos grupos: 'Como é que a escolha entre uma pilha e uma fila pode impactar a performance de um sistema de gestão de tarefas em tempo real?'. Peça a cada grupo para apresentar as suas conclusões, focando nas implicações de LIFO vs. FIFO.

Perguntas frequentes

Qual a diferença entre pilha e fila?

A pilha segue LIFO: o último elemento inserido sai primeiro, ideal para reversões como histórico de navegação. A fila segue FIFO: o primeiro entra, primeiro sai, perfeita para filas de tarefas como impressão. Ambas usam operações O(1), mas a escolha depende do cenário, promovendo optimização algorítmica.

Como pilhas e filas se aplicam em sistemas operativos?

Pilhas gerem chamadas de funções e interrupções (LIFO para retorno). Filas processam tarefas em scheduler ou dispositivos I/O (FIFO para ordem). Analisar estes casos ajuda alunos a ligar teoria a software real, como no Linux kernel.

Como o ensino activo ajuda a compreender pilhas e filas?

Simulações físicas com objectos reais e implementações colaborativas em pseudocódigo tornam LIFO/FIFO tangíveis. Alunos testam operações em grupo, depuram erros e debatem aplicações, melhorando retenção em 30-50% face a aulas expositivas. Esta abordagem desenvolve pensamento computacional prático.

Porquê estudar estas estruturas para compiladores?

Pilhas parseiam expressões matemáticas (shunting-yard algorithm) e gerem recursão. Filas simulam fluxos de tokens. Compreender optimiza parsing e avaliação, essencial para programação avançada e preparação para exames nacionais.