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

Desenvolva uma classe chamada Dequeue para representar o tipo abstrato de dados deque, ou seja, onde os elementos podem ser inseridos e/ou removidos em ambas as extremidades da lista. Os elementos devem ser armazenados numa lista duplamente encadeada (doubly linked list) genérica. Estenda a classe Dequeue para implementar as classes Stack e Queue, para representar os tipos abstratos de dados pilha e fila, respectivamente (Goodrich, 2007). Forneça métodos public para cada um dos itens a seguir da classe Queue: a) inserir um elemento na fila; b) remover e retornar o elemento inserido na fila; c) retornar o elemento inserido na fila, sem removê-lo; d) retornar o número de elementos inseridos na fila; e) retornar se há ou não elementos inseridos na fila. Forneça métodos public para cada um dos itens a seguir da classe Stack: a) inserir um elemento na pilha; b) remover e retornar o elemento inserido na pilha; c) retornar o elemento inserido na pilha, sem removê-lo; d) retornar o número de elementos inseridos na pilha; e) retornar se há ou não elementos inseridos na pilha.

 

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.tutorial04.exercicio07;

/**
 * Classe responsavel pela representacao do nodo
 * 
 * @param <T> tipo generico
 */
public class Node<T>
{
  /**
   * Elemento do nodo
   */
  private T element;

  /**
   * Nodo anterior
   */
  private Node<T> previous;

  /**
   * Nodo posterior
   */
  private Node<T> next;

  /**
   * Constructor
   *
   * @param element elemento do nodo
   */
  public Node(T element)
  {
    this.element = element;

    setPrevious(null);

    setNext(null);
  }

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

  /**
   * Retornar o nodo anterior
   * 
   * @return nodo anterior
   */
  public Node<T> getPrevious()
  {
    return previous;
  }

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

  /**
   * Configurar o nodo anterior
   * 
   * @param previous nodo anterior
   */
  public void setPrevious(Node<T> previous)
  {
    this.previous = previous;
  }

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

Arquivo Dequeue.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.tutorial04.exercicio07;

/**
 * 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 o elemento especificado no inicio do deque
   *
   * @param element elemento especificado
   */
  public void offerFirst(T element);

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

  /**
   * Recuperar o primeiro elemento do deque,
   * ou retornar null se o deque estiver vazio
   *
   * @return primeiro elemento do deque, ou null se o deque estiver vazio
   */
  public T peekFirst();

  /**
   * Recuperar o ultimo elemento do deque,
   * ou retornar null se o deque estiver vazio
   *
   * @return ultimo elemento do deque, ou null se o deque estiver vazio
   */
  public T peekLast();

  /**
   * Recuperar e remover o primeiro elemento do deque,
   * ou retornar null se o deque estiver vazio
   *
   * @return primeiro elemento do deque, ou null se o deque estiver vazio
   */
  public T pollFirst();

  /**
   * Recuperar e remover o ultimo elemento do deque,
   * ou retornar null se o deque estiver vazio
   *
   * @return ultimo elemento do deque, ou null se o deque estiver vazio
   */
  public T pollLast();

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

Arquivo DequeueDoublyLinkedList.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.tutorial04.exercicio07;

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

  /**
   * Ultimo nodo do deque
   */
  private Node<T> tailer;

  /**
   * Constructor
   */
  public DequeueDoublyLinkedList()
  {
    header = null;
    
    tailer = null;
  }

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

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

