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

Implemente o diagrama de classes apresentado a seguir, que especifica os tipos abstratos de dados fila (Queue) e pilha (Stack) a partir do tipo abstrato de dados deque (Dequeue), que armazena os elementos numa lista simplesmente encadeada de tipos genéricos (generics).

Conforme Goodrich (2007), uma lista simplesmente encadeada é uma coleção de nodos que juntos formam uma ordem linear, no qual cada nodo (Node) é um objeto que armazena uma referência para um elemento e uma referência, chamada next, para o próximo nodo, conforme apresentado na Figura 01. O primeiro nodo de uma lista simplesmente encadeada é normalmente chamada de cabeça (header).

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

O tipo abstrato de dados deque (Dequeue) é uma estrutura de dados similar a uma fila, mas nos quais os elementos podem ser inseridos e/ou removidos em ambas as extremidades da lista (Goodrich, 2007). Os métodos especificados para o tipo abstrato de dados deque (Dequeue) são:

  1. empty - verificar se o deque está vazio.
  2. offerFirst - inserir um novo elemento no início do deque.
  3. offerLast - inserir um novo elemento no final do deque.
  4. peekFirst - recuperar o primeiro elemento do deque, ou lançar a exceção EmptyDequeueException se o deque estiver vazio.
  5. peekLast - recuperar o último elemento do deque, ou lançar a exceção EmptyDequeueException se o deque estiver vazio.
  6. pollFirst - recuperar e remover o primeiro elemento do deque, ou lançar a exceção EmptyDequeueException se o deque estiver vazio.
  7. pollLast - recuperar e remover o último elemento do deque, ou lançar a exceção EmptyDequeueException se o deque estiver vazio.
  8. size - retornar o número de elementos do deque.

Conforme Deitel (2003), o tipo abstrato de dados fila (Queue) é semelhante a uma fila de caixa em um supermercado - a primeira pessoa na fila é atendida primeiro e os outros clientes entram na fila apenas no final e esperam ser atendidos. Os nodos da fila são removidos apenas do início (ou cabeça) da fila e são inseridos somente no final (ou cauda) da fila. Por essa razão, trata-se uma fila como uma estrutura de dados primeiro a entrar, primeiro a sair (first-in, first-out - FIFO). Os métodos especificados para o tipo abstrato de dados fila (Queue) são:

  1. empty - verificar se a fila está vazia.
  2. offer - inserir um novo elemento no fim da fila.
  3. peek - recuperar o elemento no início da fila, ou lançar a exceção EmptyQueueException se a fila estiver vazia.
  4. poll - recuperar e remover o elemento no início da fila, ou lançar a exceção EmptyQueueException se a fila estiver vazia.
  5. size - retornar o número de elementos da fila.

Conforme Deitel (2003), o tipo abstrato de dados pilha (Stack) é uma versão limitada de uma lista simplesmente encadeada - novos nodos podem ser adicionados a uma pilha e removidos de uma pilha apenas na parte superior (topo). Por essa razão, a pilha é conhecida como uma estrutura de dados último a entrar, primeiro a sair (last-in, first-out - LIFO). Os métodos especificados para o tipo abstrato de dados pilha (Stack) são:

  1. empty - verificar se a pilha está vazia.
  2. peek - recuperar o elemento no topo da pilha, ou lançar a exceção EmptyStackException se a pilha estiver vazia.
  3. pop - recuperar e remover o elemento no topo da pilha, ou lançar a exceção EmptyStackException se a pilha estiver vazia.
  4. push - inserir um novo elemento no topo da pilha.
  5. size - retornar o número de elementos da pilha.

 

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 EmptyDequeueException.java Dequeue.java DequeueSinglyLinkedList.java EmptyQueueException.java Queue.java QueueSinglyLinkedList.java EmptyStackException.java Stack.java StackSinglyLinkedList.java Application.java Saída da Implementação na Linguagem de Programação Java
Diagrama de Classes
Diagrama de Classes na Linguagem de Programação 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.tutorial05.exercicio28;

import java.io.Serializable;

/**
 * Nodo de uma lista simplesmente encadeada de tipos genericos
 * 
 * @param <T> tipo generico
 */
public class Node<T> implements Serializable
{
  /**
   * Identificador de serializacao da classe
   */
  private static final long serialVersionUID = 1L;

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

  /**
   * Proximo elemento deste nodo
   */
  private Node<T> next;

