Mudanças entre as edições de "PRG29003: Introdução a Pilhas"

De MediaWiki do Campus São José
Ir para navegação Ir para pesquisar
(Criou página com 'Pilhas são estruturas do tipo LIFO (''Last In First Out'' - último a entrar, primeiro a sair). Apenas duas operações são possíveis de modificar pilhas: {| border="0" |* ''...')
 
 
(19 revisões intermediárias por 2 usuários não estão sendo mostradas)
Linha 1: Linha 1:
−
Pilhas são estruturas do tipo LIFO (''Last In First Out'' - último a entrar, primeiro a sair). Apenas duas operações são possíveis de modificar pilhas:
+
[[PRG29003:_Introdução_a_Listas|Próxima aula]]
 +
 
 +
 
 +
Pilhas são estruturas de dados lineares, em que os dados são retirados em ordem inversa a que foram inseridos. Esse comportamento é denominado LIFO (''Last In First Out'' - último a entrar, primeiro a sair).
 +
 
 +
 
 +
[[imagem:PRG2-Stack_example.jpg]]
 +
<br>''Algumas pilhas da vida real ...''
 +
 
 +
 
 +
Pilhas apresentam três operações típicas:
  
 
{| border="0"
 
{| border="0"
−
|* '''Push''': empilha um novo dado (acrescenta-o ao topo da pilha).<br>* '''Pop''': desempilha um dado (retira-o do topo da pilha)<br>*'''Top''': acessa o dado do topo da pilha ||[[imagem:Prg-pilha.jpg|200px]]
+
|* '''Push''': empilha um novo dado (acrescenta-o ao topo da pilha).<br>* '''Pop''': desempilha um dado (retira-o do topo da pilha)<br>*'''Top''': acessa o dado do topo da pilha (sem retirá-lo) ||[[imagem:Prg-pilha.jpg|200px]]
 
|}
 
|}
  
  
−
A declaração da Pilha na biblioteca Prglib é esta:
+
'''Algumas aplicações de pilhas são:'''
 +
