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) de inteiros. 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 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.

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.

 

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

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

  /**
   * Nodo anterior
   */
  private Node previous;

  /**
   * Nodo posterior
   */
  private Node next;

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

    setPrevious(null);

    setNext(null);
  }

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

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

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

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

  /**
   * Configurar o nodo posterior
   *
   * @param next nodo posterior
   */
  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.exercicio08;

/**
 * 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 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.tutorial03.exercicio08;

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

  /**
   * Ultimo nodo do deque
   */
  private Node tailer;

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

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

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

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

      aux.setNext(header);

      header.setPrevious(aux);

      header = aux;
    }
  }

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

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

      aux.setPrevious(tailer);

      tailer.setNext(aux);

      tailer = aux;
    }
  }

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

    return 0;
  }

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

    return 0;
  }

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

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

      node.setNext(null);

      return node.getElement();
    }

    return 0;
  }

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

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

      node.setPrevious(null);

      return node.getElement();
    }

    return 0;
  }

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

/**
 * 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 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.tutorial03.exercicio08;

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

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

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

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

/**
 * 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 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.tutorial03.exercicio08;

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

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

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

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

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

    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 StackDoublyLinkedList();

    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);

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

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

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

  /**
   * Retornar o nodo anterior
   *
   * @return nodo anterior
   */
  Node* getPrevious() const;

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

  /**
   * Configurar o nodo anterior
   *
   * @param previous nodo anterior
   */
  void setPrevious(Node* previous);

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

  private:

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

  /**
   * Nodo anterior
   */
  Node* previous;

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

  setPrevious(NULL);

  setNext(NULL);
}

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

  previous = other.previous;

  next = other.next;
}

/**
 * Destructor
 */
Node::~Node()
{
  setPrevious(NULL);

  setNext(NULL);
}

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

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

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

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

/**
 * Configurar o nodo posterior
 *
 * @param next nodo posterior
 */
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;

  /**
   * Ultimo nodo do deque
   */
  Node* tailer;
};

#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;

  tailer = NULL;
}

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

  tailer = other.tailer;
}

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

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

    node->setNext(header);

    header->setPrevious(node);

    header = node;
  }
}

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

    tailer = header;
  }
  else
  {
    Node* node = new Node(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
 */
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())
  {
    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
 */
int Dequeue::pollFirst()
{
  int element = 0;

  if(!empty())
  {
    element = header->getElement();
    
    Node* 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
 */
int Dequeue::pollLast()
{
  int element = 0;

  if(!empty())
  {
    element = tailer->getElement();
    
    Node* 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 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.