ippqwert

Engenharia da Computação

Tutorial

Aplicações de Pilhas Em C++.

Autores:

Alexandre Cordaro – RA: 12435/08-2
Erick Carrijo de Oliveira – RA: 10294/08-2
João Felipe Tunuchi – RA: 11278/08-7
Leonardo Willians Couto – RA: 12307/08-6
Pablo Inácio Dutra – RA: 00846/08-9
Rafael Moraes da Silva – RA: 02657/08-7

SÃO PAULO

2 0 1 0
Definição de Pilha

Na computação, uma pilha (stack em inglês) é uma estrutura de dados básica. Seu comportamento é bem simples, o último que entrou é o primeiro que sai. Nos chamamos isso de LIFO de Last In First Out.

Pilhas são usadas extensivamente em cada nível de um sistema de computação moderno. Por exemplo, um PC moderno usa pilhas ao nível de arquitetura, as quais são usadas no design básico de um sistema operacional para manipular interrupções e chamadas de função do sistema operacional. Entre outros usos, pilhas são usadas para executar uma Máquina virtual java e a própria linguagem Java possui uma classe denominada "Stack", as quais podem ser usadas pelos programadores. A pilha é onipresente.
Um sistema informático baseado em pilha é aquele que armazena a informação temporária basicamente em pilhas, em vez de registradores de hardware da UCP (um sistema baseado em registradores).

Acima na figura, temos uma representação da pilha, onde a inserção de um novo item ou a remoção de um item já existente se dá em uma única extremidade, no topo.

Estrutura de pilhas

Pilha vazia
Insere(A)
Insere(B)
Retira(B)
Insere(C)
Retira(C)
Retira(A)

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).
Operações Associadas:
1. criar (P) - criar uma pilha P vazia
2. inserir (x, P) - insere x no topo de P (empilha): push(x,P)
3. vazia (P) - testa se P está vazia
4. topo (P) - acessa o elemento do topo da pilha (sem