Wserwserwsert

Pilhas Encadeadas (com Alocação Dinâmica)

Prof. Ms. Eleandro Maschio Tecnologia em Sistemas para Internet Campus Guarapuava Universidade Tecnológica Federal do Paraná (UTFPR)

Conceito (Revisão)
• Chamadas também de stacks. • Funcionam de modo análogo a uma pilha de pratos. • Uma pilha é um conjunto de dados linearmente ordenados (possui primeiro, segundo...). • A manipulação de elementos é permitida somente no topo da pilha. • Portanto, não se possibilita acesso aos outros elementos de uma pilha. • Os elementos são organizados de maneira que: • o último a entrar seja o primeiro a sair. • last in, first out - LIFO.

Push e Pop (Revisão)
Há duas operações básicas e características de uma pilha:

• empilhamento (push): insere um elemento no topo da pilha.

push

pop

5 2 4 6 1

• desempilhamento (pop): remove o elemento que está no topo da pilha.

Representação Encadeada

• Implementada através de uma coleção de nós conectados: • implementação menos simples. • estrutura dinâmica. • maior flexibilidade: tamanho variável.

Representação Encadeada
Representação na memória:

topo

2
Nó

4
Nó

6
Nó

1
Nó

null

Structs Envolvidas

• Observamos claramente a necessidade de implementar duas structs: • Nó: para representar individualmente cada elemento da pilha. • Pilha: a estrutura de dados propriamente dita. Serve para coordenar o encadeamento de nós conforme as regras da estrutura de dados pilha.

Struct Nó
• A struct Nó possui dois únicos atributos: • valor ou dado: valor (inteiro, no exemplo) armazenado no nó. • próximo: referência (ponteiro) para o próximo nó.

2

4

typedef struct No { int valor; No *proximo; };

Structs Nó e Pilha
Temos pronto: o encadeamento dos nós que guardam os elementos da coleção.

2

4

6

1

null

Falta: criar uma struct que coordene a manipulação de elementos (internamente representados por nós) na coleção. topo null

Struct Pilha

topo

2
Nó

4
Nó

6