PlanoDeAula_278404

Prévia do material em texto

Plano	de	Aula:	Listas	Lineares	Sequenciais	e	Encadeadas	(Parte
III)
ESTRUTURA	DE	DADOS	-	CCT0021
Título
Listas	Lineares	Sequenciais	e	Encadeadas	(Parte	III)
Número	de	Aulas	por	Semana
Número	de	Semana	de	Aula
10
Tema
Listas	Lineares	Sequenciais	e	Encadeadas	(Parte	III)
Objetivos
Possibilitar	ao	aluno:
-	Reconhecer	e	manipular	o	TAD	Pilha
-	Desenvolver	no	laboratório	os	conceitos	sobre	o	TAD	Pilha	por	meio	de
exercícios	guiados	que	criem	situações	de	uso	dessas	estruturas.
Estrutura	do	Conteúdo
CONTEÚDOS:
Pilha
RESUMO	DE	CONCEITOS:
Definição
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).
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.
As	operações	de	inclusão	e	remoção	para	pilhas	são	conhecidas	como	"push''
e	"pop''.
Pilhas	também	podem	ser	estáticas	ou	dinâmicas.	Como	no	caso	das	listas,	as
implementações	estáticas	de	pilhas	normalmente	fazem	uso	de	arrays	e	as
dinâmicas	utilizam	ponteiros.
Implementação	(Estática)
Uma	das	formas	mais	simples	de	se	implementar	uma	pilha	é	utilizando	array.
No	exemplo	abaixo,	os	elementos	armazenados	serão	números	inteiros.
A	informação	sobre	o	topo	da	pilha	também	deve	ser	armazenada.
A	principal	vantagem	em	se	utilizar	implementação	estática	de	pilhas	é	a
simplicidade	da	implementação.
Especificação:	
1.	 PLH	*Inicia_Pilha(int	N)
Cria	uma	nova	estrutura	de	pilha	com	tamanho	máximo	N.
2.	 PUSH(PLH	*P,	int	A)
Insere	um	novo	elemento	A	no	topo	da	pilha	P
3.	 int	POP(PLH	*p)
Retira	o	elemento	do	topo	da	pilha	P	retornando	seu	valor
4.	 int	SIZE(PLH	*p)
retorna	o	valor	correspondente	a	quantidade	de	elementos
armazenados	na	Pilha
5.	 int	IS_EMPTY(PLH	*p)
retorna	o	valor	1	se	a	Pilha	estiver	vazia	e	0,	caso	contrário.
typedef	struct	Pilha	PLH;
struct	No_Pilha
{
				int	top	;
				int	max	;	/*	Armazena	o	tamanho	máximo	da	pilha	*/
				int	*elem;	
};
void	PUSH(PLH	*P,int	A)
{
				if	(P->top	<	P->max	-	1)
								P->elem[++(P->top)]	=	A;
				else
								cout	<<	"Pilha	Cheia"	<<	endl;
}
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.
	
	
typedef	struct	Pilha	PLH;
typedef	struct	No_pilha	NO	;
struct	No_pilha
{
	int	elem;
	NO	*prox;
}
struct	Pilha
{
	NO	*top;
}
/*	Exercício:	Implementar	as	operações	de	PUSH	e	POP	e	as	outras	funções*/
Aplicação	Prática	Teórica
SUGESTÃO	DE	EXERCÍCIOS	PARA	SEMANA	10
TEÓRICOS
1.	 Ano:	 2014	 /	 Banca:	 CESGRANRIO	 /	 Órgão:	 Banco	 da	 Amazônia	 /	 Prova:
Técnico	Científico	-	Banco	de	Dados
	
