Exercício_Prático_Pilha_Fila

Prévia do material em texto

UNIVERSIDADE FEDERAL DE OURO PRETO 
DEPARTAMENTO DE COMPUTAÇÃO E SISTEMAS 
ALGORITMOS E ESTRUTURAS DE DADOS I 
 
Atividade Prática de TAD 
Professor: Álvaro A. F. de Souza 
 
1- Considere uma Fila não vazia e uma pilha P inicialmente vazia. Usando apenas a variavel x e 
as 
seguintes operações: ​Empilha(P,x), Desempilha(P, x), Enfilera(F, x), 
x=Desenfileira(F), VazioPilha(P), VazioFila(F). 
escreva um algoritmo para reverter a ordem dos elementos da Fila. Por exemplo, se a 
Fila contiver os seguintes elementos 1 2 3 4 5 6 7, nessa ordem, o seu algoritmo 
devera inverter a ordem dos elementos deixando-os na seguinte ordem: 7 6 5 4 3 2 1. 
 
2- Usando uma pilha, escreva um programa que lê uma entrada de texto contendo os 
símbolos {, (, [, ],),} e determina se os parênteses, chaves e colchetes estão na 
quantidade corretamente. Por exemplo, seu programa devera imprimir que a entrada 
{([{()}])} está balanceada e que a entrada {(} não está balanceada. Dica: Para cada 
elemento da pilha use um caracter de chave, parênteses e colchetes. 
 
3- Escreva uma função para determinar se uma cadeia de caracteres ( string ) é da 
forma: ​xCy onde x e y são cadeias de caracteres compostas por letras ‘A’ e/ou ‘B ’, e y 
é o inverso de x . Isto é, se x = “ABABBA”, y deve equivaler a “ABBABA”. Em cada 
ponto, você só poderá ler o próximo caractere da cadeia (é mandatório o uso de pilha). 
 
4- Considere a implementação de filas usando arranjos “circulares”. Escreva uma 
função FuraFila(TipoFila * pFila, TipoItem x) que insere um item na primeira posição da 
fila. O detalhe é que seu procedimento deve ser O(1) , ou seja, não pode movimentar 
os outros itens da fila. (observe que este neste caso, estaremos desrespeitando o 
conceito de FILA – primeiro a entrar é o primeiro a sair). 
 
5- Considere a implementação de filas usando apontadores. Escreva uma função 
FuraFila(TipoFila * pFila, TipoItem x) que insere um item na primeira posição da fila. O 
detalhe é que seu procedimento deve ser O(1) , ou seja, não pode movimentar os 
outros itens da fila. (observe que este neste caso, estaremos desrespeitando o conceito 
de FILA – primeiro a entrar é o primeiro a sair). 
 
6- Uma Fila pode ser implementada usando-se duas pilhas. Implemente as operações 
de inserir e ​remover de uma la usando duas pilhas. 
 
7- Suponha uma sequência misturada de 10 operações que empilha em uma pilha 
e 10 operações de desempilhar. As operações de empilhar inserem valores de 0 a 9 
na pilha, nessa ordem. A operação de desempilhar retira e imprime na tela o valor 
desempilhado. Quais das sadas a seguir podem ocorrer? 
❏ 3 2 1 0 4 5 6 7 8 9 
❏ 0 5 6 7 9 8 4 3 2 1 
❏ 0 2 3 5 4 7 1 9 8 6 
❏ 1 2 0 6 5 4 7 9 3 8 
❏ 0 1 3 2 4 6 5 7 8 9