Tipos e Estruturas de Dados

Lista de Exercícios - 3  (PILHAS E FILAS e Listas Circulares)

1) Seja a expressão (2+5) * (7-4)

 - Passe a expressao para a notacao Polonesa reversa
 - indique passo a passo como a expressao é executada por meio de uma pilha

2) Escreva a função char *Infixa2Posfixa(char *infixa) que toma a expressão 
    no formato infixo "infixa" e transforma para notacao posfixa
   considere expressoes com parenteses e os operadores binarios +, -, / e *,
   alem do operador de potencia ^



3) Escreva um TAD pilha ESTATICO e implemente as funcoes PUSH, POP,
   PilhaVazia, PilhaCheia, TamanhoPilha...

4) repita o exercicio 3, considerando agora uma pilha dinamica

5) Retome as funcoes InsereLista (Elem x, posicao p, Lista *l)
   e as demais: Localiza, busca, Retira(Posicao p, Lista *l)

   - utilizando esse TAD, mostre a implementacao das funcoes PUSH e
     POP .
   - Discuta as vantagens e desvantagens com relacao a implementacao
     dinamica da pilha do exercicio 4



6) Implementar o TAD para uma fila circular em um vetor
	- Estrutura de dados
        - Funcoes: Insere, Retira, FilaCheia, FilaVAzia, TamanhoFila()

7) Idem exercicio 1, só que para uma estrutura dinâmica

8) Utilizando as rotinas de listas generica que implementamos no 
   inicio do curso, mostre como seria o seu TAD Fila, utilizando-se
   destas funções.

9) SUponha uma fila estática NAO circular. Suponha que a fila possua
  dois ponteiros: inicio e fim, que vao se movendo em direcao ao final
do vetor à medida que insercoes e retiradas sao feitas. Quando o ponteiro
fim chegar ao final do vetor, todos os elementos devem ser deslocados 
para o inicio do vetor. Implemente essa fila.

10) Seja uma fila circular estática. Reimplemente o TAD usando a seguinte
estratégia para indicar fila cheia: mantenha uma posicao vazia no vetor, de
forma que fila cheia signifique que o ponteiro fim está DUAS posicoes antes 
do inicio. 

11) Uma estrutura DEQUE é uma especie de lista em que  elementos podem ser inseridos
e retirados de ambas extremidades da estrutura (estática ou dinâmica) APENAS. Outros
tipos de insercao e remocao (em outras posicoes) nao sao válidas.
Podemos entao dizer que um deque é uma generalizacao de uma fila e pilha ao mesmo
tempo.

	- Escreva as funcoes para implementar um deque em um vetor linear.
	- Idem acima, só que para um vetor circular
	- NA sua opinião, é mais apropriado implementar um deque num vetor
		linear ou circular? Por que?