Pilha.h

Disponível somente no TrabalhosFeitos
  • Páginas : 5 (1115 palavras )
  • Download(s) : 0
  • Publicado : 30 de janeiro de 2013
Ler documento completo
Amostra do texto
Introdução a Linguagem de Programação C

Disciplina: Estrutura de Dados I

Pilhas: Estática e Dinâmica

Prof. Rafael Alexandre

1

Sumário
Definição

Operações
Implementações

Front cover

2

Pilhas

• Definição: Dada uma pilha P=( a(1), a(2), ..., a(n) ), dizemos que a(1) é o elemento da base da pilha; a(n) é o elemento topo da pilha; e a(i+1) está acima de a(i). Pilhassão também conhecidas como listas LIFO (last in first out).

3

Implementação de Pilhas

• Tipos de Implementação:
• Através de arranjos (arrays) – Pilhas estáticas • Através de apontadores ou ponteiros – Pilhas dinâmicas

• Em qualquer uma das implementações, deve-se:
• Definir a estrutura de dados • Definir as operações

4

Operações Usuais de uma Pilha

• • • •

Iniciar/Criaruma Pilha vazia Inserir um novo item retirar um item Imprimir os itens

5

Operações Básicas de uma Pilha

1. inicializa
parâmetros: TipoPilha *pilha funcionalidade: faz a pilha pilha ficar vazia resultado: retorna (indiretamente) a pilha pilha vazia

2. vazia
parâmetros: TipoPilha pilha funcionalidade: testa se a pilha pilha está vazia ou não resultado: retorna (diretamente) 1 se apilha pilha está vazia; senão retorna 0

6

Operações Básicas de uma Pilha

3. Empilha
parâmetros: TipoItem Item, TipoPilha *pilha funcionalidade: insere o item x após o último item da pilha pilha 4. Desempilha parâmetros: TipoItem *Item, TipoPilha *pilha funcionalidade: retorna (indiretamente) o item Item.

7

Operações Básicas de uma Pilha

5. imprime
parâmetros: TipoPilha Pilhafuncionalidade: imprime os itens da pilha pilha resultado: impressão dos itens da pilha na ordem de ocorrência

8

Pilhas com Array– Estrutura

TipoPilha

0

1

n-1

n

MAX-1

item

x1
Base Topo

x2

...

xn

...

9

Pilha com Array– Estrutura
#define typedef typedef typedef MAX 100 int tipoChave; int apontador; struct { tipoChave chave; //outros componentes}tipoItem; typedef struct{ tipoItem item[MAX]; apontador topo; }tipoPilha;

10

Pilha com Array– Operação inicializa

void fpVazia(tipoPilha *pilha) { pilha->topo = 0; }

tipoPilha

0

1

2

MAX

item

...

topo

11

Pilha com Array– Operação inicializa

void fpVazia(tipoPilha *pilha) { pilha->topo = 0; }

tipoPilha

0

1

2

MAX

item topo

...

12 Pilha com Array– Operação vazia

int vazia(tipoPilha pilha) { return(pilha.topo == 0); } //Esta pilha esta vazia

tipoPilha

0

1

2

MAX

item topo

...

13

Pilha com Array– Operação empilha

void empilha(tipoItem x, tipoPilha *pilha) { if (pilha->topo==MAX) cout topo++; pilha->item[pilha->topo-1] = x; } }

x

tipoPilha

x1
item

0

1

2

MAX

...

topo
15 Pilha com Array– Operação empilha

void empilha(tipoItem x, tipoPilha *pilha) { if (pilha->topo==MAX) cout topo++; pilha->item[pilha->topo-1] = x; } }

x

tipoPilha

x1
item

0

1

2

MAX

x1

...

topo
17

Pilha com Array– Operação empilha

void empilha(tipoItem x, tipoPilha *pilha) { if (pilha->topo==MAX) cout topo++; pilha->item[pilha->topo-1] = x; } }

xtipoPilha

x1
item

0

1

2

MAX

x1

...

topo
19

Pilha com Array– Operação desempilha

void desempilha (tipoPilha *pilha, tipoItem *x) { if (vazia(*pilha)) cout item[pilha->topo-1]; pilha->topo--; } }

0

1

2

3

4

5

MAX

item *x

x1

x2

x3

x4

x5

...

topo
21

Pilha com Array– Operação desempilha

void desempilha (tipoPilha*pilha, tipoItem *x) { if (vazia(*pilha)) cout item[pilha->topo-1]; pilha->topo--; } }

0

1

2

3

4

5

MAX

item *x

x1

x2

x3

x4

x5

...

x5
23

topo

Pilha com Array– Operação desempilha

void desempilha (tipoPilha *pilha, tipoItem *x) { if (vazia(*pilha)) cout item[pilha->topo-1]; pilha->topo--; } }

0

1

2

3

4

5

MAX

item *x

x1...
tracking img