A2 TADS4 Estrutura De Dados Teleaula 3 Tema 3 Impressao

15/09/2014

Estrutura de Dados
Tema 3: Pilhas.

O que é uma pilha (stack)
Um conjunto de itens dispostos linearmente, onde a remoção e a inserção de itens acontecem sempre pela mesma extremidade, chamada topo.
R
H
E
A

topo

topo
1

4

5

9

Características de uma pilha
• É um objeto dinâmico, compreendendo a possibilidade de inserção e remoção de elementos sucessivamente;
• Não há limite de tamanho;
• Fornece acesso apenas ao elemento localizado no topo;
• Chamada de lista LIFO
(last in first out)

1

15/09/2014

Analisando uma pilha graficamente
Inserir os elementos A, B, K, O, P na pilha 1

Inserir os elementos D, L,
P na pilha 2

Analisando uma pilha graficamente
Remover os elementos da pilha
H
E
A

topo

Pilha como um Tipo de Dado Abstrato
Características:
•Conjunto de elementos;
•Topo para indicar último elemento inserido
Operações:
•Inserir novo elemento -push
•Remover elemento -pop
•Obter elemento do topo
-stacktop
•Verificar se pilha está vazia -empty

2

15/09/2014

Funções Empty e Push abstract empty(pilha)
SE tem algum elemento no topo retorne
FALSE
SENÃO retorne TRUE fim empty abstract push(pilha, el) pilha ← el + pilha atualiza topo fim push

Função Stacktop abstract stacktop(pilha)
SE empty(pilha) = TRUE retorne “Erro”
SENÃO retorne elemento do topo fim stacktop

Função Pop abstract pop(pilha) aux ← pilha(topo) pilha ← pilha – pilha(topo) atualiza topo retorne aux fim pop

3

15/09/2014

Representando uma pilha em C usando vetor
#define TAM 100 struct pilha { char itens[TAM]; int topo;
};
... struct pilha p;
p.topo = -1;

Continuando
Tema 3: Pilhas.

Implementando uma Pilha em C
(vetor)
#include <stdio.h>
#include <stdlib.h>
#define TAM 100 struct pilha { char itens[TAM]; int topo;
};

4

15/09/2014

void push(struct pilha *p, int el) { if (p->topo == TAM-1) //pilha cheia exit(1); else { p->topo = p->topo + 1; p->itens[p->topo] = el;
}
}

int empty(struct pilha *p) { if (p->topo == -1) return true; else return false;
}
int stacktop(struct pilha