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

(Goodrich, 2007) Desenvolva uma classe chamada Queue para representar o tipo abstrato de dados fila. Uma fila é uma estrutura de dados baseada no princípio FIFO, no qual o primeiro elemento inserido é o primeiro elemento retirado. A classe utiliza uma lista simplesmente encadeada de inteiros para o armazenamento dos elementos.

Uma lista simplesmente encadeada (Singly Linked List) é uma coleção de nodos (Node) que juntos formam uma ordem linear, no qual cada nodo é um objeto que armazena um elemento e uma referência, chamada next, para o próximo nodo, conforme apresentado na Figura 01.

Representação de uma lista simplesmente encadeada
Figura 01: representação de uma lista simplesmente encadeada

A classe possui um único atributo denominado header, que representa a referência para o nodo armazenado no início da fila. Os métodos especificados para o tipo abstrato de dados fila são:

  1. empty - verifica se a fila está vazia.
  2. offer - insere um novo elemento no fim da fila.
  3. peek - recupera o elemento do início da fila, ou retorna zero caso a fila esteja vazia.
  4. poll - recupera e remove o elemento do início da fila, ou retorna zero caso a fila esteja vazia.
  5. size - retorna a quantidade de elementos armazenados na fila.

 

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 Node.java Queue.java Application.java
Diagrama de Classes
Diagrama de Classes na Linguagem de Programação Java

Arquivo Node.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.exercicio38;

import java.io.Serializable;

/**
 * Nodo de uma lista simplesmente encadeada de inteiros
 */
public class Node implements Serializable
{
  /**
   * Identificador de serializacao da classe
   */
  private static final long serialVersionUID = 1L;

  /**
   * Elemento deste nodo
   */
  private int element;

  /**
   * Proximo elemento deste nodo
   */
  private Node next;

  /**
   * Criar um nodo com um dado elemento e o proximo nodo
   *
   * @param element elemento deste nodo
   * @param next proximo elemento deste nodo
   */
  public Node(int element, Node next)
  {
    this.element = element;

    this.next = next;
  }

  /**
   * Retornar o elemento deste nodo
   *
   * @return elemento deste nodo
   */
  public int getElement()
  {
    return element;
  }

  /**
   * Retornar o proximo elemento deste nodo
   *
   * @return proximo elemento deste nodo
   */
  public Node getNext()
  {
    return next;
  }

  /**
   * Configurar o proximo elemento deste nodo
   *
   * @param next proximo elemento deste nodo
   */
  public void setNext(Node next)
  {
    this.next = next;
  }
}

Arquivo Queue.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.exercicio38;

/**
 * Classe responsavel pela implementacao da fila,
 * utilizando uma lista simplesmente encadeada de inteiros
 */
public class Queue
{
  /**
   * Referencia para o nodo armazenado no inicio da fila
   */
  private Node header;

  /**
   * Construtor para inicializar a fila
   */
  public Queue()
  {
    header = null;
  }

  /**
   * Verificar se a fila esta vazia
   *
   * @return true se a fila esta vazia, false em caso contrario
   */
  public boolean empty()
  {
    return header == null;
  }

  /**
   * Inserir um novo elemento no fim da fila
   *
   * @param @param element novo elemento
   */
  public void offer(int element)
  {
    if(empty())
    {
      header = new Node(element, header);
    }
    else
    {
      Node node = header;

      while(node.getNext() != null)
      {
        node = node.getNext();
      }

      node.setNext(new Node(element, null));
    }
  }

  /**
   * Recuperar o elemento do inicio da fila,
   * ou retornar zero caso a fila esteja vazia
   *
   * @return elemento do inicio da fila, ou zero caso a fila esteja vazia
   */
  public int peek()
  {
    if(!empty())
    {
      return header.getElement();
    }

    return 0;
  }

  /**
   * Recuperar e remover o elemento do inicio da fila,
   * ou retornar zero caso a fila esteja vazia
   *
   * @return elemento do inicio da fila, ou zero caso a fila esteja vazia
   */
  public int poll()
  {
    if(!empty())
    {
      Node node = header;

      header = header.getNext();

      node.setNext(null);

      return node.getElement();
    }

    return 0;
  }

  /**
   * Retornar a quantidade de elementos na fila
   *
   * @return quantidade de elementos na fila
   */
  public int size()
  {
    Node node = header;

    int count = 0;

    while(node != null)
    {
      node = node.getNext();

      count = count + 1;
    }

    return count;
  }

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

    out.append("[");

    Node node = header;

    while(node != null)
    {
      out.append(node.getElement());

      if(node.getNext() != null)
      {
        out.append(", ");
      }

      node = node.getNext();
    }

    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.exercicio38;

import java.util.Scanner;

/**
 * Classe responsavel pela execucao da classe Queue
 */
public class Application
{
  /**
   * Construtor para inicializar a execucao da classe Queue
   */
  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);

    Queue queue = new Queue();

    int option = 0;