* [https://www.geeksforgeeks.org/expression-evaluation/ Cálculo de expressões] em diferentes representações (infix, postfix, prefix)
 +
* [https://www.geeksforgeeks.org/check-for-balanced-parentheses-in-an-expression/ Balanceamento de símbolos em expressões], tais como parênteses, chaves e outros.
 +
* Operações como ''refazer'' ou ''desfazer'' em editores e outros programas
 +
* Avançar e recuar entre páginas visitadas em navegadores web
 +
* Usada em muitos algoritmos, tais como [https://en.wikipedia.org/wiki/Tree_traversal ''travessias de árvores''] (usada, por exemplo, em procura de arquivos em diretórios), [https://en.wikipedia.org/wiki/Maze_solving_algorithm resolução de labirintos], [https://en.wikipedia.org/wiki/Sudoku_solving_algorithms resolvedor de sudoku], [https://en.wikibooks.org/wiki/Data_Structures/Stacks_and_Queues#The_Stock_Span_Problem problema do período de preços de ações]
 +
 
  
−
<syntaxhighlight lang=c>
+
Na [https://pt.wikipedia.org/wiki/Standard_Template_Library biblioteca STL] existe a estrutura de dados [http://www.cplusplus.com/reference/stack/stack/ stack], que implementa uma pilha. Suas operações elementares são estas:
−
template <typename T> class pilha : public std::stack<T> {
+
* [http://www.cplusplus.com/reference/stack/stack/push/ push]: empilha um dado
−
public:
+
* [http://www.cplusplus.com/reference/stack/stack/pop pop]: desempilha um dado
−
  // construtor: deve-se informar a capacidade da pilha
+
* [http://www.cplusplus.com/reference/stack/stack/top top]: acessa o dado que está no topo da pilha
−
  pilha(unsigned int umaCapacidade);
+
* [http://www.cplusplus.com/reference/stack/stack/empty empty]: retorna ''true'' se pilha estiver vazia
−
+
* [http://www.cplusplus.com/reference/stack/stack/size size]: retorna a quantidade de dados armazenados na pilha
−
  // construtor de cópia: cria uma pilha que é cópia de outra
 
−
  pilha(const pilha<T>& outra);
 
−
 
−
  // destrutor da pilha
 
−
  ~pilha();
 
−
 
−
  // operador de atribuição: torna esta pilha uma cópia de outra pilha
 
−
  pilha<T> & operator=(const pilha<T> & outra);
 
−
 
−
  // operações da pilha
 
−
 
−
  virtual void push(const T & dado); // empilha um dado
 
−
 
−
  T pop(); // desempilha um dado
 
−
 
−
  virtual const T& top() const; // retorna o dado do topo da pilha, sem retirá-lo
 
−
 
−
  bool vazia() const;
 
−
  bool cheia() const;
 
−
  unsigned int comprimento() const;
 
−
  void esvazia();
 
−
  unsigned int capacidade() const;
 
−
 
 
−
private:
 
−
  unsigned int N;
 
−
};
 
−
</syntaxhighlight>''Arquivo libs/pilha.h''
 
  
  
Linha 48: Linha 37:
 
#include <iostream>
 
#include <iostream>
 
#include <string>
 
#include <string>
−
#include "prglib.h"
+
#include <stack>
  
 
using namespace std;
 
using namespace std;
  
 
int main() {
 
int main() {
−
   // uma pilha com capacidade de armazenar 20 inteiros
+
   // uma pilha para armazenar inteiros
−
   prglib::pilha<int> numeros(20);
+
   stack<int> numeros;
  
 
   numeros.push(6);
 
   numeros.push(6);
Linha 61: Linha 50:
 
   numeros.push(12);
 
   numeros.push(12);
  
−
   cout << "Pilha de numeros tem comprimento=" << numeros.comprimento() << endl;
+
   cout << "Pilha de numeros tem comprimento=" << numeros.size() << endl;
 +
 
 +
  while (! numeros.empty()) {
 +
    int x = numeros.top();
 +
    numeros.pop();
  
−
  while (not numeros.vazia()) {
+
     cout << "Topo da pilha: " << x << " e o desempilhou ..." << endl;
−
     cout << "Topo da pilha: " << numeros.top() << endl;
 
−
    cout << "... desempilhou: " << numeros.pop() << endl;
 
 
   }
 
   }
  
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
 +
== Atividades ==
 +
* [[Introdução_C%2B%2B]]
 +
 +
'''Objetivo''': escrever um programa que localize um arquivo dentro de uma árvore de diretórios.
 +
 +
A busca deve iniciar em algum subdiretório a ser informado, e ela termina ao encontrar o arquivo (ou se não encontrá-lo !). Ao localizar o arquivo procurado, deve ser informado o caminho seguido até encontrá-lo. O diretório inicial e o nome do arquivo devem ser fornecidos, respectivamente, no primeiro e segundo argumentos de linha de comando.
 +
* [https://github.com/IFSC-Engtelecom-Prg2/LocalizadorDeArquivo Descrição completa do exercício]
 +
 +
 +
Para se familiarizar com pilhas, resolva estes problemas. Observe que eles estão disponibilizados no [http://github.com GitHub] (ver [[PRG29003:_Introdu%C3%A7%C3%A3o_a_Filas#Reposit.C3.B3rio_de_exerc.C3.ADcios|instruções de acesso]]):
 +
# [https://github.com/IFSC-Engtelecom-Prg2/EmpilhaCaracteres Empilhador de caracteres]
 +
# [https://github.com/IFSC-Engtelecom-Prg2/InversorLinhas Inversor das linhas de um arquivo]
 +
# [https://github.com/IFSC-Engtelecom-Prg2/CaminhosArquivos Reduzir caminhos de arquivos]
 +
# [https://github.com/IFSC-Engtelecom-Prg2/FilaComPilhas Criação de uma fila usando pilhas]

Edição atual tal como às 14h26min de 28 de fevereiro de 2020

Próxima aula


Pilhas são estruturas de dados lineares, em que os dados são retirados em ordem inversa a que foram inseridos. Esse comportamento é denominado LIFO (Last In First Out - último a entrar, primeiro a sair).


PRG2-Stack example.jpg
Algumas pilhas da vida real ...


Pilhas apresentam três operações típicas:

* Push: empilha um novo dado (acrescenta-o ao topo da pilha).
* Pop: desempilha um dado (retira-o do topo da pilha)
*Top: acessa o dado do topo da pilha (sem retirá-lo)		 Prg-pilha.jpg


Algumas aplicações de pilhas são:


Na biblioteca STL existe a estrutura de dados stack, que implementa uma pilha. Suas operações elementares são estas:

  • push: empilha um dado
  • pop: desempilha um dado
  • top: acessa o dado que está no topo da pilha
  • empty: retorna true se pilha estiver vazia
  • size: retorna a quantidade de dados armazenados na pilha


... e um exemplo de uso é mostrado a seguir: 

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main() {
  // uma pilha para armazenar inteiros
  stack<int> numeros;

  numeros.push(6);
  numeros.push(8);
  numeros.push(10);
  numeros.push(12);

  cout << "Pilha de numeros tem comprimento=" << numeros.size() << endl;

  while (! numeros.empty()) {
    int x = numeros.top();
    numeros.pop();

    cout << "Topo da pilha: " << x << " e o desempilhou ..." << endl;
  }

}

Atividades

Objetivo: escrever um programa que localize um arquivo dentro de uma árvore de diretórios.

A busca deve iniciar em algum subdiretório a ser informado, e ela termina ao encontrar o arquivo (ou se não encontrá-lo !). Ao localizar o arquivo procurado, deve ser informado o caminho seguido até encontrá-lo. O diretório inicial e o nome do arquivo devem ser fornecidos, respectivamente, no primeiro e segundo argumentos de linha de comando.


Para se familiarizar com pilhas, resolva estes problemas. Observe que eles estão disponibilizados no GitHub (ver instruções de acesso):

  1. Empilhador de caracteres
  2. Inversor das linhas de um arquivo
  3. Reduzir caminhos de arquivos
  4. Criação de uma fila usando pilhas
Disponível em “https://wiki.sj.ifsc.edu.br/index.php?title=PRG29003:_Introdução_a_Pilhas&oldid=165448”