Considere	 o	 tipo	 abstrato	 de	 dados	 Pilha	 com	 as	 seguintes
especificações:
-	 Pilha	 é	 uma	 lista	 (LIFO)	 de	 itens	 com	 a	 restrição	 de	 que
inserções	(Push)	e	retiradas	(Pop)	de	itens	só	podem	ser	feitas
no	final	da	lista	(Topo	da	lista).
-	CriarP	cria	uma	pilha	P	vazia.
-	Push(P,	i)	insere	o	item	i	no	Topo	da	pilha	P.
-	Pop(P)	retira	e	retorna	da	pilha	P	o	item	que	está	no	Topo	da
pilha	P.
-	Pop(P)	para	pilha	P	vazia	=	Erro.
Com	 essa	 especificação,	 quais	 são,	 respectivamente,	 os	 resultados
das	expressões
Pop(Push(CriarP,	X))
Pop	(CriarP)
Pop(Push(P,(Pop(Push(CriarP,	X)))))
a)	X,	X,	X
b)	X,	Erro,	Erro
c)	X,	Erro,	X
d)	Erro,	Erro,	Erro
e)	Erro,	Erro,	X
	
1.	 Ano:	 2014	 /	 Banca:	 FCC	 /	 Órgão:	 SABES	 /	 PProva:	 Técnico	 em	 Gestão	 -
Informática
	
Considere	 uma	 pilha	 s	 e	 um	 item	 i.	 As	 funções	 que	 executam	 a
operação	primitiva	para	incluir	o	item	i	no	topo	da	pilha	s	e,	a	operação
para	 remover	 o	 elemento	 do	 topo	 e	 o	 retornar	 como	 valor	 da	 função
são,	respectivamente,
a)	bop(s,i)	e	pop(s,i).
b)	queuein(s,i)	e	queueout(s,i)
c)	stackpush(s,i)	e	stacktop(s).
d)	push(s,i)	e	pop(s).
e)	settop(s,i)	e	gettop(s).
	
1.	 Ano:	2013	 /	Banca:	ESAF	 /	Órgão:	DNIT	 /	Prova:	Analista	Administrativo	 -
Tecnologia	da	Informação
	
Assinale	a	opção	correta	relativa	às	operações	básicas	suportadas	por
pilhas.
a)	Push:	insere	um	novo	elemento	no	final	da	pilha.
b)	Pop:	adiciona	elementos	ao	topo	da	pilha.
c)	Pull:	insere	um	novo	elemento	no	interior	da	pilha.
d)	Top:	transfere	o	último	elemento	para	o	topo	da	pilha.
e)	Top:	acessa	o	elemento	posicionado	no	topo	da	pilha.
	
1.	 Ano:	2012	 /	Banca:	CESPE	 /	Órgão:	Banco	da	Amazônia	 /	Prova:	Técnico
Científico	-	Administração	de	Dados
	
O	uso	de	alocação	dinâmica	de	memória	é	essencial	na	criação	de	uma
pilha	de	dados.
(					)	Certo	(					)	Errado
	
1.	 Ano:	2012	/	Banca:	CONSULPLAN	/	Órgão:	TSE	/	Prova:	Técnico	Judiciário	-
Programação	de	Sistemas
	
A	empresa	HIGH_TEC_STE	Consultoria	&	Projetos	possui	suas	atividades
de	 TI	 informatizadas,	 atuando	 em	 apoio	 ao	 STE,	 possuindo	 as
características	listadas	a	seguir,	de	forma	resumida.
	
Agora,	 observe	 os	 quadros	 I	 e	 II,	 relacionados	 à	 estrutura	 de	 dados
pilha.
	
Após	 a	 execução	 de	 todas	 as	 operações	 indicadas	 no	 quadro	 II,	 o
elemento	de	topo	da	pilha	será	igual	a
a)	SANTA_CATARINA.
b)	SANTO_EXPEDITO.
	
1.	 Ano:	2012	 /	Banca:	AOCP	 /	Órgão:	BRDE	 /	 Prova:	Analista	de	Sistemas	 -
Desenvolvimento	de	Sistemas
	
