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 encadeada (singly linked list) de inteiros. Estenda a classe Dequeue para implementar as classes Queue e Stack, para representar os tipos abstratos de dados fila e pilha, respectivamente (Goodrich, 2007).

Forneça métodos public para cada um dos itens a seguir da classe Queue:

  1. inserir um elemento na fila;
  2. remover e retornar o elemento inserido na fila;
  3. retornar o elemento inserido na fila, sem removê-lo;
  4. retornar o número de elementos inseridos na fila;
  5. 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:

  1. inserir um elemento na pilha;
  2. remover e retornar o elemento inserido na pilha;
  3. retornar o elemento inserido na pilha, sem removê-lo;
  4. retornar o número de elementos inseridos na pilha;
  5. 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.tutorial03.exercicio06;

/**
 * Classe responsavel pela representacao do nodo
 */
public class Node
{
  /**
   * Elemento do nodo
   */
  private int element;

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

  /**
   * Constructor
   *
   * @param element elemento do nodo
   */
  public Node(int element)
  {
    this(element, null);
  }

  /**
   * Constructor
   *
   * @param element elemento do nodo
   * @param next proximo nodo
   */
  public Node(int element, Node next)
  {
    this.element = element;

    setNext(next);
  }

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

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

  /**
   * Configurar o proximo nodo
   *
   * @param next proximo nodo
   */
  public void setNext(Node 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.tutorial03.exercicio06;

/**
 * Interface responsavel pela especificacao do deque
 */
public interface Dequeue
{
  /**
   * 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(int element);

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

  /**
   * 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
   */
  public int peekFirst();

  /**
   * 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
   */
  public int peekLast();

  /**
   * 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
   */
  public int pollFirst();

  /**
   * 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
   */
  public int pollLast();

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

Arquivo DequeueSinglyLinkedList.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.tutorial03.exercicio06;

/**
 * Classe responsavel pela implementacao do deque,
 * utilizando uma Singly Linked List
 */
public class DequeueSinglyLinkedList implements Dequeue
{
  /**
   * Primeiro nodo do deque
   */
  private Node header;

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

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

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial03.exercicio06.Dequeue#offerFirst(int)
   */
  @Override
  public void offerFirst(int element)
  {
    if(empty())
    {
      header = new Node(element);
    }
    else
    {
      header = new Node(element, header);
    }
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial03.exercicio06.Dequeue#offerLast(int)
   */
  @Override
  public void offerLast(int element)
  {
    if(empty())
    {
      header = new Node(element);
    }
    else
    {
      Node trailer = header;

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

      Node node = new Node(element);

      trailer.setNext(node);
    }
  }

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

    return 0;
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial03.exercicio06.Dequeue#peekLast()
   */
  @Override
  public int peekLast()
  {
    if(!empty())
    {
      Node trailer = header;

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

      return trailer.getElement();
    }

    return 0;
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial03.exercicio06.Dequeue#pollFirst()
   */
  @Override
  public int pollFirst()
  {
    if(!empty())
    {
      Node node = header;

      header = header.getNext();

      node.setNext(null);

      return node.getElement();
    }

    return 0;
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial03.exercicio06.Dequeue#pollLast()
   */
  @Override
  public int pollLast()
  {
    if(!empty())
    {
      Node trailer = header;

      Node node = null;

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

        trailer = trailer.getNext();
      }

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

      return trailer.getElement();
    }

    return 0;
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial03.exercicio06.Dequeue#size()
   */
  @Override
  public int size()
  {
    Node 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.tutorial03.exercicio06;

/**
 * Interface responsavel pela especificacao da fila
 */
public interface Queue
{
  /**
   * 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(int 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
   */
  public int peek();

  /**
   * 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
   */
  public int poll();

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

Arquivo QueueSinglyLinkedList.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.tutorial03.exercicio06;

/**
 * Classe responsavel pela implementacao da fila,
 * utilizando uma Singly Linked List
 */
public class QueueSinglyLinkedList extends DequeueSinglyLinkedList
  implements Queue
{
  /**
   * Constructor
   */
  public QueueSinglyLinkedList()
  {
    super();
  }

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial03.exercicio06.Queue#offer(int)
   */
  @Override
  public void offer(int element)
  {
    offerLast(element);
  }

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

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial03.exercicio06.Queue#poll()
   */
  @Override
  public int 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.tutorial03.exercicio06;

/**
 * Interface responsavel pela especificacao da pilha
 */
public interface Stack
{
  /**
   * 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 zero se a pilha estiver vazia
   *
   * @return elemento no topo da pilha, ou zero se a pilha estiver vazia
   */
  public int peek();

  /**
   * 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
   */
  public int pop();

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

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

Arquivo StackSinglyLinkedList.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.tutorial03.exercicio06;

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

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

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

  /* (non-Javadoc)
   * @see com.ybadoo.tutoriais.poo.tutorial03.exercicio06.Stack#push(int)
   */
  @Override
  public void push(int 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.tutorial03.exercicio06;

/**
 * Classe responsavel pela execucao da aplicacao
 */
public class Application
{
  /**
   * Constructor
   */
  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 queue = new QueueSinglyLinkedList();

    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 stack = new StackSinglyLinkedList();

    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_

/**
 * Classe responsavel pela representacao do nodo
 */
class Node
{
  public:

  /**
   * Constructor
   *
   * @param element elemento do nodo
   */
  Node(const int element);

  /**
   * Constructor
   *
   * @param element elemento do nodo
   * @param next proximo nodo
   */
  Node(const int element, Node* next);

  /**
   * Copy constructor
   */
  Node(const Node &other);

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

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

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

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

  private:

  /**
   * Elemento do nodo
   */
  int element;

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

#endif

Arquivo Node.cpp

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

#include <cstdlib>

#include "Node.hpp"

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

  setNext(NULL);
}

/**
 * Constructor
 *
 * @param element elemento do nodo
 * @param next proximo nodo
 */
Node::Node(const int element, Node* next)
{
  Node::element = element;

  setNext(next);
}

/**
 * Copy constructor
 */
Node::Node(const Node &other)
{
  element = other.element;

  next = other.next;
}

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

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

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

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

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
 */
class Dequeue
{
  public:

  /**
   * Constructor
   */
  Dequeue();

  /**
   * Copy constructor
   */
  Dequeue(const Dequeue &other);

  /**
   * Destructor
   */
  virtual ~Dequeue();

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

  /**
   * Inserir o elemento especificado no inicio do deque
   *
   * @param element elemento especificado
   */
  void offerFirst(const int element);

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

  /**
   * 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
   */
  int peekFirst() const;

  /**
   * 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
   */
  int peekLast() const;

  /**
   * 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
   */
  int pollFirst();

  /**
   * 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
   */
  int pollLast();

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

  private:

  /**
   * Primeiro nodo do deque
   */
  Node* header;
};

#endif

Arquivo Dequeue.cpp

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

#include <cstdlib>

#include "Dequeue.hpp"

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

/**
 * Copy constructor
 */
Dequeue::Dequeue(const Dequeue &other)
{
  header = other.header;
}

/**
 * Destructor
 */
Dequeue::~Dequeue()
{
  while(header != NULL)
  {
    Node* 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 Dequeue::empty() const
{
  return header == NULL;
}

/**
 * Inserir o elemento especificado no inicio do deque
 *
 * @param element elemento especificado
 */
void Dequeue::offerFirst(const int element)
{
  if(empty())
  {
    header = new Node(element);
  }
  else
  {
    header = new Node(element, header);
  }
}

/**
 * Inserir o elemento especificado no final do deque
 *
 * @param element elemento especificado
 */
void Dequeue::offerLast(const int element)
{
  if(empty())
  {
    header = new Node(element);
  }
  else
  {
    Node* trailer = header;

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

    Node* node = new Node(element);

    trailer->setNext(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
 */
int Dequeue::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
 */
int Dequeue::peekLast() const
{
  if(!empty())
  {
    Node* trailer = header;

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

    return trailer->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
 */
int Dequeue::pollFirst()
{
  int element = 0;

  if(!empty())
  {
    Node* node = header;

    header = header->getNext();

    element = node->getElement();

    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
 */
int Dequeue::pollLast()
{
  int element = 0;

  if(!empty())
  {
    Node* trailer = header;

    Node* node = NULL;

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

      trailer = trailer->getNext();
    }

    node->setNext(NULL);

    element = trailer->getElement();

    free(trailer);
  }

  return element;
}

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

  int count = 0;

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

    count = count + 1;
  }

  return count;
}

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
 */
class Queue : private Dequeue
{
  public:

  /**
   * Constructor
   */
  Queue();

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

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

  /**
   * 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
   */
  int poll();

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

#endif

Arquivo Queue.cpp

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

#include <cstdlib>

#include "Queue.hpp"

/**
 * Constructor
 */
Queue::Queue() : Dequeue()
{

}

/**
 * Destructor
 */
Queue::~Queue()
{

}

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

/**
 * Inserir o elemento especificado no fim da fila
 *
 * @param element elemento especificado
 */
void Queue::offer(const int element)
{
  Dequeue::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
 */
int Queue::peek() const
{
  return Dequeue::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
 */
int Queue::poll()
{
  return Dequeue::pollFirst();
}

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

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
 */
class Stack : private Dequeue
{
  public:

  /**
   * Constructor
   */
  Stack();

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

  /**
   * 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
   */
  int peek() const;

  /**
   * 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
   */
  int pop();

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

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

#endif

Arquivo Stack.cpp

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

#include <cstdlib>

#include "Stack.hpp"

/**
 * Constructor
 */
Stack::Stack() : Dequeue()
{

}

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

}

/**
 * Verificar se a pilha esta vazia
 *
 * @return true (1) se a pilha esta vazia, false (0) em caso contrario
 */
bool Stack::empty() const
{
  return Dequeue::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
 */
int Stack::peek() const
{
  return Dequeue::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
 */
int Stack::pop()
{
  return Dequeue::pollFirst();
}

/**
 * Inserir o elemento especificado no topo da pilha
 *
 * @param element elemento especificado
 */
void Stack::push(const int element)
{
  Dequeue::offerFirst(element);
}

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

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* queue = new Queue();

  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* stack = new Stack();

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

g++ -o Dequeue.o -c Dequeue.cpp

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

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

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

g++ -o application Node.o Dequeue.o Queue.o Stack.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

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