Estrutura de Dados - Aula 06 - Pilhas Estáticas

# Estrutura de Dados #Aula 06 – Pilhas Estáticas

Prof. Leinylson Fontinele Pereira

Na aula anterior...

Filas Estáticas Sequencial# Propriedades

# Operações fundamentais

13:48 Estrutura de Dados: Aula 06 - Pilhas Estáticas

Introdução

13:48 3 Estrutura de Dados: Aula 06 - Pilhas Estáticas

O que vamos aprender?

Pilhas Estáticas# Propriedades



Vamos começar?


13:48

O que é uma Pilha?

Estrutura de Dados: Aula 06 - Pilhas Estáticas

13:48

Algumas Pilhas...


O que é uma Pilha?

13:48

Uma pilha é uma estrutura de dados em que todo o acesso a seus elementos é feito

através do seu topo


Operações Básicas em uma Pilha

13:48

Criação da pilha

Inserção de um elemento no início

Remoção de um elemento do início

Aceso ao elemento do início

Destruição da pilhaEstrutura de Dados: Aula 06 - Pilhas Estáticas

Pilha: Características

13:48

O elemento removido é o que está naestrutura há menos tempo

O último objeto inserido na pilha é tambémo primeiro a ser removido

𝐿𝐼𝐹𝑂 (𝐿𝑎𝑠𝑡‐ 𝐼𝑛‐ 𝐹𝑖𝑟𝑠𝑡‐ 𝑂𝑢𝑡)


Pilha: Índices de Controle da Pilha

13:48Estrutura de Dados: Aula 06 - Pilhas Estáticas

LIMITE

Tamanho máximo que pode ser ocupado pela pilha

TOPO

Atual posição de consulta da pilha

BASE

Ponto de início da pilha

Executando as Operações na Pilha


Executando as Operações na Pilha


Aplicações com Pilha


Identificando Palíndromos com Pilha


Relembrando...

Palíndromos são palavras/frases que são iguais quando lidas de frente para trás

Exemplos: Ana

Arara

Rotor

Socorram me subi no onibus em marrocos

• Desconsiderando os espaços em branco

Identificando Palíndromos com Pilha


Algoritmo

Identificando Palíndromos




Empilha letra 1



Empilha letra 2



Descarta letra central



Comparar topo com próxima letra



Se são iguais então desempilhe



Comparar topo com próxima letra



Se são iguais então desempilhe

Se no final a pilha está vazia então é um palíndromo

Balanceamento de Expressões

13:48

Pilhas podem ser utilizadas para verificar seos parênteses em uma expressão estãobalanceadosExemplo:

((3 + 4 + (4 ∗ 9)ERRO: Faltam dois parênteses fechando!


Balanceamento de Expressões


((𝟑 + 𝟒 + (𝟒 ∗ 𝟗)

Chamadas de Funções

13:48

O Sistema Operacional utiliza pilhapara tratar as chamadas a funções

Fazendo uso de recursividade


13:48

Entenderam o conceito da Pilha?


Pilha: Implementação em Vetor

13:48

Supondo a pilha está armazenada em um vetor 𝑝𝑖𝑙ℎ𝑎[0. . 𝑛 − 1]

A parte do vetor ocupada pela pilha será:


Pilha: Implementação em Vetor

13:48

A natureza dos elementos do vetor é irrelevante, eles podem serinteiros, caracteres, ponteiros, etc...

O índice 𝑡 indica a primeira posição vaga da pilha

𝑡1 é o índice do topo da pilha.

A pilha está vazia se 𝑡 = 0 e cheia se 𝑡 = 𝑁


Pilha: Removendo um Elemento

13:48Estrutura de Dados: Aula 05 - Filas Estáticas

Pilha: Removendo um Elemento

13:48

Para remover (desempilhar, pop) um elemento:


Pilha: Inserindo um Elemento


Pilha: Inserindo um Elemento

13:48

Para inserir (empilhar, push) o elemento 𝑦 na pilha pilha:


Nesta aula aprendemos... Pilhas Estáticas

# Propriedades



Material: https://sites.google.com/site/leinylsonnassau

13:48

Material baseado nas aulas de:

Estrutura de dados e algoritmos, Prof. Sérgio Souza Costa


Na próxima aula veremos...

Prática com listas, filas e pilhas

Arquivos# Teoria e Prática de laboratório


Alguma Dúvida?

13:48

Até a próxima aula...

[email protected]

Prática

13:48 39

As aulas práticas foram baseadas no material de

Linguagem C Descomplicada , Dr. André R. Backes.

Disponível em: https://programacaodescomplicada.wordpress.com/


Pilha Estática

13:48

PilhaSequencial.h

Os protótipos das funções

O tipo de dado armazenado na pilha

O ponteiro pilha

Tamanho do vetor usado na pilha


Pilha Estática

13:48

PilhaSequencial.c

O tipo de dados pilha

Implementar as suas funções


13:48 42

Definindo a Pilha


Definindo a Pilha


13:48 44

Criando a Pilha


Criando a Pilha


1. Definir valor do índice de BASE da pilha

2. Definir valor máximo (LIMITE) de nodos que a pilha pode ter

3. Indicar que a pilha está vazia através do valor de TOPO

Criando a Pilha


Criando a Pilha


13:48 48

Destruindo a Pilha


Destruindo a Pilha


13:48 50

Tamanho da Pilha


Tamanho da Pilha


13:48 52

A Pilha está Cheia?


Pilha Cheia


13:48 54

A Pilha está Vazia?


Pilha Vazia


13:48 56

Algumas Considerações


Algumas Considerações


13:48 58

Inserindo na Pilha


Inserindo na Pilha


Inserindo na Pilha


13:48 61

Removendo da Pilha


Removendo da Pilha


Removendo da Pilha


13:48 64

Consultando um elemento na Pilha






Education

Estrutura de Dados - Aula 06 - Pilhas Estáticas