Em	 estruturas	 de	 dados	 e	 algoritmos,	 encontramos	 uma	 estrutura
chamada	 Pilha.	 A	 esse	 respeito,	 analise	 as	 assertivas	 e	 assinale	 a
alternativa	que	aponta	as	corretas.
I.	Uma	Pilha	é	um	contêiner	de	objetos	que	são	inseridos
e	 retirados	de	acordo	 com	o	princípio	de	que	 “o	último
que	entra	é	o	primeiro	que	sai”	(LIFO).
II.	Exemplo	de	implementação	de	uma	pilha	pode	ser	os
navegadores	 para	 a	 Internet	 que	 armazenam	 os
endereços	mais	recentemente	visitados	em	uma	pilha.
III.	 Pilhas	 são	 estruturas	 de	 dados	 muito	 complexas,
porém	não	estão	entre	as	mais	importantes.
IV.	É	 impossível	 inserir	objetos	em	uma	pilha	a	qualquer
momento,	mas	somente	o	objeto	recentemente	inserido
poderá	ser	removido	a	qualquer	momento.
a)	Apenas	I	e	II.
b)	Apenas	I	e	III.
c)	Apenas	II	e	III.
d)	Apenas	II,	III	e	IV.
e)	I,	II,	III	e	IV.
	
1.	 Sobre	pilhas	é	correto	afirmar:
a)	Uma	lista	LIFO	(Last-In/First-Out)	é	uma	estrutura	estática,	ou
seja,	é	uma	coleção	que	não	pode	aumentar	e	diminuir	durante
sua	existência.
b)	 Os	 elementos	 na	 pilha	 são	 sempre	 removidos	 na	 mesma
ordem	em	que	foram	inseridos.
c)	 Uma	 pilha	 suporta	 apenas	 duas	 operações	 básicas,
tradicionalmente	denominadas	push	 (insere	um	novo	elemento
no	topo	da	pilha)	e	pop	(remove	um	elemento	do	topo	da	pilha).
d)	Cada	vez	que	um	novo	elemento	deve	ser	 inserido	na	pilha,
ele	 é	 colocado	no	 seu	 topo	 e,	 em	qualquer	momento,	 apenas
aquele	posicionado	no	topo	da	pilha	pode	ser	removido.
e)	 Sendo	 P	 uma	 pilha	 e	 x	 um	 elemento	 qualquer,	 a	 operação
Push(P,x)	diminui	o	tamanho	da	pilha	P,	removendo	o	elemento
x	do	seu	topo.
	
1.	 Ano:	 2010	 /	 Banca:	 CESPE	 /	 Órgão:	 INMETRO	 /	 Prova:	 Pesquisador	 -
Ciência	da	Computação
	
	
Considere	 que,	 no	 trecho	 do	 programa	 acima,	 representado	 por	 seu
pseudocódigo,	 seja	 fornecido	 para	 num,	 sucessivamente,	 os	 valores
inteiros	 1,	 2,	 3,	 4,	 5,	 3	 e	 6.	 Nesse	 caso,	 ao	 final	 da	 execução	 do
programa,	o	valor	de	x	será	igual	a
a)	2	e	a	pilha	terá	os	valores	6,	4	e	1.
b)	3	e	a	pilha	terá	os	valores	6,	4	e	1.
c)	5	e	a	pilha	terá	os	valores	6,	4	e	1.
d)	3	e	a	pilha	terá	os	valores	6,	5,	4,	2	e	1.
e)	5	e	a	pilha	terá	os	valores	6,	3,	5,	4,	3,	2	e	1.
	
1.	 Ano:	 2006	 /	 Banca:	 CESGRANRIO	 /	 Órgão:	 DECEA	 /	 Prova:	 Técnico	 de
Defesa	Aérea	e	Controle	de	Tráfego	Aéreo	-	Análise	de	SistemasObserve	o	código	abaixo,	que	 implementa	uma	estrutura	de	dados	do
tipo	pilha.
	
	
Assinale	a	opção	que	contém	o	código	correto	correspondente	à	linha
14.
a)	head[++pointer]	=	i;
b)	head[i]	=	pointer++;
c)	head[pointer]=i;
d)	head.indexOf[i]	=	pointer;
e)	return	head[pointer++];
	
	
1.	 Ano:	 2006	 /	 Banca:	 CESGRANRIO	 /	 Órgão:	 EPE	 /	 Prova:	 Técnico	 de	 Nível
Superior	-	Área	Tecnologia	da	Informação
	
