Pilhas são as mais simples de todas as estruturas de dados, ...

Pilhas são as mais simples de todas as estruturas de dados, apesar de estar entre uma das mais importantes, na medida em que são usadas em uma gama de aplicações diferentes que incluem estruturas de dados muito mais sofisticadas. Uma pilha é uma coleção de objetos que são inseridos e retirados de acordo com o princípio de que “o último que entra é o primeiro que sai”.

Formalmente, uma pilha é um tipo abstrato de dados que suporta os seguintes métodos:

push(e) -> insere o objeto (e) no topo da pilha;

pop() -> remove o elemento que está no topo da

pilha e o retorna. Se a pilha estiver vazia retorna

um erro;

size( ) -> retorna o número de elementos da

pilha;

isEmpty( ) -> retorna um booleano indicando se

a pilha está vazia;

top() -> retorna o elemento que está no topo da

pilha sem retirá-lo. Se a pilha estiver vazia

retorna um erro.

Outra estrutura de dados fundamental é a fila. Ela é uma prima próxima da pilha, pois uma fila é uma coleção de objetos que são inseridos e removidos de acordo com o princípio de que “o primeiro que entra é o primeiro que sai”.

De maneira análoga à pilha, a fila também é um tipo abstrato de dados e suporta os seguintes métodos:

enqueue(e) -> insere o elemento (e) no fim da

fila;

dequeue() -> retira o elemento da frente da fila e

o retorna. Se a fila estiver vazia retorna um erro;

size() -> retorna o número de elementos na fila;

isEmpty() -> retorna um booleano indicando se

a fila está vazia;

front() -> retorna, mas não remove, o elemento

que está na frente da fila. Se a fila estiver vazia

retorna um erro;

(GOODRICH, M. T., Estruturas de Dados e Algoritmos em Java, 4 ed., Porto Alegre: Bookman, 2007, com adaptações).

As duas tabelas a seguir apresentam operações com pilhas e filas sendo executadas.

A primeira mostra uma série de operações de pilha e seus efeitos sobre uma pilha de números inteiros inicialmente vazia.

A segunda tabela mostra uma série de operações e seus efeitos sobre uma fila de números inteiros inicialmente vazia.

As operações são executadas na mesma ordem das linhas, ou seja, a operação da linha 02 foi executada depois da operação da linha 01, a operação da linha 03 foi executada depois da operação da linha 02 e assim sucessivamente até a linha final da tabela, que mostra a última operação executada.

Selecione, dentre as alternativas disponíveis, aquela que substitui corretamente os termos {?} em cada tabela, nas linhas indicadas. Atente-se para o fato de que existe três {?} em cada tabela.