UNIVERSIDADE EDUARDO MONDLANE

FACULDADE DE ENGENHARIA

Departamento de Electrotecnia

Engenharia Informática – Pós Laboral

Listas, Pilhas e Filas

Discente: Docente:

Mboa, Elton Ernesto Eng. Munguanaze

Maputo, Novembro de 201

1
Faculdade de Engenharia – Listas, Pilhas e Filas - Mboa, Elton Ernesto
Listas
Conceito
A estrutura de dados Lista é um conjunto de dados dispostos e/ou acessíveis em uma
sequência determinada.
Este conjunto de dados pode:
 Possuir uma ordem (Lista Ordenada) ou não;
 Ocupar espaços de memória fisicamente consecutivos ou não, espelhando a sua
ordem ou não.
Uma Lista Simplesmente Encadeada é uma cadeia de objectos do mesmo tipo, ligados
através de ponteiros de um objecto para o próximo. Cada elemento da lista é chamado nó
ou nodo e tem um campo reservado para o valor (que pode ser de qualquer tipo de dados)
e o campo next, onde fica guardada a referência para o próximo elemento da lista.
Abaixo, a estrutura de um nodo:
Onde:
dado – Guarda a informação útil.

next – Guarda referência para o próximo elemento (nodo) da lista

Operações sobre Listas

1) Percurso
Permite utilizar cada um dos elementos de uma lista, detal forma que: · 0 primeiro nodo utilizado
é o primeiro da lista; · Para utilizar o nodo Xj, todos os nodos de X1 até X(j-1) já foram
utilizados; · último nodo utilizado é o último nodo da lista.

2) Busca
Procura um nodo específico da lista linear, de tal forma que: · nodo é identificado por sua
posição na lista; · nodo é identificado pelo seu conteúdo.

3) Inserção
Acrescenta um nodo X a uma lista linear, de tal forma que: · nodo X terá um sucessor e/ou um
antecessor; · Após inserir o nodo X na posição i (i >= 1 e i <= n+1), ele passará a ser i-ésimo
nodo da lista; · número de elementos (n) é acrescido de uma unidade.

2
Faculdade de Engenharia – Listas, Pilhas e Filas - Mboa, Elton Ernesto
4) Retirada (Exclusão)
Retira um nodo X da lista, de tal forma que: · Se Xi é o elemento retirado, o seu sucessor passa a
ser o sucessor de seu antecessor. X(i+1) passa a ser o sucessor de X(i-

63
1). Se Xi é o primeiro nodo, o seu sucessor passa a ser o primeiro, se Xi é o último, o seu
antecessor passa a ser o último; · número de elementos (n) é decrescido de uma unidade

3
Faculdade de Engenharia – Listas, Pilhas e Filas - Mboa, Elton Ernesto
Pilha

Conceito Básico

A pilha é uma estrutura de dados básica que fornece a lógica conhecida por LIFO(Last In, First
out). Isso significa que o ultimo dado adicionado a estrutura será o primeiro removido dela e por
isso foca a entrada e saída de dados na mesma ponta do vetor/lista.

Na prática, a pilha como um controle para serviços que dependem da conclusão do ultimo
recurso ativado antes de prosseguirem. Exemplos de rotinas que utilizam essa lógica são o
“desfazer” do Word e o gerenciamento da execução de funções (de programação), que causa o
conhecido erro de stackoverflow.

Código Fonte

O código fonte abaixo não vai usar o vetor do JavaScript simplesmente para podermos ver em
mais detalhes o funcionamento desta estrutura de dados. não será uitlizado um vetor, mas sim
nós (nodes) que se conectam uns aos outros.

1. function Pilha() {
2. var topo = null;
3. var quantidade = 0;
4.
5. //Retorna o número de itens na Pilha
6. [Link] = function () {
7. return quantidade;
8. }

4
Faculdade de Engenharia – Listas, Pilhas e Filas - Mboa, Elton Ernesto
 9. //Push: Adiciona itens ao topo da pilha
10. [Link] = function (dados) {
11. var node = {
12. dados: dados,
13. proximo: null
14. };
15.
16. [Link] = topo;
17. topo = node;
18.
19. quantidade++;
20. }
21. //Pop: Remove itens do topo da pilha
22. [Link] = function () {
23. if (topo === null) {
24. return null;
25. } else {
26. var removido = topo;
27. topo = [Link];
28.
29. if (quantidade > 0) {
30. quantidade--;
31. }
32.
33. return [Link];
34. }
35. }
36. //Exibe o Item do topo da pilha
37. [Link] = function () {
38. if (topo === null) {
39. return null;
40. } else {
41. return [Link];
42. }
43. }
44. //Retorna um vetor com todos iitens da Pilha
45. [Link] = function () {
46. if (topo === null) {
47. return null;
48. } else {
49. var arr = new Array();

5
Faculdade de Engenharia – Listas, Pilhas e Filas - Mboa, Elton Ernesto
 50. var current = topo;
51.
52. for (var i = 0; i < quantidade; i++) {
53. arr[i] = [Link];
54. current = [Link];
55. }
56.
57. return arr;
58. }
59. }
60. }

Manipulação
O programa abaixo demonstra a inclusão, exclusão e consulta de números inteiros em uma Pilha
alocada estaticamente usando a classe Pilha:

