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

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

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).

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)

Algumas aplicações de pilhas são:

Cálculo de expressões em diferentes representações (infix, postfix, prefix)
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 travessias de árvores (usada, por exemplo, em procura de arquivos em diretórios), resolução de labirintos, resolvedor de sudoku, problema do período de preços de ações

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

Introdução_C++

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.

Descrição completa do exercício

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

@@ Linha 1: / Linha 1: @@
+[[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).
@@ Linha 21: / Linha 24: @@
-A declaração da Pilha na [http://tele.sj.ifsc.edu.br/~msobral/prg2/Prg2.zip biblioteca Prglib] é esta:
+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:
+* [http://www.cplusplus.com/reference/stack/stack/push/ push]: empilha um dado
-<syntaxhighlight lang=c>
+* [http://www.cplusplus.com/reference/stack/stack/pop pop]: desempilha um dado
-template <typename T> class pilha {
+* [http://www.cplusplus.com/reference/stack/stack/top top]: acessa o dado que está no topo da pilha
- public:
+* [http://www.cplusplus.com/reference/stack/stack/empty empty]: retorna ''true'' se pilha estiver vazia
-  // construtor: deve-se informar a capacidade da pilha
+* [http://www.cplusplus.com/reference/stack/stack/size size]: retorna a quantidade de dados armazenados na pilha
-  pilha(unsigned int umaCapacidade);
-  // 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 63: / Linha 37: @@
 #include <iostream>
 #include <string>
-#include <prglib.h>
+#include <stack>
 using namespace std;
-using namespace prglib;
 int main() {
-   // uma pilha com capacidade de armazenar 20 inteiros
+   // uma pilha para armazenar inteiros
-   pilha<int> numeros(20);
+   stack<int> numeros;
    numeros.push(6);
@@ Linha 77: / Linha 50: @@
    numeros.push(12);
-   cout << "Pilha de numeros tem comprimento=" << numeros.comprimento() << endl;
+   cout << "Pilha de numeros tem comprimento=" << numeros.size() << endl;
-   while (not numeros.vazia()) {
+   while (! numeros.empty()) {
-     cout << "Topo da pilha: " << numeros.top() << endl;
+    int x = numeros.top();
-    cout << "... desempilhou: " << numeros.pop() << endl;
+    numeros.pop();
+     cout << "Topo da pilha: " << x << " e o desempilhou ..." << endl;
    }
@@ Linha 88: / Linha 63: @@
 == Atividades ==
+* [[Introdução_C%2B%2B]]
+'''Objetivo''': escrever um programa que localize um arquivo dentro de uma árvore de diretórios.
-* [http://tele.sj.ifsc.edu.br/~msobral/prg2/Prg2.zip Biblioteca Prglib]
+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]
-Resolva esses problemas:
+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://moodle.sj.ifsc.edu.br/mod/vpl/view.php?id=3162 Empilhador de caracteres]
+# [https://github.com/IFSC-Engtelecom-Prg2/EmpilhaCaracteres Empilhador de caracteres]
-# [https://moodle.sj.ifsc.edu.br/mod/vpl/view.php?id=3159 Inversor das linhas de um arquivo]
+# [https://github.com/IFSC-Engtelecom-Prg2/InversorLinhas Inversor das linhas de um arquivo]
-# [https://moodle.sj.ifsc.edu.br/mod/vpl/view.php?id=4197 Criação de uma pilha usando filas]
+# [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]

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

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

Atividades

Menu de navegação

Pesquisa