Ybadoo - Soluções em Software Livre
Tutoriais
Programação Orientada a Objetos

(Goodrich, 2007) Desenvolva uma classe chamada Stack para representar o tipo abstrato de dados pilha. Uma pilha é uma estrutura de dados baseada no princípio LIFO, no qual o último elemento inserido é o primeiro elemento retirado. A classe utiliza um arranjo de inteiros para o armazenamento dos elementos e possui os seguintes atributos:

  1. capacity - capacidade máxima de elementos armazenados na pilha.
  2. data - arranjo de inteiros para o armazenamento dos elementos na pilha.
  3. top - índice para o elemento armazenado no topo da pilha.

A classe possui dois construtores: o primeiro configura a capacidade máxima de elementos armazenados na pilha com o valor padrão 100, e o segundo recebe como parâmetro a capacidade máxima de elementos armazenados na pilha. Os métodos especificados para o tipo abstrato de dados pilha são:

  1. empty - verifica se a pilha está vazia.
  2. peek - recupera o elemento do topo da pilha, ou retorna zero caso a pilha esteja vazia.
  3. pop - recupera e remove o elemento do topo da pilha, ou retorna zero caso a pilha esteja vazia.
  4. push - insere um novo elemento no topo da pilha, retornando true caso o novo elemento seja inserido no topo da pilha, ou false caso a pilha esteja cheia.
  5. size - retorna a quantidade de elementos armazenados na pilha.

 

Terminal

ybadoo@server:~$ ./application
Implementação na Linguagem de Programação Java Implementação na Linguagem de Programação C++
Diagrama de Classes na Linguagem de Programação Java Stack.java Application.java
Diagrama de Classes
Diagrama de Classes na Linguagem de Programação Java

Arquivo Stack.java

/*************************************************************************
 * Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.poo.tutorial02.exercicio32;

/**
 * Classe responsavel pela implementacao da pilha,
 * utilizando um arranjo de inteiros
 */
public class Stack
{
  /**
   * Capacidade padrao de elementos armazenados na pilha
   */
  public static final int CAPACITY = 100;

  /**
   * Capacidade maxima de elementos armazenados na pilha
   */
  private int capacity;

  /**
   * Arranjo de inteiros responsavel pelo armazenamento dos elementos na
   * pilha
   */
  private int[] data;

  /**
   * Indice para o elemento armazenado no topo da pilha
   */
  private int top;

  /**
   * Construtor para inicializar a pilha
   */
  public Stack()
  {
    this(CAPACITY);
  }

  /**
   * Construtor para inicializar a capacidade maxima de elementos
   * armazenados na pilha
   *
   * @param capacity capacidade maxima de elementos armazenados na pilha
   */
  public Stack(int capacity)
  {
    if(capacity > 0)
    {
      this.capacity = capacity;
    }
    else
    {
      this.capacity = CAPACITY;
    }

    data = new int[this.capacity];

    top = -1;
  }

  /**
   * Verificar se a pilha esta vazia
   *
   * @return true se a pilha esta vazia, false em caso contrario
   */
  public boolean empty()
  {
    return top < 0;
  }

  /**
   * Recuperar o elemento do topo da pilha,
   * ou retornar zero caso a pilha esteja vazia
   *
   * @return elemento do topo da pilha, ou zero caso a pilha esteja vazia
   */
  public int peek()
  {
    if(!empty())
    {
      return data[top];
    }

    return 0;
  }

  /**
   * Recuperar e remover o elemento do topo da pilha,
   * ou retornar zero caso a pilha esteja vazia
   *
   * @return elemento do topo da pilha, ou zero caso a pilha esteja vazia
   */
  public int pop()
  {
    if(!empty())
    {
      return data[top--];
    }

    return 0;
  }

  /**
   * Inserir um novo elemento no topo da pilha
   *
   * @param @param element novo elemento
   * @return true caso o novo elemento seja inserido no topo da pilha,
   *         ou false caso a pilha esteja cheia
   */
  public boolean push(int element)
  {
    if(size() < capacity)
    {
      data[++top] = element;

      return true;
    }

    return false;
  }

  /**
   * Retornar a quantidade de elementos armazenados na pilha
   *
   * @return quantidade de elementos armazenados na pilha
   */
  public int size()
  {
    return top + 1;
  }

  /* (non-Javadoc)
   * @see java.lang.Object#toString()
   */
  @Override
  public String toString()
  {
    StringBuilder out = new StringBuilder();

    out.append("[");

    for(int i = top; i >= 0; i--)
    {
      out.append(data[i]);

      if(i != 0)
      {
        out.append(", ");
      }
    }

    out.append("]");

    return out.toString();
  }
}

Arquivo Application.java

/*************************************************************************
 * Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.poo.tutorial02.exercicio32;

import java.util.Scanner;

/**
 * Classe responsavel pela execucao da classe Stack
 */
public class Application
{
  /**
   * Construtor para inicializar a execucao da classe Stack
   */
  private Application()
  {

  }