  /**
   * Criar um nodo com um dado elemento
   *
   * @param element elemento deste nodo
   */
  public Node(T element)
  {
    this(element, null);
  }

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

    setNext(next);
  }

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

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

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

Arquivo EmptyDequeueException.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.tutorial05.exercicio28;

/**
 * Excecao lancada pela classe Dequeue para indicar que o deque esta vazio
 */
public class EmptyDequeueException extends RuntimeException
{
  /**
   * Identificador de serializacao da classe
   */
  private static final long serialVersionUID = 1L;
  
  /**
   * Construtor padrao 
   */
  public EmptyDequeueException()
  {
    super();
  }
  
  /**
   * Construtor para inicializar a mensagem de erro
   *
   * @param message mensagem de erro
   */
  public EmptyDequeueException(String message)
  {
    super(message);
  }
  
  /**
   * Construtor para inicializar a mensagem de erro e a causa do erro
   * 
   * @param message mensagem de erro
   * @param cause causa do erro
   */
  public EmptyDequeueException(String message, Throwable cause)
  {
    super(message, cause);
  }
  
  /**
   * Construtor para inicializar a mensagem de erro, a causa do erro,
   * a supressao e o rastreamento da pilha
   * 
   * @param message mensagem de erro
   * @param cause causa do erro
   * @param enableSuppression se a supressao esta ativada ou desativada
   * @param writableStackTrace se o rastreamento da pilha deve ser gravavel
   */
  public EmptyDequeueException(String message, Throwable cause,
    boolean enableSuppression, boolean writableStackTrace)
  {
    super(message, cause, enableSuppression, writableStackTrace);
  }
  
  /**
   * Construtor para inicializar a causa do erro
   * 
   * @param cause causa do erro
   */
  public EmptyDequeueException(Throwable cause)
  {
    super(cause);
  }
}

Arquivo Dequeue.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.tutorial05.exercicio28;

/**
 * Interface responsavel pela especificacao do deque
 * 
 * @param <T> tipo generico
 */
public interface Dequeue<T>
{
  /**
   * Verificar se o deque esta vazio
   *
   * @return true se o deque esta vazio, ou false caso contrario
   */
  public boolean empty();

  /**
   * Inserir um novo elemento no inicio do deque
   *
   * @param element novo elemento
   */
  public void offerFirst(T element);

  /**
   * Inserir um novo elemento no final do deque
   *
   * @param element novo elemento
   */
  public void offerLast(T element);

  /**
   * Recuperar o primeiro elemento do deque
   *
   * @return primeiro elemento do deque
   * @throws EmptyDequeueException o deque esta vazio
   */
  public T peekFirst() throws EmptyDequeueException;

  /**
   * Recuperar o ultimo elemento do deque
   *
   * @return ultimo elemento do deque
   * @throws EmptyDequeueException o deque esta vazio
   */
  public T peekLast() throws EmptyDequeueException;

  /**
   * Recuperar e remover o primeiro elemento do deque
   *
   * @return primeiro elemento do deque
   * @throws EmptyDequeueException o deque esta vazio
   */
  public T pollFirst() throws EmptyDequeueException;

  /**
   * Recuperar e remover o ultimo elemento do deque
   *
   * @return ultimo elemento do deque
   * @throws EmptyDequeueException o deque esta vazio
   */
  public T pollLast() throws EmptyDequeueException;

  /**
   * Retornar o numero de elementos do deque
   *
   * @return numero de elementos do deque
   */
  public int size();
}

Arquivo DequeueSinglyLinkedList.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.tutorial05.exercicio28;

/**
 * Classe responsavel pela implementacao do deque,
 * utilizando uma Singly Linked List
 * 
 * @param <T> tipo generico
 */
public class DequeueSinglyLinkedList<T> implements Dequeue<T>
{
  /**
   * Primeiro nodo do deque
   */
  private Node<T> header;

