Pilhas

Livro de Sedgewick e Wayne: sec.1.3, p.120.  Website do livro: resumo sec.1.3, slides.  Veja também a página algs4.cs.​princeton.edu/​code/, que tem o código fonte, a documentação, e dados de teste de todos os programas do livro.

O conceito de pilha já é bem conhecido do leitor.  Esta página examina o conceito como exemplo de ADT (e aproveita para introduzir alguns recursos da linguagem Java).

Resumo:

Pré-requisitos:

Pilha (= stack) e sua API

Exemplo de cliente

Pilha implementada em vetor com redimensionamento

Exercícios 1

  1. Implemente o método size().
  2. Prove que o vetor a[] está sempre 25% cheio. (Antes, é preciso formular essa afirmação de maneira mais precisa.)
  3. Redimensionamento.  Antes de cada push e cada pop, é verdade que a.length é potência de 2?  É verdade que a.length ≥ 2?  É verdade que a.length/4 ≤ N ≤ a.length?  Pode acontecer a.length/4 == N? Que acontece se N for 0 no começo de um pop?
  4. Escreva um programa que leia linhas de texto da entrada padrão (ignore as linhas vazias) e coloque as linhas em ordem alfabética.  As linhas de texto têm comprimento arbitrário e o número de linhas é arbitrário.  Sugestões: Use o método readLine da classe StdIn de SW.  Use redirecionamento da entrada para ler os dados de um arquivo (= file) e não do teclado.  Construa um vetor de strings usando redimensionamento.  Use o método java.util.Arrays.sort() para colocar o vetor em ordem lexicográfica. Depois, repita os testes usando Insertion.sort(), Merge.sort(), e Quick.sort().

Pilha implementada em lista ligada

Exercícios 2

  1. Escreva um método size() para a classe StackL. Há duas maneiras de fazer isso, uma ansiosa (eager) e outra preguiçosa (lazy).  A maneira ansiosa consiste em manter uma variável de instância N e atualizar o seu valor a cada push() e cada pop(). A maneira preguiçosa consiste em calcular o tamanho da lista diretamente.  Escreva uma versão preguiçosa em estilo recursivo.
  2. O método main() da classe StackL imprime o número de elementos que sobraram na pilha no fim do teste. Modifique o método de modo a imprimir o conteúdo da pilha no fim do teste. Teste o código modificado.
  3. (SW 1.3.19, p.164)  Exercício sobre listas ligadas, sem relação direta com pilhas.  Escreva um método recursivo que remova último nó de uma lista ligada cujo primeiro nó é first. Que coisa o método deveria devolver? Pense!

Perguntas e respostas

Valid CSS! Valid HTML 4.01 Strict