Pilha.h

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). Pilhas sã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/Criar uma 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 a pilha 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 Pilha funcionalidade: 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