A	tabela	abaixo	mostra	as	operações	para	a	manipulação	de	uma	pilha.
Utilizando	as	definições	acima,	 a	 sequência	de	 instruções	a	 seguir	 foi
implementada	para	avaliar	o	resultado	de	uma	expressão,	sendo	A,	B,
C,	 D	 e	 E	 os	 operandos	 desta	 expressão.	 O	 resultado	 da	 avaliação	 é
acumulado	em	F.
PUSH	A
PUSH	B
SUB
PUSH	C
PUSH	D
PUSH	E
MPY
ADD
DEC
DIV
POP	F
Com	base	no	 que	 foi	 exposto	 acima,	 se	A,	 B,	 C,	D	 e	 E	 apresentarem,
respectivamente,	os	valores	9,	3,	2,	1	e	1,	qual	o	valor	armazenado	em
F	após	a	execução	da	instrução	POP	F?
a)	2
b)	3
c)	4
d)	5
e)	6
	
PRÁTICOS
1.	 Escreva	 funções	 desempilha	 e	 empilha	 para	 manipular	 uma	 pilha.
Lembre-se	de	que	uma	pilha	é	um	pacote	com	dois	objetos:	um	vetor	e
um	 índice.	 Quais	 os	 parâmetros	 de	 suas	 funções?	 Não	 use	 variáveis
globais.
	
2.	 VALOR	DE	EXPRESSÃO	POLONESA.	 	 	Suponha	 que	 posf	 é	 uma	 string
que	guarda	uma	expressão	aritmética	em	notação	posfixa.	Suponha	que
posf	não	é	vazia	e	contém	somente	os	operadores		+,		-,		*		e		/	 	(todos
exigem	 dois	 operandos).	 Suponha	 também	 que	 a	 expressão	 não	 tem
constantes	e	que	todos	os	nomes	de	variáveis	na	expressão	consistem
em	 uma	 única	 letra	 maiúscula.	 Suponha	 ainda	 que	 temos	 um	 vetor
tabela	que	dá	os	valores	das	variáveis	(todas	os	valores	são	inteiros):
tabela[0]	é	o	valor	da	variável	A,
tabela[1]	é	o	valor	da	variável	B,	etc.
Escreva	 uma	 função	 que	 calcule	 o	 valor	 da	 expressão	 posf.	 Cuidado
com	divisões	por	zero!
	
1.	 Escreva	 um	 algoritmo	 que	 use	 uma	 pilha	 para	 inverter	 a	 ordem	 das
letras	 de	 cada	 palavra	 de	 uma	 string,	 preservando	 a	 ordem	 das
palavras.	 Por	 exemplo,	 dado	 o	 texto	 	 ESTE	 EXERCICIO	 E	MUITO	 FACIL	 	 a
saída	deve	ser		ETSE	OICICREXE	E	OTIUM	LICAF.
	
2.	 Digamos	 que	 nosso	 alfabeto	 contém	 apenas	 as	 letras	 a,	 b	 e	 c.
Considere	o	seguinte	conjunto	de	strings	sobre	nosso	alfabeto:
c,		aca,		bcb,		abcba,		bacab,		aacaa,		bbcbb,		.	.	.
Qualquer	 string	 desse	 conjunto	 tem	 a	 forma	 WcM,	 onde	 W	 é	 uma
sequência	de	letras	que	só	contém	a	e	b	e	M	é	o	inverso	de	W,	ou	seja,
M	é	W	lido	de	trás	para	frente.	Escreva	um	programa	que	determina	se
uma	string	X	pertence	ou	não	ao	nosso	conjunto,	ou	seja,	determina	se
X	é	da	forma	WcM.
	
1.	 Permutações	produzidas	pelo	pop.		Suponha	que	os	inteiros	1,2,3,4	são
colocados,	 nesta	 ordem,	 numa	 pilha	 inicialmente	 vazia.	 Depois	 de
empilhar	cada	inteiro,	você	pode	retirar	zero	ou	mais	elementos	da	pilha.
Cada	 elemento	 desempilhado	 é	 impresso	 numa	 folha	 de	 papel.	 Por
exemplo,	a	sequência	de	operações
push	1,	push	2,	pop,	push	3,	pop,	pop,	push	4,	pop,
produz	 a	 impressão	 da	 sequência	 2,3,1,4.	Quais	 das	 24	 permutações
de	1,2,3,4	podem	ser	obtidas	desta	maneira?