Exercício 02.38

(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:

empty - verifica se a fila está vazia.
offer - insere um novo elemento no fim da fila.
peek - recupera o elemento do início da fila, ou retorna zero caso a fila esteja vazia.
poll - recupera e remove o elemento do início da fila, ou retorna zero caso a fila esteja vazia.
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

Arquivo Node.java

/*************************************************************************
 * Copyright (C) 2009/2024 - 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/2024 - 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/2024 - 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

Arquivo Node.hpp

/*************************************************************************
 * Copyright (C) 2009/2024 - 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/2024 - 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/2024 - 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/2024 - 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/2024 - 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/2024 - 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.

Tutoriais - Programação Orientada a Objetos
Tutoriais
Programação Orientada a Objetos

Simulação na Linguagem de Programação JavaScript

Terminal

Implementação nas Linguagens de Programação

Implementação na Linguagem de Programação Java

Arquivo Node.java

Arquivo Queue.java

Arquivo Application.java

Implementação na Linguagem de Programação C++

Arquivo Node.hpp

Arquivo Node.cpp

Arquivo Queue.hpp

Arquivo Queue.cpp

Arquivo Application.cpp

Arquivo makefile

Referências Bibliográficas

Tutoriais - Programação Orientada a ObjetosTutoriaisProgramação Orientada a Objetos

Exercício 02.38

Simulação na Linguagem de Programação JavaScript

Terminal

Implementação nas Linguagens de Programação

Implementação na Linguagem de Programação Java

Arquivo Node.java

Arquivo Queue.java

Arquivo Application.java

Implementação na Linguagem de Programação C++

Arquivo Node.hpp

Arquivo Node.cpp

Arquivo Queue.hpp

Arquivo Queue.cpp

Arquivo Application.cpp

Arquivo makefile

Referências Bibliográficas

Tutoriais - Programação Orientada a Objetos
Tutoriais
Programação Orientada a Objetos