Slide aula 10

Prévia do material em texto

2019.2
ESTUTURAS DE DADOS
CCT0637
Aula 10
PROFESSOR: EDIBERTO MARIANO
1
2019.2
CONTEÚDOS
2
Listas Lineares 
Sequenciais e Encadeadas 
(Parte III)
Pilha
2019.2 3
As pilhas são listas onde o primeiro elemento a ser inserido é
sempre o último a ser removido. Por isso as pilhas são muitas vezes
chamadas de LIFO (Last In First Out).
Pilha
Definição – já visto antes
2019.2 4
Representação
Pilha
As operações de inclusão e remoção – já 
visto antes
Por exemplo, se os números 3 5 7 2 e 8 forem inseridos em uma pilha nesta 
ordem, então eles deverão ser removidos na ordem: 8 2 7 5 e 3.
2019.2 5
Pilhas também podem ser estáticas ou dinâmicas.
Pilha
Como no caso das listas:
As implementações estáticas de pilhas normalmente
fazem uso de arrays.
As implementações dinâmicas utilizam ponteiros.
2019.2 6
Pilha
Implementação (Estática)
Uma das formas mais simples de se implementar uma
pilha é utilizando array. No exemplo a seguir, os
elementos armazenados serão números inteiros.
A principal vantagem em se utilizar implementação
estática de pilhas é a simplicidade da
implementação.
2019.2 7
Pilha
Implementação (Estática)
Especificação:
PLH *Inicia_Pilha(int N)
o Cria uma nova estrutura de pilha com tamanho máximo N.
PUSH(PLH *P, int A)
o Insere um novo elemento A no topo da pilha P
int POP(PLH *p)
o Retira o elemento do topo da pilha P retornando seu valor
int SIZE(PLH *p)
o retorna o valor correspondente a quantidade de elementos
armazenados na Pilha
int IS_EMPTY(PLH *p)
o retorna o valor 1 se a Pilha estiver vazia e 0, caso
contrário.
2019.2 8
Pilha
Implementação (Estática)
Sintaxe:
typedef struct Pilha PLH;
struct No_Pilha
{
int top ;
int max ; /* Armazena o tamanho máximo da pilha */
int *elem;
};
2019.2 9
Pilha
Implementação (Estática)
Sintaxe:
void PUSH(PLH *P, int A)
{
if (P->top < P->max - 1)
P->elem[++(P->top)] = A;
else
cout << "Pilha Cheia" << endl;
}
2019.2 10
Pilha
Implementação (Estática) - Exemplo
#include <stdio.h>
#include <stdlib.h> 
#include <iostream>
#include <conio.h>
using namespace std;
#define max 3 
int dado[max]; 
int topo=0; 
int op; 
void exibir(void) {
printf("\n");
for(int temp=topo-1; temp >= 0; temp--) {
printf("\tNa posicao %d temos %d\n", temp, dado[temp]);
}
printf("\n");
getch();
}
2019.2 11
Pilha
Implementação (Estática) - Exemplo
void inserir(void) {
if(topo==max) {
cout<<"\tA pilha esta cheia, Overflow\n";
getch();
}
else {
printf("\tInforme o valor a ser inserido na pilha : ");
scanf("\t%d", &dado[topo]);
topo++;
exibir();
}
} 
2019.2 12
Pilha
Implementação (Estática) - Exemplo
void remover(void){ 
if(topo == 0) {
cout<<"\tA pilha esta vazia \n";
}
else {
printf("\t\nRetirado o valor %d da pilha\n", dado[topo-1]);
topo--;
}
exibir();
} 
2019.2 13
Pilha
Implementação (Estática) - Exemplo
int menu() {
cout<<"\tPrograma Pilha em C \n\n";
cout<<"\tPara Inserir digite----------- : 1\n";
cout<<"\tPara Remover digite------- : 2\n";
cout<<"\tPara Exibir digite------------ : 3\n";
cout<<"\tPara Sair digite-------------- : 4 \t\tInforme uma opcao = ";
scanf("%d", &op);
switch (op) {
case 1 : 
inserir();
break;
case 2 : 
remover();
break;
case 3 : 
exibir();
break;
}
return 0;
}
2019.2 14
Pilha
Implementação (Estática) - Exemplo
int main() { 
while(op!=4) {
system("cls");
menu();
}
return 0;
}
Resultado
2019.2 15
Pilha
Implementação (Dinâmica)
A implementação dinâmica de pilhas possui as
mesmas vantagens que as listas dinâmicas, ou seja,
não é necessário saber a quantidade máxima de
elementos que serão armazenados.
A especificação é idêntica a que foi feita no caso
estático.
2019.2 16
Pilha
Implementação (Dinâmica)
Sintaxe:
typedef struct Pilha PLH;
typedef struct No_pilha NO ;
struct No_pilha
{
int elem;
NO *prox;
}
struct Pilha
{
NO *top;
}
2019.2 17
Pilha
Implementação (Dinâmica)
Sintaxe:
struct Pilha
{
NO *top;
}
2019.2 18
Pilha
Implementação (Dinâmica) - Exemplo
#include <stdio.h>
#include <stdlib.h>
typedef struct elemento {
int dado;
struct elemento *proximo;
}t_elemento;
typedef struct pilha {
t_elemento *primeiro;
t_elemento *ultimo;
}t_pilha;
t_pilha* criaPilha() {
t_pilha *pilha = 
(t_pilha*)malloc(sizeof(t_pilha));
pilha->primeiro = NULL;
pilha->ultimo = NULL;
return pilha;
}
2019.2 19
Pilha
Implementação (Dinâmica) - Exemplo
void empilhar(char valor, t_pilha *pilha) {
t_elemento *novo = (t_elemento*)malloc(sizeof(t_elemento));
novo->dado = valor;
novo->proximo = NULL;
if(pilha->primeiro == NULL) { //Se a lista estiver vazia
pilha->primeiro = novo;
}
else {
novo->proximo = pilha->primeiro;
pilha->primeiro = novo; /*pilha->primeiro aponta para o novo, e
novo passa a ser o primeiro elemento da pilha*/
}
}
2019.2 20
Pilha
Implementação (Dinâmica) - Exemplo
int desempilha(t_pilha *pilha) {
int primer = pilha->primeiro->dado;
t_elemento *removido;
removido = pilha->primeiro;
pilha->primeiro = pilha->primeiro->proximo; /*pilha->primeiro aponta
para o meu proximo Primeiro elemento (topo da pilha) passa a
ser o meu proximo elemento (que estava de baixo).*/
free(removido); /*Remove o ex-topo da pilha.*/
if(pilha->primeiro == NULL) {
pilha->ultimo = NULL;
}
return primer; /*Retorna o elemento que foi removido da pilha, ou seja,
o ex-topo da pilha*/
}
2019.2 21
Pilha
Implementação (Dinâmica) - Exemplo
void Destruir(int t, t_pilha *pilha) {
while(t--) {
t_elemento *removido;
removido = pilha->primeiro;
pilha->primeiro = pilha->primeiro->proximo;
free(removido);
}
if(pilha->primeiro == NULL) {
pilha->ultimo = NULL;
}
}
2019.2 22
Pilha
Implementação (Dinâmica) - Exemplo
int esta_vazia(t_pilha *pilha) { /*Verifica se o topo da pilha esta vazio, caso 
sim, a pilha esta vazia*/
if(pilha->primeiro == NULL) {
printf("Pilha esta fazia!\n");
return 1;
}else {
return 0;
}
}
int tamanho_pilha(t_pilha *pilha) { /*Tanto faz passar o endereço ou uma 
copia da pilha*/
t_elemento *aux = pilha->primeiro;
int tamanho = 0;
while(aux != NULL) {
aux = aux->proximo; //Vai &quot;andando&quot; pela pilha
tamanho++;
}
return tamanho;
}
2019.2 23
Pilha
Implementação (Dinâmica) - Exemplo
void imprimir(t_pilha *pilha){
t_elemento *atual = pilha->primeiro;
while(atual != NULL){
printf(" %d",atual->dado);
atual = atual->proximo;
}
printf("\nFIM DA PILHA\n");
}
void menu() {
printf("PILHA DINAMICA\n");
printf("\n1 - Inserir\n");
printf("2 - Remover\n");
printf("3 - Imprimir\n");
printf("4 - Tamanho\n");
printf("5 - Destruir\n");
printf("0 - Sair\n");
}
2019.2 24
Pilha
Implementação (Dinâmica) - Exemplo
int main(void) {
int opcao = 1, quantidade, elemento; t_pilha *pilha = criaPilha();
while(1) {
menu();
printf("\nDigite a opcao: "); scanf("%d", &opcao);
if(opcao == 0){
quantidade = tamanho_pilha(pilha);
Destruir(quantidade, pilha);
printf("\nPROGRAMA ENCERRADO - FIM!\n");
break;
}
else
if(opcao == 1) {
printf("\nQuantidade de elemento(s): ");
scanf("%d&", &quantidade);
while(quantidade--) {
printf("\nDigite o elemento: ");
scanf("%d&", &elemento);
empilhar(elemento, pilha);
}
}
2019.2 25
Pilha
Implementação (Dinâmica) - Exemplo
else 
if(opcao == 2) {
printf("Removendo...\n");
printf("\nElemento removido: \n", desempilha(pilha));
}
else 
if(opcao == 3) {
printf("Pilha : ");
imprimir(pilha);
} else if(opcao == 4) {
if(esta_vazia(pilha) == 0) {
printf("\nTamanho da pilha: %d\n", tamanho_pilha(pilha));
}
}
else 
if(opcao == 5) {
quantidade = tamanho_pilha(pilha);
Destruir(quantidade, pilha);
esta_vazia(pilha);
}
}
2019.2 26
Pilha
Implementação (Dinâmica) - Exemplo
quantidade = tamanho_pilha(pilha);
Destruir(quantidade, pilha);
esta_vazia(pilha);
return 0;
}
2019.2 27
Pilha
Implementação (Dinâmica) - Resultado
2019.2 28
Pilha
Exemplo
1 - Com relação a pilhas e filas é possível afirmar:
A [ ] Na fila simples o primeiroelemento que entra é o último a sair
B [ ] Na pilha o primeiro elemento que entra é o primeiro a sair
C [ ] Na fila simples se a variável de controle do próximo elemento da fila 
chega ao final, ela retorna para o início da fila
D [ ] Na fila circular é necessário manter uma posição vazia para se 
determinar o início e fim da fila
E [ ] Nenhuma das anteriores
2 - Em um jogo com cartões que envolve memorização, os participantes devem dizer a 
ordem inversa que os cartões foram dispostos na mesa. Que estrutura de dados deve 
ser usada para guardar os cartões a cada vez que são postos na mesa e depois, 
obtê-los na ordem inversa ? Justifique sua resposta, objetivamente.
2019.2 29
Pilha
Exemplo
3 - Seja a lista encadeada definida por:
struct listaDE
{
int info;
struct listaDE* ant;
struct listaDE* prox;
}
listaDE *lista=NULL;
Escreva a função de inserção de um nó no início desta estrutura.
4 - A conversão de um número decimal para uma outra base numérica, por exemplo 
binária ou octal ou ainda hexadecimal pode ser realizada através de um processo 
de divisões sucessivas, onde os restos da divisão são armazenados em uma estrutura 
de dados e ao serem recuperados em ordem reversa ao armazenamento obtém-se o 
número convertido na mesma base usada para divisão. Para realizar esta tarefa indique 
qual a estrutura de dados mais adequada e justifique sua resposta.
2019.2 30
Pilha
Exemplo
5 - Um programa desenvolvido para cadastrar grupos de 20 ajudantes especiais para 
atuarem em cada um dos 12 estádios sede da copa do mundo de futebol no Brasil, 
utiliza um critério especial para alocação dos grupos de ajudantes nos estádios. 
Isto é, considerando o estádio sede origem o Maracanã no Rio de Janeiro, os 20
últimos candidatos a se escreverem ficarão no estádio mais distante do Maracanâ, 
o penúltimo grupo de 20 inscritos, ficarão no segundo estádio mais distante do 
Maracanã, assim por diante até que, o segundo grupo de candidatos inscritos ficarão 
no estádio sede mais próximo do Maracanâ e os primeiros candidatos escritos serão
alocados no Maracanã. Para auxiliar o desenvolvimento deste programa pode-se utilizar:
A [ ] Uma pilha sequencial de 240 posições para fase do cadastramento de todos os 
candidatos e a mesma estrutura para realizar as alocações começando pelos os 
estádios mais distantes do estádio sede.
B [ ] Uma pilha sequencial de 20 posições para fase do cadastramento de todos os 
candidatos e a mesma estrutura para realizar as alocações começando pelos os
estádios mais distantes do estádio sede.
C [ ] Uma fila sequencial de 240 posições para fase do cadastramento de todos os 
candidatos e a mesma estrutura para realizar as alocações começando pelos os
estádios mais distantes do estádio sede.
2019.2 31
Pilha
Exemplo
D [ ] Uma fila sequencial de 20 posições para fase do cadastramento de todos os candidatos
e a mesma estrutura para realizar as alocações começando pelos os estádios mais 
distantes do estádio sede.
E [ ] Uma pilha sequencial de 20 posições para fase do cadastramento de todos os candidatos
e uma fila sequencial de 20 posições para realizar as alocações de todos os candidatos 
começando pelos os estádios mais distantes do estádio sede.
6 - As estruturas de dados são utilizadas para manter dados ou informações organizados na
memória, o que possibilita a otimização do uso destes dados. Porém, as estruturas 
guardam características especiais na manipulação destes dados, assim deve-se escolher 
a estrutura certa ou mais adequada para uma determinada aplicação. Portanto marque a 
opção que representa a melhor estrutura, quando se tem como requisitos principais a 
ordem reversa dos de armazenamento de dados e alocação destes de forma contínua na
memória.
A [ ] Lista Sequencial
B [ ] Lista Encadeada
C [ ] Pilha Sequencial
D [ ] Pilha Encadeada
E [ ] Fila Sequencial
2019.2 32
Pilha
Exemplo
7 - Observe o trecho do programa em C++ abaixo e, após, entrar com os valores sugeridos 
para sua execução assinale a alternativa que representa a resposta final.
cin >> a;
cin >> b;
cin >> c;
cin >> d;
cout << a;
cout << b;
cout << c;
cout << d;
cout << d;
cout << c;
cout << b;
cout << a;
A [ ] Após a impressão dos valores pela ordem teremos uma fila e uma
pilha.
B [ ] Após a impressão dos valores pela ordem teremos uma pilha e
uma fila.
C [ ] Após a impressão dos valores pela ordem teremos duas pilhas.
D [ ] Após a impressão dos valores pela ordem teremos duas filas.
E [ ] Após a impressão dos valores pela ordem teremos uma fila e um
grafo.
2019.2 33
Pilha
Exemplo
8 - Considere as seguintes afirmativas:
1- Pilhas são um exemplo de estrutura linear, enquanto filas são um exemplo de estrutura
não linear
2- Pilhas são uma estrutura eficiente para armazenar as requisições que os programas 
clientes façam a um programa servidor.
3- Estruturas de acesso mandatório, tais como pilhas e filas, determinam como será a 
ordem de inserção e remoção de dados da estrutura
A [ ] Somente 1 está correta
B [ ] Somente 2 está correta
C [ ] Somente 3 está correta
D [ ] Todas estão corretas
E [ ] Somente 2 e 3 estão corretas
2019.2 34
Pilha
Exemplo
9 - Ao treinar macacos, foi realizado um jogo para avaliar sua memória. O cientista 
fornecia sequências de cartas com figuras geométricas e o macaco devia reproduzir a 
sequência inversa usando figuras geométricas reais. Qual a estrutura de dados mais 
adequada para modelar esse jogo ?
A [ ] Pilha
B [ ] Fila
C [ ] Árvore
D [ ] Lista
E [ ] Grafo
10 - Ling Tang, estudante de computação, precisou implementar parte de um jogo de
cartões com figuras de animais. Alguns jogadores teriam que jogar os cartões na
mesa, enquanto outros deveriam devolver os cartões na sequência inversa à jogada.
Ling Tang estudou o mecanismo do jogo e decidiu usar a melhor estrutura de dados
na sua implementação. Qual a estrutura escolhida ?
A [ ] Pilha
B [ ] Fila
C [ ] Árvore
D [ ] Lista
E [ ] Grafo
2019.2 35
Pilha
Exemplo
11 - Considere dados sendo manipulados em uma pilha sequencial em que as operações
possíveis são: inserção - push(novo valor) ou remoção - pop().
Se realizarmos a seguinte sequencia de operações:
push(A), push(B), push(C), pop(), pop(), push(D), pop(), pop().
Pode-se dizer que o interior da pilha apresenta-se:
A [ ] Vazio
B [ ] Apenas com o dado A
C [ ] Apenas com o dado D
D [ ] Com os dados A e B
E [ ] Com os dados A e D