  /**
   * Metodo principal da linguagem de programacao Java
   *
   * @param args argumentos da linha de comando (nao utilizado)
   */
  public static void main(String[] args)
  {
    Scanner scanner = new Scanner(System.in);

    System.out.print("Forneça a capacidade da pilha: ");

    int capacity = scanner.nextInt();

    Stack stack = new Stack(capacity);

    int option = 0;

    System.out.println("Método : Ação");
    System.out.println("empty  : 1");
    System.out.println("peek   : 2");
    System.out.println("pop    : 3");
    System.out.println("push   : 4");
    System.out.println("size   : 5");
    System.out.println("print  : 6");
    System.out.println("exit   : 9");

    while(option != 9)
    {
      System.out.println();
      System.out.print("Ação   : ");

      option = scanner.nextInt();

      if(option == 1)
      {
        System.out.println("empty  : " + stack.empty());
      }
      else if(option == 2)
      {
        System.out.println("peek   : " + stack.peek());
      }
      else if(option == 3)
      {
        System.out.println("pop    : " + stack.pop());
      }
      else if(option == 4)
      {
        System.out.print("push   : ");

        int number = scanner.nextInt();

        stack.push(number);
      }
      else if(option == 5)
      {
        System.out.println("size   : " + stack.size());
      }
      else if(option == 6)
      {
        System.out.println("print  : " + stack);
      }
      else if(option == 9)
      {
        System.out.println("exit");
      }
    }

    scanner.close();
  }
}
Diagrama de Classes na Linguagem de Programação C++ Stack.hpp Stack.cpp Application.cpp makefile
Diagrama de Classes
Diagrama de Classes na Linguagem de Programação C++

Arquivo Stack.hpp

/*************************************************************************
 * Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * g++ (Ubuntu 6.2.0-5ubuntu12) 6.2.0 20161005                           *
 *************************************************************************/

#ifndef STACK_HPP
#define STACK_HPP

#include <string>

/**
 * Classe responsavel pela implementacao da pilha,
 * utilizando um arranjo de inteiros
 */
class Stack
{
  public:

  /**
   * Capacidade padrao de elementos armazenados na pilha
   */
  static const int CAPACITY = 100;

  /**
   * Construtor para inicializar a pilha
   */
  Stack();

  /**
   * Construtor para inicializar a capacidade maxima de elementos
   * armazenados na pilha
   *
   * @param capacity capacidade maxima de elementos armazenados na pilha
   */
  Stack(const int capacity);

  /**
   * Destrutor
   */
  ~Stack();

  /**
   * Verificar se a pilha esta vazia
   *
   * @return true se a pilha esta vazia, false em caso contrario
   */
  bool empty() const;

  /**
   * Recuperar o elemento do topo da pilha,
   * ou retornar zero caso a pilha esteja vazia
   *
   * @return elemento do topo da pilha, ou zero caso a pilha esteja vazia
   */
  int peek() const;

  /**
   * Recuperar e remover o elemento do topo da pilha,
   * ou retornar zero caso a pilha esteja vazia
   *
   * @return elemento do topo da pilha, ou zero caso a pilha esteja vazia
   */
  int pop();

  /**
   * Inserir um novo elemento no topo da pilha
   *
   * @param @param element novo elemento
   * @return true caso o novo elemento seja inserido no topo da pilha,
   *         ou false caso a pilha esteja cheia
   */
  bool push(const int element);

  /**
   * Retornar a quantidade de elementos armazenados na pilha
   *
   * @return quantidade de elementos armazenados na pilha
   */
  int size() const;

  /*
   * Retornar a pilha no formato texto
   *
   * @return pilha no formato texto
   */
  std::string toString() const;

  private:

  /**
   * Capacidade maxima de elementos armazenados na pilha
   */
  int capacity;

  /**
   * Arranjo de inteiros responsavel pelo armazenamento dos elementos na
   * pilha
   */
  int* data;

  /**
   * Indice para o elemento armazenado no topo da pilha
   */
  int top;

  /**
   * Inicializar a pilha
   *
   * @param capacity capacidade maxima de elementos armazenados na pilha
   */
  void init(const int capacity);
};

#endif

Arquivo Stack.cpp

/*************************************************************************
 * Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * g++ (Ubuntu 6.2.0-5ubuntu12) 6.2.0 20161005                           *
 *************************************************************************/

#include <cstdlib>
#include <sstream>

#include "Stack.hpp"

/**
 * Construtor para inicializar a pilha
 */
Stack::Stack()
{
  init(CAPACITY);
}

/**
 * Construtor para inicializar a capacidade maxima de elementos
 * armazenados na pilha
 *
 * @param capacity capacidade maxima de elementos armazenados na pilha
 */
Stack::Stack(const int capacity)
{
  init(capacity);
}

/**
 * Destrutor
 */
Stack::~Stack()
{
  if(data != NULL)
  {
    free(data);
  }
}