public class Pilha {

final int SUCESSO = 0;
final int PILHA_CHEIA = 1;
final int PILHA_VAZIA = 2;
protected final int m = 7;
protected int topo;
protected int [ ]elem = new int[m];
//----------- criaVetor
public void criaVetor() {
topo = -1;
}
// ------------ Topo
public int Topo() {
if (topo == -1) {
[Link]("Vetor Vazio!!");
return(PILHA_VAZIA);
}
else {
[Link]("Topo: " + elem[topo]);
return(SUCESSO);

6
Faculdade de Engenharia – Listas, Pilhas e Filas - Mboa, Elton Ernesto
}
}
// -------- exibePilha
public void exibePilha() {
[Link]("Pilha: ");
if (topo != -1) {
for (int i = topo;i >= 0; i--) {
[Link](elem[i] + " ");
}
[Link]();

}
// ----------- push
public int push(int dado) {
if (topo == m - 1) {
[Link]("Vetor Cheio!!");
return(PILHA_CHEIA);
}
else {
topo = topo + 1;
elem[topo] = dado;
return(SUCESSO);
}
}
// ---------- pop
public int pop() {
if (topo == -1) {
[Link]("Pilha Vazia!!");
return(PILHA_VAZIA);
}
else {
[Link]("Pop: " + elem[topo]);
topo = topo - 1;
return(elem[topo+1]);
}
}

7
Faculdade de Engenharia – Listas, Pilhas e Filas - Mboa, Elton Ernesto
Fila

Conceito Básico

Fila é um tipo de estrutura de dados com um controle definido pela lógica FIFO (do inglês first
in, last out). Esse controle quer dizer que os dados contidos nela são podem entrar apenas por
uma ponta e deverão sair pela outra. Com isso, garante-se que o primeiro dado que entrou será o
primeiro a sair da fila.

A fila é uma estrutura de dados muito útil quando se possui um serviço ao qual o sistema recebe
alimentação de diversas fontes, mas precisa manter uma ordem do “primeiro que chegou será o
primeiro servido”. Um exemplo simples é o sistema que administra diversos computadores
ligados a uma única impressora.

Código Fonte

O código fonte abaixo não vai usar o vetor do JavaScript simplesmente para podermos ver em
mais detalhes o funcionamento desta estrutura de dados. Não será utilizado um vetor como forma
de controle mas sim nós contectados uns aos outros, irei também fazer com que o ato de
adicionar o faça no começo da fila e o de remover será na outra ponta.

1. function Fila() {
2. var quantidade = 0;
3. var primeiro = null;
4. var ultimo = null;
5.
6. //Retorna a quantidade na fila
7. [Link] = function () {
8. return quantidade;
9. }
10. //adiciona um item a fila
11. [Link] = function (data) {
12. var node = {
13. data: data,

8
Faculdade de Engenharia – Listas, Pilhas e Filas - Mboa, Elton Ernesto
 14. prox: primeiro
15. };
16.
17. if (primeiro === null) {
18. ultimo = node;
19. }
20.
21. primeiro = node;
22.
23. quantidade++;
24. }
25. //Remove um item da fila
26. [Link] = function () {
27. //se a fila estiver vaiza, retorna nulo
28. if (ultimo === null) {
29. return null;
30. }
31. else {
32. //senão percorre a fila até o ultimo item para removelo e ajusta a lista
33. var current = primeiro;
34. var previous = null;
35.
36. while ([Link]) {
37. previous = current;
38. current = [Link];
39. }
40.
41. if (quantidade > 1) {
42. [Link] = null;
43.
44. ultimo = previous;
45. }
46. //zera/reseta a fila
47. else {
48. primeiro = null;
49. ultimo = null;
50. }
51. quantidade--;
52. }
53. //Exibe todos os itens da fila
54. [Link] = function () {

9
Faculdade de Engenharia – Listas, Pilhas e Filas - Mboa, Elton Ernesto
 55. if (primeiro === null) {
56. return null;
57. } else {
58. var arr = new Array();
59. var current = primeiro;
60.
61. for (var i = 0; i < quantidade; i++) {
62. arr[i] = [Link];
63. current = [Link];
64. }
65.
66. return arr;
67. }
68. }
69. }
70. }

Manipulação
O programa abaixo demonstra a inclusão, exclusão e consulta de números inteiros
em uma Fila usando as classes: Fila.
public class Fila {
final int SUCESSO = 0;
final int PILHA_CHEIA = 1;
final int PILHA_VAZIA = 2;
protected final int m = 7;
protected int topo;
protected int []elem = new int[m];
//----------- criaVetor
public void criaVetor() {
topo = -1;
}
// ----------- push
public int push(int dado) {
if (topo == m - 1) {
[Link]("Vetor Cheio!!");
return(PILHA_CHEIA);
}
else {
topo = topo + 1;
elem[topo] = dado;
return(SUCESSO);

10
Faculdade de Engenharia – Listas, Pilhas e Filas - Mboa, Elton Ernesto
}

Public int topo( )

{
if (topo == -1) {
[Link]("Vetor Vazio!!");
return(PILHA_VAZIA);

else {
[Link]("Topo: " + elem[topo]);
return(SUCESSO);
}
}
// ---------- pop
public int pop() {
if (topo == -1) {
[Link]("Fila Vazia!!");
return(PILHA_VAZIA);
}
else {
[Link]("Pop: " + elem[0]);
aux=elem[0];
topo = topo - 1;
for(int cont=1;cont<m;cont++)
elem[cont-1]=elem[cont];
return(aux);
}
}
// -------- exibeFila
public void exibeFila() {
[Link]("Fila: ");
if (topo != -1) {
for (int i = topo;i >= 0; i--) {
[Link](elem[i] + " ");
}
[Link]();
}

11
Faculdade de Engenharia – Listas, Pilhas e Filas - Mboa, Elton Ernesto