Estrutura de dados

Estrutura de Dados e Algoritmos e Programação e Computadores II
Pilhas e Filas

Pilhas e Filas




Estruturas Heterogêneas
Pilhas
Filas

Pilhas




Uma pilha é uma estrutura de dados que pode ser acessada somente por uma de suas extremidades para armazenar e recuperar dados. Por essa razão, uma pilha é chamada de estrutura LIFO (last in/first out).

Pilhas


Operações sobre pilhas:







clear() – limpa a pilha; isEmpty() – verifica se a pilha está vazia; push(elem) – coloca o elemento no topo da pilha; pop() – toma o elemento mais alto da pilha; topEl() – retorna o elemento mais alto da pilha sem removê-lo.

Pilhas push 10

push 5

pop

push 15

push 7

pop

7
5
10

10

15
10

15

10

10

Pilhas




Uma aplicação de pilhas é o casamento de delimitadores em um programa.
O casamento de delimitadores é parte importante de qualquer compilador. while (m < (n[8] + o))
{ p = 7; /* inicializa p */ r = 6; }

Lê o caracter ch do arquivo file; while não é o fim de file if ch é ´(´,´[´ ou ´{´ push(ch); else if ch é ´)´,´]´ ou ´}´ if ch e o caracter extraído não se casam falha; else if ch é ´/´ lê o próximo caracter; if este caracter é ´*´ pule todos os caracteres até encontrar o final do contrário “*”; indique um erro se o final for encontrado antes do “*”;
// else ignore os outros caracteres; lê o próximo caracter ch a partir de file; if a pilha está vazia sucesso; else falha;
};

Filas




Uma fila é simplesmente uma linha de espera que cresce somando elementos ao seu final e que diminui tomando elementos de sua frente. Em uma extremidade os nós são somente adicionados, e na outra os nós são somente removidos. Filas


Operações







clear() – limpa a fila; isEmpty() – verifica se a fila está vazia; isFull() – verifica se a fila está cheia; enqueue(elem) – toma o elemento no final da fila; dequeue() – toma o