      tailer = header;
    }
    else
    {
      Node<T> aux = new Node<>(element);

      aux.setNext(header);

      header.setPrevious(aux);

      header = aux;
    }
  }

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

      tailer = header;
    }
    else
    {
      Node<T> aux = new Node<>(element);

      aux.setPrevious(tailer);

      tailer.setNext(aux);

      tailer = aux;
    }
  }

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

    return null;
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial04.exercicio07.Dequeue#peekLast()
   */
  @Override
  public T peekLast()
  {
    if(!empty())
    {
      return tailer.getElement();
    }

    return null;
  }

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

      header = header.getNext();
      
      if(header != null)
      {
        header.setPrevious(null);
      }
      else
      {
        tailer = header;
      }

      node.setNext(null);

      return node.getElement();
    }

    return null;
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial04.exercicio07.Dequeue#pollLast()
   */
  @Override
  public T pollLast()
  {
    if(!empty())
    {
      Node<T> node = tailer;

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

      node.setPrevious(null);

      return node.getElement();
    }

    return null;
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial04.exercicio07.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 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.tutorial04.exercicio07;

/**
 * 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 o elemento especificado no fim da fila
   *
   * @param element elemento especificado
   */
  public void offer(T element);

  /**
   * Recuperar o elemento no inicio da fila,
   * ou retornar null se a fila estiver vazia
   *
   * @return elemento no inicio da fila, ou null se a fila estiver vazia
   */
  public T peek();

  /**
   * Recuperar e remover o elemento no inicio da fila,
   * ou retornar null se a fila estiver vazia
   *
   * @return elemento no inicio da fila, ou null se a fila estiver vazia
   */
  public T poll();

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

Arquivo QueueDoublyLinkedList.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.tutorial04.exercicio07;

/**
 * Classe responsavel pela implementacao da fila,
 * utilizando uma Doubly Linked List
 * 
 * @param <T> tipo generico
 */
public class QueueDoublyLinkedList<T> extends DequeueDoublyLinkedList<T>
  implements Queue<T>
{
  /**
   * Constructor
   */
  public QueueDoublyLinkedList()
  {
    super();
  }

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

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial04.exercicio07.Queue#peek()
   */
  @Override
  public T peek()
  {
    return peekFirst();
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial04.exercicio07.Queue#poll()
   */
  @Override
  public T poll()
  {
    return pollFirst();
  }
}

Arquivo Stack.java

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

package com.ybadoo.tutoriais.poo.tutorial04.exercicio07;

/**
 * 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,
   * ou retornar null se a pilha estiver vazia
   *
   * @return elemento no topo da pilha, ou null se a pilha estiver vazia
   */
  public T peek();

  /**
   * Recuperar e remover o elemento no topo da pilha,
   * ou retornar null se a pilha estiver vazia
   *
   * @return elemento no topo da pilha, ou null se a pilha estiver vazia
   */
  public T pop();

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

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

Arquivo StackDoublyLinkedList.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.tutorial04.exercicio07;

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

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial04.exercicio07.Stack#peek()
   */
  @Override
  public T peek()
  {
    return peekFirst();
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial04.exercicio07.Stack#pop()
   */
  @Override
  public T pop()
  {
    return pollFirst();
  }

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

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.tutorial04.exercicio07;

/**
 * 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 QueueDoublyLinkedList<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 StackDoublyLinkedList<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
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_

#include <cstdlib>

/**
 * Classe responsavel pela representacao do nodo
 * 
 * @param <T> tipo generico
 */
template <class T> class Node
{
  public:

  /**
   * Constructor
   *
   * @param element elemento do nodo
   */
  Node(const T element)
  {
    Node::element = element;
    
    setPrevious(NULL);

    setNext(NULL);
  }

  /**
   * Copy constructor
   */
  Node(const Node<T> &other)
  {
    element = other.element;
    
    previous = other.previous;

    next = other.next;
  }

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

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

  /**
   * Retornar o nodo anterior
   *
   * @return nodo anterior
   */
  Node<T>* getPrevious() const
  {
    return previous;
  }

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

  /**
   * Configurar o nodo anterior
   *
   * @param previous nodo anterior
   */
  void setPrevious(Node<T>* previous)
  {
    Node::previous = previous;
  }

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

  private:

  /**
   * Elemento do nodo
   */
  T element;

  /**
   * Nodo anterior
   */
  Node<T>* previous;

  /**
   * Nodo posterior
   */
  Node<T>* next;
};

#endif

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

#include "Node.hpp"

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

  /**
   * Constructor
   */
  Dequeue()
  {
    header = NULL;

    tailer = NULL;
  }

  /**
   * Copy constructor
   */
  Dequeue(const Dequeue<T> &other)
  {
    header = other.header;

    tailer = other.tailer;
  }

  /**
   * Destructor
   */
  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 o elemento especificado no inicio do deque
   *
   * @param element elemento especificado
   */
  void offerFirst(const T element)
  {
    if(empty())
    {
      header = new Node<T>(element);

      tailer = header;
    }
    else
    {
      Node<T>* node = new Node<T>(element);

      node->setNext(header);

      header->setPrevious(node);

      header = node;
    }
  }

  /**
   * Inserir o elemento especificado no final do deque
   *
   * @param element elemento especificado
   */
  void offerLast(const T element)
  {
    if(empty())
    {
      header = new Node<T>(element);

      tailer = header;
    }
    else
    {
      Node<T>* node = new Node<T>(element);

      node->setPrevious(tailer);

      tailer->setNext(node);

      tailer = node;
    }
  }

  /**
   * Recuperar o primeiro elemento do deque,
   * ou retornar zero se o deque estiver vazio
   *
   * @return primeiro elemento do deque, ou zero se o deque estiver vazio
   */
  T peekFirst() const
  {
    if(!empty())
    {
      return header->getElement();
    }

    return 0;
  }

  /**
   * Recuperar o ultimo elemento do deque,
   * ou retornar zero se o deque estiver vazio
   *
   * @return ultimo elemento do deque, ou zero se o deque estiver vazio
   */
  T peekLast() const
  {
    if(!empty())
    {
      return tailer->getElement();
    }

    return 0;
  }

  /**
   * Recuperar e remover o primeiro elemento do deque,
   * ou retornar zero se o deque estiver vazio
   *
   * @return primeiro elemento do deque, ou zero se o deque estiver vazio
   */
  T pollFirst()
  {
    T element = 0;

    if(!empty())
    {
      element = header->getElement();
    
      Node<T>* node = header;

      header = header->getNext();
      
      if(header != NULL)
      {
        header->setPrevious(NULL);
      }
      else
      {
        tailer = header;
      }

      node->setNext(NULL);

      free(node);
    }

    return element;
  }

  /**
   * Recuperar e remover o ultimo elemento do deque,
   * ou retornar zero se o deque estiver vazio
   *
   * @return ultimo elemento do deque, ou zero se o deque estiver vazio
   */
  T pollLast()
  {
    T element = 0;

    if(!empty())
    {
      element = tailer->getElement();
    
      Node<T>* node = tailer;

      tailer = tailer->getPrevious();
      
      if(tailer != NULL)
      {
        tailer->setNext(NULL);
      }
      else
      {
        header = tailer;
      }

      node->setPrevious(NULL);

      free(node);
    }

    return element;
  }

  /**
   * 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;

  /**
   * Ultimo nodo do deque
   */
  Node<T>* tailer;
};

#endif

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 "Dequeue.hpp"

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

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

  }

  /**
   * Destructor
   */
  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 o elemento especificado no fim da fila
   *
   * @param element elemento especificado
   */
  void offer(const T element)
  {
    Dequeue<T>::offerLast(element);
  }

  /**
   * Recuperar o elemento no inicio da fila,
   * ou retornar zero se a fila estiver vazia
   *
   * @return elemento no inicio da fila, ou zero se a fila estiver vazia
   */
  T peek() const
  {
    return Dequeue<T>::peekFirst();
  }

  /**
   * Recuperar e remover o elemento no inicio da fila,
   * ou retornar zero se a fila estiver vazia
   *
   * @return elemento no inicio da fila, ou zero se a fila estiver vazia
   */
  T poll()
  {
    return Dequeue<T>::pollFirst();
  }

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

#endif

Arquivo Stack.hpp

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

#ifndef STACK_HPP_
#define STACK_HPP_

#include "Dequeue.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,
   * ou retornar zero se a pilha estiver vazia
   *
   * @return elemento no topo da pilha, ou zero se a pilha estiver vazia
   */
  T peek() const
  {
    return Dequeue<T>::peekFirst();
  }

  /**
   * Recuperar e remover o elemento no topo da pilha,
   * ou retornar zero se a pilha estiver vazia
   *
   * @return elemento no topo da pilha, ou zero se a pilha estiver vazia
   */
  T pop()
  {
    return Dequeue<T>::pollFirst();
  }

  /**
   * Inserir o elemento especificado no topo da pilha
   *
   * @param element elemento especificado
   */
  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/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"
#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>();

  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;

  delete queue;

  cout << endl;

  cout << "Stack Test" << endl;

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

  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;

  delete stack;

  return 0;
}

Arquivo makefile

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

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

g++ -o application 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

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