    System.out.println("Método : Ação");
    System.out.println("empty  : 1");
    System.out.println("peek   : 2");
    System.out.println("poll   : 3");
    System.out.println("offer  : 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  : " + queue.empty());
      }
      else if(option == 2)
      {
        System.out.println("peek   : " + queue.peek());
      }
      else if(option == 3)
      {
        System.out.println("poll   : " + queue.poll());
      }
      else if(option == 4)
      {
        System.out.print("offer  : ");

        int number = scanner.nextInt();

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

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

Arquivo Node.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 NODE_HPP_
#define NODE_HPP_

/**
 * Nodo de uma lista simplesmente encadeada de inteiros
 */
class Node
{
  public:

  /**
   * Criar um nodo com um dado elemento e o proximo nodo
   *
   * @param element elemento deste nodo
   * @param next proximo elemento deste nodo
   */
  Node(const int element, Node* next);

  /**
   * Destrutor
   */
  virtual ~Node();

  /**
   * Retornar o elemento deste nodo
   *
   * @return elemento deste nodo
   */
  int getElement() const;

  /**
   * Retornar o proximo elemento deste nodo
   *
   * @return proximo elemento deste nodo
   */
  Node* getNext() const;

  /**
   * Configurar o proximo elemento deste nodo
   *
   * @param next proximo elemento deste nodo
   */
  void setNext(Node* next);

  private:

  /**
   * Elemento deste nodo
   */
  int element;

  /**
   * Proximo elemento deste nodo
   */
  Node* next;
};

#endif

Arquivo Node.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 "Node.hpp"

/**
 * Criar um nodo com um dado elemento e o proximo nodo
 *
 * @param element elemento deste nodo
 * @param next proximo elemento deste nodo
 */
Node::Node(const int element, Node* next)
{
  Node::element = element;

  Node::next = next;
}

/**
 * Destrutor
 */
Node::~Node()
{
  next = NULL;
}

/**
 * Retornar o elemento deste nodo
 *
 * @return elemento deste nodo
 */
int Node::getElement() const
{
  return element;
}

/**
 * Retornar o proximo elemento deste nodo
 *
 * @return proximo elemento deste nodo
 */
Node* Node::getNext() const
{
  return next;
}

/**
 * Configurar o proximo elemento deste nodo
 *
 * @param next proximo elemento deste nodo
 */
void Node::setNext(Node* next)
{
  Node::next = next;
}

Arquivo Queue.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 QUEUE_HPP
#define QUEUE_HPP

#include <string>

#include "Node.hpp"

/**
 * Classe responsavel pela implementacao da fila,
 * utilizando uma lista simplesmente encadeada de inteiros
 */
class Queue
{
  public:

  /**
   * Construtor para inicializar a fila
   */
  Queue();

  /**
   * Destrutor
   */
  ~Queue();

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

  /**
   * Inserir um novo elemento no fim da fila
   *
   * @param @param element novo elemento
   */
  void offer(const int element);

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

  /**
   * Recuperar e remover o elemento do inicio da fila,
   * ou retornar zero caso a fila esteja vazia
   *
   * @return elemento do inicio da fila, ou zero caso a fila esteja vazia
   */
  int poll();

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

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

  private:

  /**
   * Referencia para o nodo armazenado no inicio da fila
   */
  Node* header;
};

#endif

Arquivo Queue.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 "Queue.hpp"

/**
 * Construtor para inicializar a fila
 */
Queue::Queue()
{
  header = NULL;
}

/**
 * Destrutor
 */
Queue::~Queue()
{
  while(header != NULL)
  {
    Node* node = header;

    header = header->getNext();

    free(node);
  }
}

/**
 * Verificar se a fila esta vazia
 *
 * @return true se a fila esta vazia, false em caso contrario
 */
bool Queue::empty() const
{
  return header == NULL;
}

/**
 * Inserir um novo elemento no fim da fila
 *
 * @param @param element novo elemento
 */
void Queue::offer(const int element)
{
  if(empty())
  {
    header = new Node(element, header);
  }
  else
  {
    Node* node = header;

    while(node->getNext() != NULL)
    {
      node = node->getNext();
    }

    node->setNext(new Node(element, NULL));
  }
}

/**
 * Recuperar o elemento do topo da fila,
 * ou retornar zero caso a fila esteja vazia
 *
 * @return elemento do topo da fila, ou zero caso a fila esteja vazia
 */
int Queue::peek() const
{
  if(!empty())
  {
    return header->getElement();
  }

  return 0;
}

/**
 * Recuperar e remover o elemento do topo da fila,
 * ou retornar zero caso a fila esteja vazia
 *
 * @return elemento do topo da fila, ou zero caso a fila esteja vazia
 */
int Queue::poll()
{
  if(!empty())
  {
    Node* node = header;

    header = header->getNext();

    int element = node->getElement();

    free(node);

    return element;
  }

  return 0;
}

/**
 * Retornar a quantidade de elementos armazenados na fila
 *
 * @return quantidade de elementos armazenados na fila
 */
int Queue::size() const
{
  Node* node = header;

  int count = 0;

  while(node != NULL)
  {
    node = node->getNext();

    count = count + 1;
  }

  return count;
}

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

  int i;

  buffer << "[";

  Node* node = header;

  while(node != NULL)
  {
    buffer << node->getElement();

    if(node->getNext() != NULL)
    {
      buffer << ", ";
    }

    node = node->getNext();
  }

  buffer << "]";

  return buffer.str();
}

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 "Queue.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 option = 0;

  int number;

  Queue* queue = new Queue();

  cout << "Método : Ação" << endl;
  cout << "empty  : 1" << endl;
  cout << "peek   : 2" << endl;
  cout << "poll   : 3" << endl;
  cout << "offer  : 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  : " << (queue->empty() ? "true" : "false") << endl;
    }
    else if(option == 2)
    {
      cout << "peek   : " << queue->peek() << endl;
    }
    else if(option == 3)
    {
      cout << "poll   : " << queue->poll() << endl;
    }
    else if(option == 4)
    {
      cout << "offer  : ";
      cin  >> number;

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

  delete queue;

  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 Node.o -c Node.cpp

g++ -o Queue.o -c Queue.cpp

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

g++ -o application Node.o Queue.o Application.o

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