/**
 * Verificar se a pilha esta vazia
 *
 * @return true se a pilha esta vazia, false em caso contrario
 */
bool Stack::empty() const
{
  return top < 0;
}

/**
 * Recuperar o elemento do topo da pilha,
 * ou retornar zero caso a pilha esteja vazia
 *
 * @return elemento do topo da pilha, ou zero caso a pilha esteja vazia
 */
int Stack::peek() const
{
  if(!empty())
  {
    return data[top];
  }

  return 0;
}

/**
 * Recuperar e remover o elemento do topo da pilha,
 * ou retornar zero caso a pilha esteja vazia
 *
 * @return elemento do topo da pilha, ou zero caso a pilha esteja vazia
 */
int Stack::pop()
{
  if(!empty())
  {
    return data[top--];
  }

  return 0;
}

/**
 * Inserir um novo elemento no topo da pilha
 *
 * @param @param element novo elemento
 * @return true caso o novo elemento seja inserido no topo da pilha,
 *         ou false caso a pilha esteja cheia
 */
bool Stack::push(const int element)
{
  if(size() < capacity)
  {
    data[++top] = element;

    return true;
  }

  return false;
}

/**
 * Retornar a quantidade de elementos armazenados na pilha
 *
 * @return quantidade de elementos armazenados na pilha
 */
int Stack::size() const
{
  return top + 1;
}

/*
 * Retornar a pilha no formato texto
 *
 * @return pilha no formato texto
 */
std::string Stack::toString() const
{
  std::stringstream buffer;

  int i;

  buffer << "[";

  for(i = top; i >= 0; i--)
  {
    buffer << data[i];

    if(i != 0)
    {
      buffer << ", ";
    }
  }

  buffer << "]";

  return buffer.str();
}

/**
 * Inicializar a pilha
 *
 * @param capacity capacidade maxima de elementos armazenados na pilha
 */
void Stack::init(const int capacity)
{
  if(capacity > 0)
  {
    Stack::capacity = capacity;
  }
  else
  {
    Stack::capacity = CAPACITY;
  }

  data = (int *) malloc(Stack::capacity);

  top = -1;
}

Arquivo Application.cpp

/*************************************************************************
 * Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * g++ (Ubuntu 6.2.0-5ubuntu12) 6.2.0 20161005                           *
 *************************************************************************/

#include <iostream>

#include "Stack.hpp"

/**
 * Metodo principal da linguagem de programacao C++
 *
 * @param argc quantidade de argumentos na linha de comando (nao utilizado)
 * @param argv argumentos da linha de comando (nao utilizado)
 */
int main(int argc, char** argv)
{
  using namespace std;

  int capacity;

  int option = 0;

  int number;

  cout << "Forneça a capacidade da pilha: ";
  cin  >> capacity;

  Stack* stack = new Stack(capacity);

  cout << "Método : Ação" << endl;
  cout << "empty  : 1" << endl;
  cout << "peek   : 2" << endl;
  cout << "pop    : 3" << endl;
  cout << "push   : 4" << endl;
  cout << "size   : 5" << endl;
  cout << "print  : 6" << endl;
  cout << "exit   : 9" << endl;

  while(option != 9)
  {
    cout << "\nAção   : ";
    cin  >> option;

    if(option == 1)
    {
      cout << "empty  : " << (stack->empty() ? "true" : "false") << endl;
    }
    else if(option == 2)
    {
      cout << "peek   : " << stack->peek() << endl;
    }
    else if(option == 3)
    {
      cout << "pop    : " << stack->pop() << endl;
    }
    else if(option == 4)
    {
      cout << "push   : ";
      cin  >> number;

      stack->push(number);
    }
    else if(option == 5)
    {
      cout << "size   : " << stack->size() << endl;
    }
    else if(option == 6)
    {
      cout << "print  : " << stack->toString() << endl;
    }
    else if(option == 9)
    {
      cout << "exit" << endl;
    }
  }

  delete stack;

  return 0;
}

Arquivo makefile

##########################################################################
 # Copyright (C) 2009/2018 - Cristiano Lehrer (cristiano@ybadoo.com.br)  #
 #                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  #
 #                                                                       #
 # Permission is granted to copy, distribute and/or modify this document #
 # under the terms of the GNU Free Documentation License, Version 1.3 or #
 # any later version published by the  Free Software Foundation; with no #
 # Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A #
 # A copy of the  license is included in  the section entitled "GNU Free #
 # Documentation License".                                               #
 #                                                                       #
 # Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             #
 # gcc/g++ (Ubuntu 6.2.0-5ubuntu12) 6.2.0 20161005                       #
 ##########################################################################

g++ -o Stack.o -c Stack.cpp

g++ -o Application.o -c Application.cpp

g++ -o application Stack.o Application.o

Goodrich, Michael. (2007). Estrutura de Dados e Algoritmos em Java. 4ª edição. Porto Alegre: Bookman. 600 páginas.