  /**
   * Construtor padrao
   */
  public DequeueSinglyLinkedList()
  {
    header = null;
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial05.exercicio28.Dequeue#empty()
   */
  @Override
  public boolean empty()
  {
    return header == null;
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial05.exercicio28.Dequeue#offerFirst(java.lang.Object)
   */
  @Override
  public void offerFirst(T element)
  {
    if(empty())
    {
      header = new Node<T>(element);
    }
    else
    {
      header = new Node<T>(element, header);
    }
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial05.exercicio28.Dequeue#offerLast(java.lang.Object)
   */
  @Override
  public void offerLast(T element)
  {
    if(empty())
    {
      header = new Node<T>(element);
    }
    else
    {
      Node<T> trailer = header;

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

      Node<T> node = new Node<T>(element);

      trailer.setNext(node);
    }
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial05.exercicio28.Dequeue#peekFirst()
   */
  @Override
  public T peekFirst() throws EmptyDequeueException
  {
    if(!empty())
    {
      return header.getElement();
    }

    throw new EmptyDequeueException();
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial05.exercicio28.Dequeue#peekLast()
   */
  @Override
  public T peekLast() throws EmptyDequeueException
  {
    if(!empty())
    {
      Node<T> trailer = header;

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

      return trailer.getElement();
    }

    throw new EmptyDequeueException();
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial05.exercicio28.Dequeue#pollFirst()
   */
  @Override
  public T pollFirst() throws EmptyDequeueException
  {
    if(!empty())
    {
      Node<T> node = header;

      header = header.getNext();

      node.setNext(null);

      return node.getElement();
    }

    throw new EmptyDequeueException();
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial05.exercicio28.Dequeue#pollLast()
   */
  @Override
  public T pollLast() throws EmptyDequeueException
  {
    if(!empty())
    {
      Node<T> trailer = header;

      Node<T> node = null;

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

        trailer = trailer.getNext();
      }

      if(node != null)
      {
        node.setNext(null);
      }
      else
      {
        header = null;
      }

      return trailer.getElement();
    }

    throw new EmptyDequeueException();
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial05.exercicio28.Dequeue#size()
   */
  @Override
  public int size()
  {
    Node<T> node = header;

    int count = 0;

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

      count = count + 1;
    }

    return count;
  }
}

Arquivo EmptyQueueException.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.tutorial05.exercicio28;

/**
 * Excecao lancada pela classe Queue para indicar que a fila esta vazia
 */
public class EmptyQueueException extends RuntimeException
{
  /**
   * Identificador de serializacao da classe
   */
  private static final long serialVersionUID = 1L;
  
  /**
   * Construtor padrao 
   */
  public EmptyQueueException()
  {
    super();
  }
  
  /**
   * Construtor para inicializar a mensagem de erro
   *
   * @param message mensagem de erro
   */
  public EmptyQueueException(String message)
  {
    super(message);
  }
  
  /**
   * Construtor para inicializar a mensagem de erro e a causa do erro
   * 
   * @param message mensagem de erro
   * @param cause causa do erro
   */
  public EmptyQueueException(String message, Throwable cause)
  {
    super(message, cause);
  }
  
  /**
   * Construtor para inicializar a mensagem de erro, a causa do erro,
   * a supressao e o rastreamento da pilha
   * 
   * @param message mensagem de erro
   * @param cause causa do erro
   * @param enableSuppression se a supressao esta ativada ou desativada
   * @param writableStackTrace se o rastreamento da pilha deve ser gravavel
   */
  public EmptyQueueException(String message, Throwable cause,
    boolean enableSuppression, boolean writableStackTrace)
  {
    super(message, cause, enableSuppression, writableStackTrace);
  }
  
  /**
   * Construtor para inicializar a causa do erro
   * 
   * @param cause causa do erro
   */
  public EmptyQueueException(Throwable cause)
  {
    super(cause);
  }
}

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.tutorial05.exercicio28;

/**
 * Interface responsavel pela especificacao da fila
 * 
 * @param <T> tipo generico
 */
public interface Queue<T>
{
  /**
   * Verificar se a fila esta vazia
   *
   * @return true se a fila esta vazia, ou false caso contrario
   */
  public boolean empty();

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

  /**
   * Recuperar o elemento no inicio da fila
   *
   * @return elemento no inicio da fila
   * @throws EmptyQueueException a fila esta vazia
   */
  public T peek() throws EmptyQueueException;

  /**
   * Recuperar e remover o elemento no inicio da fila
   *
   * @return elemento no inicio da fila
   * @throws EmptyQueueException a fila esta vazia
   */
  public T poll() throws EmptyQueueException;

  /**
   * Retornar o numero de elementos da fila
   *
   * @return numero de elementos da fila
   */
  public int size();
}

Arquivo QueueSinglyLinkedList.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.tutorial05.exercicio28;

/**
 * Classe responsavel pela implementacao da fila,
 * utilizando uma Singly Linked List
 * 
 * @param <T> tipo generico
 */
public class QueueSinglyLinkedList<T> extends DequeueSinglyLinkedList<T>
  implements Queue<T>
{
  /**
   * Construtor padrao
   */
  public QueueSinglyLinkedList()
  {
    super();
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial05.exercicio28.Queue#offer(java.lang.Object)
   */
  @Override
  public void offer(T element)
  {
    offerLast(element);
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial05.exercicio28.Queue#peek()
   */
  @Override
  public T peek() throws EmptyQueueException
  {
    try
    {
      return peekFirst();
    }
    catch(EmptyDequeueException exception)
    {
      throw new EmptyQueueException(exception);
    }
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial05.exercicio28.Queue#poll()
   */
  @Override
  public T poll() throws EmptyQueueException
  {
    try
    {
      return pollFirst();
    }
    catch(EmptyDequeueException exception)
    {
      throw new EmptyQueueException(exception);
    }
  }
}

Arquivo EmptyStackException.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.tutorial05.exercicio28;

/**
 * Excecao lancada pela classe Stack para indicar que a pilha esta vazia
 */
public class EmptyStackException extends RuntimeException
{
  /**
   * Identificador de serializacao da classe
   */
  private static final long serialVersionUID = 1L;
  
  /**
   * Construtor padrao 
   */
  public EmptyStackException()
  {
    super();
  }
  
  /**
   * Construtor para inicializar a mensagem de erro
   *
   * @param message mensagem de erro
   */
  public EmptyStackException(String message)
  {
    super(message);
  }
  
  /**
   * Construtor para inicializar a mensagem de erro e a causa do erro
   * 
   * @param message mensagem de erro
   * @param cause causa do erro
   */
  public EmptyStackException(String message, Throwable cause)
  {
    super(message, cause);
  }
  
  /**
   * Construtor para inicializar a mensagem de erro, a causa do erro,
   * a supressao e o rastreamento da pilha
   * 
   * @param message mensagem de erro
   * @param cause causa do erro
   * @param enableSuppression se a supressao esta ativada ou desativada
   * @param writableStackTrace se o rastreamento da pilha deve ser gravavel
   */
  public EmptyStackException(String message, Throwable cause,
    boolean enableSuppression, boolean writableStackTrace)
  {
    super(message, cause, enableSuppression, writableStackTrace);
  }
  
  /**
   * Construtor para inicializar a causa do erro
   * 
   * @param cause causa do erro
   */
  public EmptyStackException(Throwable cause)
  {
    super(cause);
  }
}

Arquivo Stack.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.tutorial05.exercicio28;

/**
 * Interface responsavel pela especificacao da pilha
 * 
 * @param <T> tipo generico
 */
public interface Stack<T>
{
  /**
   * Verificar se a pilha esta vazia
   *
   * @return true se a pilha esta vazia, false em caso contrario
   */
  public boolean empty();

  /**
   * Recuperar o elemento no topo da pilha
   *
   * @return elemento no topo da pilha
   * @throws EmptyStackException a pilha esta vazia
   */
  public T peek() throws EmptyStackException;

  /**
   * Recuperar e remover o elemento no topo da pilha
   *
   * @return elemento no topo da pilha
   * @throws EmptyStackException a pilha esta vazia
   */
  public T pop() throws EmptyStackException;

  /**
   * Inserir um novo elemento no topo da pilha
   *
   * @param element novo elemento
   */
  public void push(T element);

  /**
   * Retornar o numero de elementos na pilha
   *
   * @return numero de elementos na pilha
   */
  public int size();
}

Arquivo StackSinglyLinkedList.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.tutorial05.exercicio28;

/**
 * Classe responsavel pela implementacao da pilha,
 * utilizando uma Singly Linked List
 * 
 * @param <T> tipo generico
 */
public class StackSinglyLinkedList<T> extends DequeueSinglyLinkedList<T>
  implements Stack<T>
{
  /**
   * Constructor
   */
  public StackSinglyLinkedList()
  {
    super();
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial05.exercicio28.Stack#peek()
   */
  @Override
  public T peek() throws EmptyStackException
  {
    try
    {
      return peekFirst();
    }
    catch(EmptyDequeueException exception)
    {
      throw new EmptyStackException(exception);
    }
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial05.exercicio28.Stack#pop()
   */
  @Override
  public T pop() throws EmptyStackException
  {
    try
    {
      return pollFirst();
    }
    catch(EmptyDequeueException exception)
    {
      throw new EmptyStackException(exception);
    }
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial05.exercicio28.Stack#push(java.lang.Object)
   */
  @Override
  public void push(T element)
  {
    offerFirst(element);
  }
}

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.tutorial05.exercicio28;

/**
 * Classe responsavel pela execucao da aplicacao
 */
public class Application
{
  /**
   * Construtor padrao
   */
  private Application()
  {

  }

  /**
   * Metodo principal da linguagem de programacao Java
   *
   * @param args argumentos da linha de comando (nao utilizado)
   */
  public static void main(String[] args)
  {
    System.out.println("Queue Test");

    Queue<Integer> queue = new QueueSinglyLinkedList<Integer>();

    System.out.println("empty: " + queue.empty());

    System.out.println("offer: 9");
    queue.offer(9);

    System.out.println("empty: " + queue.empty());

    System.out.println("poll : " + queue.poll());

    System.out.println("offer: 8");
    queue.offer(8);

    System.out.println("peek : " + queue.peek());

    System.out.println("offer: 7");
    queue.offer(7);

    System.out.println("offer: 6");
    queue.offer(6);

    System.out.println("size : " + queue.size());

    System.out.println("poll : " + queue.poll());

    System.out.println("poll : " + queue.poll());

    System.out.println("poll : " + queue.poll());

    System.out.println("empty: " + queue.empty());

    System.out.println();

    System.out.println("Stack Test");

    Stack<Integer> stack = new StackSinglyLinkedList<Integer>();

    System.out.println("empty: " + stack.empty());

    System.out.println("push : 9");
    stack.push(9);

    System.out.println("empty: " + stack.empty());

    System.out.println("pop  : " + stack.pop());

    System.out.println("push : 8");
    stack.push(8);

    System.out.println("peek : " + stack.peek());

    System.out.println("push : 7");
    stack.push(7);

    System.out.println("push : 6");
    stack.push(6);

    System.out.println("size : " + stack.size());

    System.out.println("pop  : " + stack.pop());

    System.out.println("pop  : " + stack.pop());

    System.out.println("pop  : " + stack.pop());

    System.out.println("empty: " + stack.empty());
  }
}

Saída da Implementação na Linguagem de Programação Java

Queue Test
empty: true
offer: 9
empty: false
poll : 9
offer: 8
peek : 8
offer: 7
offer: 6
size : 3
poll : 8
poll : 7
poll : 6
empty: true

Stack Test
empty: true
push : 9
empty: false
pop  : 9
push : 8
peek : 8
push : 7
push : 6
size : 3
pop  : 6
pop  : 7
pop  : 8
empty: true
Diagrama de Classes na Linguagem de Programação C++ Exception.hpp Exception.cpp Node.hpp EmptyDequeueException.hpp EmptyDequeueException.cpp Dequeue.hpp EmptyQueueException.hpp EmptyQueueException.cpp Queue.hpp EmptyStackException.hpp EmptyStackException.cpp Stack.hpp Application.cpp makefile Saída da Implementação na Linguagem de Programação C++
Diagrama de Classes
Diagrama de Classes na Linguagem de Programação C++

Arquivo Exception.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                           *
 *************************************************************************/

#include <string>

#ifndef EXCEPTION_HPP
#define EXCEPTION_HPP

/**
 * Excecao padrao
 */
class Exception
{
  public:

  /**
   * Construtor padrao
   */
  Exception();

  /**
   * Construtor para inicializar a mensagem de erro
   *
   * @param message mensagem de erro
   */
  Exception(std::string message);

  /**
   * Retornar a mensagem de erro
   *
   * @return mensagem de erro
   */
  std::string getMessage();

  private:

  /**
   * Mensagem de erro
   */
  std::string message;
};

#endif

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

/**
 * Construtor padrao
 */
Exception::Exception()
{
  message = '\0';
}

/**
 * Construtor para inicializar a mensagem de erro
 *
 * @param message mensagem de erro
 */
Exception::Exception(std::string message)
{
  Exception::message = message;
}

/**
 * Retornar a mensagem de erro
 *
 * @return mensagem de erro
 */
std::string Exception::getMessage()
{
  return message;
}

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_

#include <cstdlib>

/**
 * Nodo de uma lista simplesmente encadeada de tipos genericos
 * 
 * @param <T> tipo generico
 */
template <class T> class Node
{
  public:

  /**
   * Criar um nodo com um dado elemento
   *
   * @param element elemento deste nodo
   */
  Node(const T element)
  {
    Node::element = element;

    setNext(NULL);
  }

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

    setNext(next);
  }

  /**
   * Construtor por copia
   */
  Node(const Node<T> &other)
  {
    element = other.element;

    next = other.next;
  }

  /**
   * Destrutor
   */
  virtual ~Node()
  {
    setNext(NULL);
  }

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

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

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

  private:

  /**
   * Elemento deste nodo
   */
  T element;

  /**
   * Proximo elemento deste nodo
   */
  Node<T>* next;
};

#endif

Arquivo EmptyDequeueException.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                           *
 *************************************************************************/

#include "Exception.hpp"

#ifndef EMPTYDEQUEUEEXCEPTION_HPP
#define EMPTYDEQUEUEEXCEPTION_HPP

/**
 * Excecao lancada pela classe Dequeue para indicar que o deque esta vazio
 */
class EmptyDequeueException : public Exception
{
  public:

  /**
   * Construtor padrao
   */
  EmptyDequeueException();

  /**
   * Construtor para inicializar a mensagem de erro
   *
   * @param message mensagem de erro
   */
  EmptyDequeueException(std::string message);
};

#endif

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

/**
 * Construtor padrao
 */
EmptyDequeueException::EmptyDequeueException()
                      :Exception()
{

}

/**
 * Construtor para inicializar a mensagem de erro
 *
 * @param message mensagem de erro
 */
EmptyDequeueException::EmptyDequeueException(std::string message)
                      :Exception(message)
{

}

Arquivo Dequeue.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 DEQUEUE_HPP_
#define DEQUEUE_HPP_

#include "EmptyDequeueException.hpp"
#include "Node.hpp"

/**
 * Interface responsavel pela especificacao do deque
 * 
 * @param <T> tipo generico
 */
template <class T> class Dequeue
{
  public:

  /**
   * Construtor padrao
   */
  Dequeue()
  {
    header = NULL;
  }

  /**
   * Construtor por copia
   */
  Dequeue(const Dequeue<T> &other)
  {
    header = other.header;
  }

  /**
   * Destrutor
   */
  virtual ~Dequeue()
  {
    while(header != NULL)
    {
      Node<T>* node = header;

      header = header->getNext();

      free(node);
    }
  }

  /**
   * Verificar se o deque esta vazio
   *
   * @return true (1) se o deque esta vazio, ou false (0) caso contrario
   */
  bool empty() const
  {
    return header == NULL;
  }

  /**
   * Inserir um novo elemento no inicio do deque
   *
   * @param element novo elemento
   */
  void offerFirst(const T element)
  {
    if(empty())
    {
      header = new Node<T>(element);
    }
    else
    {
      header = new Node<T>(element, header);
    }
  }

  /**
   * Inserir um novo elemento no final do deque
   *
   * @param element novo elemento
   */
  void offerLast(const T element)
  {
    if(empty())
    {
      header = new Node<T>(element);
    }
    else
    {
      Node<T>* trailer = header;

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

      Node<T>* node = new Node<T>(element);

      trailer->setNext(node);
    }
  }

  /**
   * Recuperar o primeiro elemento do deque
   *
   * @return primeiro elemento do deque
   * @throws EmptyDequeueException o deque esta vazio
   */
  T peekFirst() const throw (EmptyDequeueException)
  {
    if(!empty())
    {
      return header->getElement();
    }

    throw EmptyDequeueException();
  }

  /**
   * Recuperar o ultimo elemento do deque
   *
   * @return ultimo elemento do deque
   * @throws EmptyDequeueException o deque esta vazio
   */
  T peekLast() const throw (EmptyDequeueException)
  {
    if(!empty())
    {
      Node<T>* trailer = header;

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

      return trailer->getElement();
    }

    throw EmptyDequeueException();
  }

  /**
   * Recuperar e remover o primeiro elemento do deque
   *
   * @return primeiro elemento do deque
   * @throws EmptyDequeueException o deque esta vazio
   */
  T pollFirst() throw (EmptyDequeueException)
  {
    if(!empty())
    {
      Node<T>* node = header;

      header = header->getNext();

      T element = node->getElement();

      free(node);

      return element;
    }

    throw EmptyDequeueException();
  }

  /**
   * Recuperar e remover o ultimo elemento do deque
   *
   * @return ultimo elemento do deque
   * @throws EmptyDequeueException o deque esta vazio
   */
  T pollLast() throw (EmptyDequeueException)
  {
    if(!empty())
    {
      Node<T>* trailer = header;

      Node<T>* node = NULL;

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

        trailer = trailer->getNext();
      }

      node->setNext(NULL);

      T element = trailer->getElement();

      free(trailer);

      return element;
    }

    throw EmptyDequeueException();
  }

  /**
   * Retornar o numero de elementos do deque
   *
   * @return numero de elementos do deque
   */
  int size() const
  {
    Node<T>* node = header;

    int count = 0;

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

      count = count + 1;
    }

    return count;
  }

  private:

  /**
   * Primeiro nodo do deque
   */
  Node<T>* header;
};

#endif

Arquivo EmptyQueueException.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                           *
 *************************************************************************/

#include "Exception.hpp"

#ifndef EMPTYQUEUEEXCEPTION_HPP
#define EMPTYQUEUEEXCEPTION_HPP

/**
 * Excecao lancada pela classe Queue para indicar que a fila esta vazia
 */
class EmptyQueueException : public Exception
{
  public:

  /**
   * Construtor padrao
   */
  EmptyQueueException();

  /**
   * Construtor para inicializar a mensagem de erro
   *
   * @param message mensagem de erro
   */
  EmptyQueueException(std::string message);
};

#endif

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

/**
 * Construtor padrao
 */
EmptyQueueException::EmptyQueueException()
                    :Exception()
{

}

/**
 * Construtor para inicializar a mensagem de erro
 *
 * @param message mensagem de erro
 */
EmptyQueueException::EmptyQueueException(std::string message)
                    :Exception(message)
{

}

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 "Dequeue.hpp"
#include "EmptyDequeueException.hpp"
#include "EmptyQueueException.hpp"

/**
 * Interface responsavel pela especificacao da fila
 * 
 * @param <T> tipo generico
 */
template <class T> class Queue : private Dequeue<T>
{
  public:

  /**
   * Construtor padrao
   */
  Queue() : Dequeue<T>()
  {

  }

  /**
   * Destrutor
   */
  virtual ~Queue()
  {

  }

  /**
   * Verificar se a fila esta vazia
   *
   * @return true (1) se a fila esta vazia, ou false (0) caso contrario
   */
  bool empty() const
  {
    return Dequeue<T>::empty();
  }

  /**
   * Inserir um novo elemento no fim da fila
   *
   * @param element novo elemento
   */
  void offer(const T element)
  {
    Dequeue<T>::offerLast(element);
  }

  /**
   * Recuperar o elemento no inicio da fila
   *
   * @return elemento no inicio da fila
   * @throws EmptyQueueException a fila esta vazia
   */
  T peek() const throw (EmptyQueueException)
  {
    try
    {
      return Dequeue<T>::peekFirst();
    }
    catch(EmptyDequeueException exception)
    {
      throw EmptyQueueException();
    }
  }

  /**
   * Recuperar e remover o elemento no inicio da fila
   *
   * @return elemento no inicio da fila
   * @throws EmptyQueueException a fila esta vazia
   */
  T poll() throw (EmptyQueueException)
  {
    try
    {
      return Dequeue<T>::pollFirst();
    }
    catch(EmptyDequeueException exception)
    {
      throw EmptyQueueException();
    }
  }

  /**
   * Retornar o numero de elementos da fila
   *
   * @return numero de elementos da fila
   */
  int size() const
  {
    return Dequeue<T>::size();
  }
};

#endif

Arquivo EmptyStackException.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                           *
 *************************************************************************/

#include "Exception.hpp"

#ifndef EMPTYSTACKEXCEPTION_HPP
#define EMPTYSTACKEXCEPTION_HPP

/**
 * Excecao lancada pela classe Stack para indicar que a pilha esta vazia
 */
class EmptyStackException : public Exception
{
  public:

  /**
   * Construtor padrao
   */
  EmptyStackException();

  /**
   * Construtor para inicializar a mensagem de erro
   *
   * @param message mensagem de erro
   */
  EmptyStackException(std::string message);
};

#endif

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

/**
 * Construtor padrao
 */
EmptyStackException::EmptyStackException()
                    :Exception()
{

}

/**
 * Construtor para inicializar a mensagem de erro
 *
 * @param message mensagem de erro
 */
EmptyStackException::EmptyStackException(std::string message)
                    :Exception(message)
{

}

Arquivo Stack.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 STACK_HPP_
#define STACK_HPP_

#include "Dequeue.hpp"
#include "EmptyDequeueException.hpp"
#include "EmptyStackException.hpp"

/**
 * Interface responsavel pela especificacao da pilha
 * 
 * @param <T> tipo generico
 */
template <class T> class Stack : private Dequeue<T>
{
  public:

  /**
   * Constructor
   */
  Stack() : Dequeue<T>()
  {

  }

  /**
   * Destructor
   */
  virtual ~Stack()
  {

  }

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

  /**
   * Recuperar o elemento no topo da pilha
   *
   * @return elemento no topo da pilha
   * @throws EmptyStackException a pilha esta vazia
   */
  T peek() const throw (EmptyStackException)
  {
    try
    {
      return Dequeue<T>::peekFirst();
    }
    catch(EmptyDequeueException exception)
    {
      throw EmptyStackException();
    }
  }

  /**
   * Recuperar e remover o elemento no topo da pilha
   *
   * @return elemento no topo da pilha
   * @throws EmptyStackException a pilha esta vazia
   */
  T pop() throw (EmptyStackException)
  {
    try
    {
      return Dequeue<T>::pollFirst();
    }
    catch(EmptyDequeueException exception)
    {
      throw EmptyStackException();
    }
  }

  /**
   * Inserir um novo elemento no topo da pilha
   *
   * @param element novo elemento
   */
  void push(const T element)
  {
    Dequeue<T>::offerFirst(element);
  }

  /**
   * Retornar o numero de elementos na pilha
   *
   * @return numero de elementos na pilha
   */
  int size() const
  {
    return Dequeue<T>::size();
  }
};

#endif

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 "EmptyQueueException.hpp"
#include "EmptyStackException.hpp"
#include "Queue.hpp"
#include "Stack.hpp"

using namespace std;

/**
 * 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)
{
  cout << "Queue Test" << endl;

  Queue<int>* queue = new Queue<int>();

  try
  {
    cout << "empty: " << queue->empty() << endl;

    cout << "offer: 9" << endl;
    queue->offer(9);

    cout << "empty: " << queue->empty() << endl;

    cout << "poll : " << queue->poll() << endl;

    cout << "offer: 8" << endl;
    queue->offer(8);

    cout << "peek : " << queue->peek() << endl;

    cout << "offer: 7" << endl;
    queue->offer(7);

    cout << "offer: 6" << endl;
    queue->offer(6);

    cout << "size : " << queue->size() << endl;

    cout << "poll : " << queue->poll() << endl;

    cout << "poll : " << queue->poll() << endl;

    cout << "poll : " << queue->poll() << endl;

    cout << "empty: " << queue->empty() << endl;
  }
  catch(EmptyQueueException exception)
  {
    cerr << "EmptyQueueException" << endl;
  }

  delete queue;

  cout << endl;

  cout << "Stack Test" << endl;

  Stack<int>* stack = new Stack<int>();

  try
  {
    cout << "empty: " << stack->empty() << endl;

    cout << "push : 9" << endl;
    stack->push(9);

    cout << "empty: " << stack->empty() << endl;

    cout << "pop  : " << stack->pop() << endl;

    cout << "push : 8" << endl;
    stack->push(8);

    cout << "peek : " << stack->peek() << endl;

    cout << "push : 7" << endl;
    stack->push(7);

    cout << "push : 6" << endl;
    stack->push(6);

    cout << "size : " << stack->size() << endl;

    cout << "pop  : " << stack->pop() << endl;

    cout << "pop  : " << stack->pop() << endl;

    cout << "pop  : " << stack->pop() << endl;

    cout << "empty: " << stack->empty() << endl;
  }
  catch(EmptyStackException exception)
  {
    cerr << "EmptyStackException" << endl;
  }

  delete stack;

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

g++ -o EmptyDequeueException.o -c EmptyDequeueException.cpp

g++ -o EmptyQueueException.o -c EmptyQueueException.cpp

g++ -o EmptyStackException.o -c EmptyStackException.cpp

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

g++ -o application Exception.o EmptyDequeueException.o EmptyQueueException.o EmptyStackException.o Application.o

Saída da Implementação na Linguagem de Programação C++

Queue Test
empty: 1
offer: 9
empty: 0
poll : 9
offer: 8
peek : 8
offer: 7
offer: 6
size : 3
poll : 8
poll : 7
poll : 6
empty: 1

Stack Test
empty: 1
push : 9
empty: 0
pop  : 9
push : 8
peek : 8
push : 7
push : 6
size : 3
pop  : 6
pop  : 7
pop  : 8
empty: 1

Deitel, H. M. (2003). Java, como programar. 4ª edição. Porto Alegre: Bookman. 1.386 páginas.

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