Pilhas e fias

Algoritmos de manipulação de estruturas elementares de dados
Pilhas e Filas

Prof. Rosana Palazon

INTRODUÇÃO
O

objetivo desta aula é o de conceituar as estruturas de dados: Pilhas e Filas abordando suas diferentes implementações e seus mecanismos de manipulação.

Pilha e Fila – Conceitos


Uma pilha, assim como uma fila, é simplesmente uma lista linear de informações (2).



Tanto a pilha como a fila podem ser implementadas por meio de uma lista encadeada ou de um vetor.



O que difere uma pilha de uma fila é o mecanismo responsável pelo armazenamento e recuperação dos seus elementos (2).



Enquanto a fila obedece ao princípio FIFO (First In First
Out), uma pilha (ou stack) é manipulada pelo mecanismo
LIFO (Last In First Out). (1)



A analogia mais próxima que se faz de uma pilha é compará-la a uma pilha de pratos (2), e a mais próxima de uma fila é a própria fila única de um banco ou supermercado. Pilha - Conceitos


O conceito de pilha é usado em muitos softwares de sistemas incluindo compiladores e interpretadores. (A maioria dos compiladores C usa pilha quando passa argumentos para funções) (2)..



As duas operações básicas – armazenar e recuperar – são implementadas por funções tradicionalmente chamadas de push e pop, respectivamente (2)..



A função push() coloca um item na pilha e a função pop() recupera um item da pilha.



A região de memória a ser utilizada como pilha pode ser um vetor, ou uma área alocada dinamicamente (2)..

Pilha – Representação Gráfica (2)

.

Ação:
1. push (A)
2. push (B)
3. push (C)
4. pop ( ) – recupera C

C

5. push (D)

B

B

B

B

B

A

A

A

A

A

A

A

1.

2.

3.

4.

5.

6.

7.

6. pop ( ) – recupera D
7. pop ( ) – recupera B
8. pop ( ) – recupera A

D

8.

Interface do tipo Pilha
 Operações








básicas:

criar uma pilha vazia inserir um elemento (push)