Tutoriais - Programação Orientada a ObjetosDesenvolva uma classe chamada Dequeue para representar o tipo abstrato de dados deque, ou seja, onde os elementos podem ser inseridos e/ou removidos em ambas as extremidades da lista. Os elementos devem ser armazenados numa lista duplamente encadeada (doubly linked list) genérica. A classe deve possuir um construtor que receba como parâmetro a quantidade máxima de elementos a serem armazenados na lista duplamente encadeada. Estenda a classe Dequeue para implementar as classes Stack e Queue, para representar os tipos abstratos de dados pilha e fila, respectivamente (Goodrich, 2007). Forneça métodos public para cada um dos itens a seguir da classe Queue: a) inserir um elemento na fila, retornando o sucesso ou a falha na operação; b) remover e retornar o elemento inserido na fila; c) retornar o elemento inserido na fila, sem removê-lo; d) retornar o número de elementos inseridos na fila; e) retornar se há ou não elementos inseridos na fila. Forneça métodos public para cada um dos itens a seguir da classe Stack: a) inserir um elemento na pilha, retornando o sucesso ou a falha na operação; b) remover e retornar o elemento inserido na pilha; c) retornar o elemento inserido na pilha, sem removê-lo; d) retornar o número de elementos inseridos na pilha; e) retornar se há ou não elementos inseridos na pilha.
/*************************************************************************
* Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br) *
* Ybadoo - Solucoes em Software Livre (ybadoo.com.br) *
* *
* Permission is granted to copy, distribute and/or modify this document *
* under the terms of the GNU Free Documentation License, Version 1.3 or *
* any later version published by the Free Software Foundation; with no *
* Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A *
* A copy of the license is included in the section entitled "GNU Free *
* Documentation License". *
* *
* Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic) *
* OpenJDK Version "1.8.0_121" *
* OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode) *
*************************************************************************/
package com.ybadoo.tutoriais.poo.tutorial04.exercicio08;
/**
* Classe responsavel pela representacao do nodo
*
* @param <T> tipo generico
*/
public class Node<T>
{
/**
* Elemento do nodo
*/
private T element;
/**
* Nodo anterior
*/
private Node<T> previous;
/**
* Nodo posterior
*/
private Node<T> next;
/**
* Constructor
*
* @param element elemento do nodo
*/
public Node(final T element)
{
this.element = element;
setPrevious(null);
setNext(null);
}
/**
* Retornar o elemento do nodo
*
* @return elemento do nodo
*/
public T getElement()
{
return element;
}
/**
* Retornar o nodo anterior
*
* @return nodo anterior
*/
public Node<T> getPrevious()
{
return previous;
}
/**
* Retornar o nodo posterior
*
* @return nodo posterior
*/
public Node<T> getNext()
{
return next;
}
/**
* Configurar o nodo anterior
*
* @param previous nodo anterior
*/
public void setPrevious(final Node<T> previous)
{
this.previous = previous;
}
/**
* Configurar o nodo posterior
*
* @param next nodo posterior
*/
public void setNext(final Node<T> next)
{
this.next = next;
}
}/*************************************************************************
* Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br) *
* Ybadoo - Solucoes em Software Livre (ybadoo.com.br) *
* *
* Permission is granted to copy, distribute and/or modify this document *
* under the terms of the GNU Free Documentation License, Version 1.3 or *
* any later version published by the Free Software Foundation; with no *
* Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A *
* A copy of the license is included in the section entitled "GNU Free *
* Documentation License". *
* *
* Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic) *
* OpenJDK Version "1.8.0_121" *
* OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode) *
*************************************************************************/
package com.ybadoo.tutoriais.poo.tutorial04.exercicio08;
/**
* Interface responsavel pela especificacao do deque
*
* @param <T> tipo generico
*/
public interface Dequeue<T>
{
/**
* Verificar se o deque esta vazio
*
* @return true se o deque esta vazio, ou false caso contrario
*/
public boolean empty();
/**
* Inserir o elemento especificado no inicio do deque
*
* @param element elemento especificado
*/
public void offerFirst(final T element);
/**
* Inserir o elemento especificado no final do deque
*
* @param element elemento especificado
*/
public void offerLast(final T element);
/**
* Recuperar o primeiro elemento do deque,
* ou retornar null se o deque estiver vazio
*
* @return primeiro elemento do deque, ou null se o deque estiver vazio
*/
public T peekFirst();
/**
* Recuperar o ultimo elemento do deque,
* ou retornar null se o deque estiver vazio
*
* @return ultimo elemento do deque, ou null se o deque estiver vazio
*/
public T peekLast();
/**
* Recuperar e remover o primeiro elemento do deque,
* ou retornar null se o deque estiver vazio
*
* @return primeiro elemento do deque, ou null se o deque estiver vazio
*/
public T pollFirst();
/**
* Recuperar e remover o ultimo elemento do deque,
* ou retornar null se o deque estiver vazio
*
* @return ultimo elemento do deque, ou null se o deque estiver vazio
*/
public T pollLast();
/**
* Retornar o numero de elementos do deque
*
* @return numero de elementos do deque
*/
public int size();
}/*************************************************************************
* Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br) *
* Ybadoo - Solucoes em Software Livre (ybadoo.com.br) *
* *
* Permission is granted to copy, distribute and/or modify this document *
* under the terms of the GNU Free Documentation License, Version 1.3 or *
* any later version published by the Free Software Foundation; with no *
* Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A *
* A copy of the license is included in the section entitled "GNU Free *
* Documentation License". *
* *
* Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic) *
* OpenJDK Version "1.8.0_121" *
* OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode) *
*************************************************************************/
package com.ybadoo.tutoriais.poo.tutorial04.exercicio08;
/**
* Classe responsavel pela implementacao do deque,
* utilizando uma Doubly Linked List
*
* @param <T> tipo generico
*/
public class DequeueDoublyLinkedList<T> implements Dequeue<T>
{
/**
* Primeiro nodo do deque
*/
private Node<T> header;
/**
* Ultimo nodo do deque
*/
private Node<T> tailer;
/**
* Limite maximo de nodos suportado
*/
private int maximum;
/**
* Inicializar o deque
*/
public DequeueDoublyLinkedList()
{
this(10);
}
/**
* Inicializar o deque
*
* @param maximum limite maximo de nodos suportado
*/
public DequeueDoublyLinkedList(final int maximum)
{
header = null;
tailer = null;
if (maximum > 0)
{
this.maximum = maximum;
}
else
{
this.maximum = 0;
}
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio08.Dequeue#empty()
*/
@Override
public boolean empty()
{
return header == null;
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio08.Dequeue#offerFirst(java.lang.Object)
*/
@Override
public void offerFirst(final T element)
{
if (empty())
{
header = new Node<>(element);
tailer = header;
}
else if (size() < maximum)
{
final Node<T> aux = new Node<>(element);
aux.setNext(header);
header.setPrevious(aux);
header = aux;
}
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio08.Dequeue#offerLast(java.lang.Object)
*/
@Override
public void offerLast(final T element)
{
if (empty())
{
header = new Node<>(element);
tailer = header;
}
else if (size() < maximum)
{
final Node<T> aux = new Node<>(element);
aux.setPrevious(tailer);
tailer.setNext(aux);
tailer = aux;
}
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio08.Dequeue#peekFirst()
*/
@Override
public T peekFirst()
{
if (!empty())
{
return header.getElement();
}
return null;
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio08.Dequeue#peekLast()
*/
@Override
public T peekLast()
{
if (!empty())
{
return tailer.getElement();
}
return null;
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio08.Dequeue#pollFirst()
*/
@Override
public T pollFirst()
{
if (!empty())
{
final Node<T> node = header;
header = header.getNext();
if (header != null)
{
header.setPrevious(null);
}
else
{
tailer = header;
}
node.setNext(null);
return node.getElement();
}
return null;
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio08.Dequeue#pollLast()
*/
@Override
public T pollLast()
{
if (!empty())
{
final Node<T> node = tailer;
tailer = tailer.getPrevious();
if (tailer != null)
{
tailer.setNext(null);
}
else
{
header = tailer;
}
node.setPrevious(null);
return node.getElement();
}
return null;
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio08.Dequeue#size()
*/
@Override
public int size()
{
Node<T> node = header;
int count = 0;
while(node != null)
{
node = node.getNext();
count = count + 1;
}
return count;
}
}/*************************************************************************
* Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br) *
* Ybadoo - Solucoes em Software Livre (ybadoo.com.br) *
* *
* Permission is granted to copy, distribute and/or modify this document *
* under the terms of the GNU Free Documentation License, Version 1.3 or *
* any later version published by the Free Software Foundation; with no *
* Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A *
* A copy of the license is included in the section entitled "GNU Free *
* Documentation License". *
* *
* Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic) *
* OpenJDK Version "1.8.0_121" *
* OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode) *
*************************************************************************/
package com.ybadoo.tutoriais.poo.tutorial04.exercicio08;
/**
* Interface responsavel pela especificacao da fila
*
* @param <T> tipo generico
*/
public interface Queue<T>
{
/**
* Verificar se a fila esta vazia
*
* @return true se a fila esta vazia, ou false caso contrario
*/
public boolean empty();
/**
* Inserir o elemento especificado no fim da fila
*
* @param element elemento especificado
*/
public void offer(final T element);
/**
* Recuperar o elemento no inicio da fila,
* ou retornar null se a fila estiver vazia
*
* @return elemento no inicio da fila, ou null se a fila estiver vazia
*/
public T peek();
/**
* Recuperar e remover o elemento no inicio da fila,
* ou retornar null se a fila estiver vazia
*
* @return elemento no inicio da fila, ou null se a fila estiver vazia
*/
public T poll();
/**
* Retornar o numero de elementos da fila
*
* @return numero de elementos da fila
*/
public int size();
}/*************************************************************************
* Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br) *
* Ybadoo - Solucoes em Software Livre (ybadoo.com.br) *
* *
* Permission is granted to copy, distribute and/or modify this document *
* under the terms of the GNU Free Documentation License, Version 1.3 or *
* any later version published by the Free Software Foundation; with no *
* Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A *
* A copy of the license is included in the section entitled "GNU Free *
* Documentation License". *
* *
* Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic) *
* OpenJDK Version "1.8.0_121" *
* OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode) *
*************************************************************************/
package com.ybadoo.tutoriais.poo.tutorial04.exercicio08;
/**
* Classe responsavel pela implementacao da fila,
* utilizando uma Doubly Linked List
*
* @param <T> tipo generico
*/
public class QueueDoublyLinkedList<T> extends DequeueDoublyLinkedList<T>
implements Queue<T>
{
/**
* Inicializar a fila
*/
public QueueDoublyLinkedList()
{
super();
}
/**
* Inicializar a fila
*
* @param maximum limite maximo de nodos suportado
*/
public QueueDoublyLinkedList(final int maximum)
{
super(maximum);
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio08.Queue#offer(java.lang.Object)
*/
@Override
public void offer(final T element)
{
offerLast(element);
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio08.Queue#peek()
*/
@Override
public T peek()
{
return peekFirst();
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio08.Queue#poll()
*/
@Override
public T poll()
{
return pollFirst();
}
}/*************************************************************************
* Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br) *
* Ybadoo - Solucoes em Software Livre (ybadoo.com.br) *
* *
* Permission is granted to copy, distribute and/or modify this document *
* under the terms of the GNU Free Documentation License, Version 1.3 or *
* any later version published by the Free Software Foundation; with no *
* Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A *
* A copy of the license is included in the section entitled "GNU Free *
* Documentation License". *
* *
* Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic) *
* OpenJDK Version "1.8.0_121" *
* OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode) *
*************************************************************************/
package com.ybadoo.tutoriais.poo.tutorial04.exercicio08;
/**
* Interface responsavel pela especificacao da pilha
*
* @param <T> tipo generico
*/
public interface Stack<T>
{
/**
* Verificar se a pilha esta vazia
*
* @return true se a pilha esta vazia, false em caso contrario
*/
public boolean empty();
/**
* Recuperar o elemento no topo da pilha,
* ou retornar null se a pilha estiver vazia
*
* @return elemento no topo da pilha, ou null se a pilha estiver vazia
*/
public T peek();
/**
* Recuperar e remover o elemento no topo da pilha,
* ou retornar null se a pilha estiver vazia
*
* @return elemento no topo da pilha, ou null se a pilha estiver vazia
*/
public T pop();
/**
* Inserir o elemento especificado no topo da pilha
*
* @param element elemento especificado
*/
public void push(final T element);
/**
* Retornar o numero de elementos na pilha
*
* @return numero de elementos na pilha
*/
public int size();
}/*************************************************************************
* Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br) *
* Ybadoo - Solucoes em Software Livre (ybadoo.com.br) *
* *
* Permission is granted to copy, distribute and/or modify this document *
* under the terms of the GNU Free Documentation License, Version 1.3 or *
* any later version published by the Free Software Foundation; with no *
* Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A *
* A copy of the license is included in the section entitled "GNU Free *
* Documentation License". *
* *
* Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic) *
* OpenJDK Version "1.8.0_121" *
* OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode) *
*************************************************************************/
package com.ybadoo.tutoriais.poo.tutorial04.exercicio08;
/**
* Classe responsavel pela implementacao da pilha,
* utilizando uma Doubly Linked List
*
* @param <T> tipo generico
*/
public class StackDoublyLinkedList<T> extends DequeueDoublyLinkedList<T>
implements Stack<T>
{
/**
* Inicializar a pilha
*/
public StackDoublyLinkedList()
{
super();
}
/**
* Inicializar a pilha
*
* @param maximum limite maximo de nodos suportado
*/
public StackDoublyLinkedList(final int maximum)
{
super(maximum);
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio08.Stack#peek()
*/
@Override
public T peek()
{
return peekFirst();
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio08.Stack#pop()
*/
@Override
public T pop()
{
return pollFirst();
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio08.Stack#push(java.lang.Object)
*/
@Override
public void push(final T element)
{
offerFirst(element);
}
}/*************************************************************************
* Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br) *
* Ybadoo - Solucoes em Software Livre (ybadoo.com.br) *
* *
* Permission is granted to copy, distribute and/or modify this document *
* under the terms of the GNU Free Documentation License, Version 1.3 or *
* any later version published by the Free Software Foundation; with no *
* Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A *
* A copy of the license is included in the section entitled "GNU Free *
* Documentation License". *
* *
* Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic) *
* OpenJDK Version "1.8.0_121" *
* OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode) *
*************************************************************************/
package com.ybadoo.tutoriais.poo.tutorial04.exercicio08;
/**
* Classe responsavel pela execucao da aplicacao
*/
public class Application
{
/**
* Construtor padrao
*/
private Application()
{
}
/**
* Metodo principal da linguagem de programacao Java
*
* @param args argumentos da linha de comando (nao utilizado)
*/
public static void main(String[] args)
{
System.out.println("Queue Test");
final Queue<Integer> queue = new QueueDoublyLinkedList<Integer>(10);
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");
final Stack<Integer> stack = new StackDoublyLinkedList<Integer>(10);
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());
}
}
/*************************************************************************
* Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br) *
* Ybadoo - Solucoes em Software Livre (ybadoo.com.br) *
* *
* Permission is granted to copy, distribute and/or modify this document *
* under the terms of the GNU Free Documentation License, Version 1.3 or *
* any later version published by the Free Software Foundation; with no *
* Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A *
* A copy of the license is included in the section entitled "GNU Free *
* Documentation License". *
* *
* Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic) *
* g++ (Ubuntu 6.2.0-5ubuntu12) 6.2.0 20161005 *
*************************************************************************/
#ifndef NODE_HPP_
#define NODE_HPP_
#include <cstdlib>
/**
* Classe responsavel pela representacao do nodo
*
* @param <T> tipo generico
*/
template <class T> class Node
{
public:
/**
* Constructor
*
* @param element elemento do nodo
*/
Node(const T element)
{
Node::element = element;
setPrevious(NULL);
setNext(NULL);
}
/**
* Copy constructor
*/
Node(const Node<T> &other)
{
element = other.element;
previous = other.previous;
next = other.next;
}
/**
* Destructor
*/
virtual ~Node()
{
setPrevious(NULL);
setNext(NULL);
}
/**
* Retornar o elemento do nodo
*
* @return elemento do nodo
*/
T getElement() const
{
return element;
}
/**
* Retornar o nodo anterior
*
* @return nodo anterior
*/
Node<T>* getPrevious() const
{
return previous;
}
/**
* Retornar o nodo posterior
*
* @return nodo posterior
*/
Node<T>* getNext() const
{
return next;
}
/**
* Configurar o nodo anterior
*
* @param previous nodo anterior
*/
void setPrevious(Node<T>* previous)
{
Node::previous = previous;
}
/**
* Configurar o nodo posterior
*
* @param next nodo posterior
*/
void setNext(Node<T>* next)
{
Node::next = next;
}
private:
/**
* Elemento do nodo
*/
T element;
/**
* Nodo anterior
*/
Node<T>* previous;
/**
* Nodo posterior
*/
Node<T>* next;
};
#endif/*************************************************************************
* Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br) *
* Ybadoo - Solucoes em Software Livre (ybadoo.com.br) *
* *
* Permission is granted to copy, distribute and/or modify this document *
* under the terms of the GNU Free Documentation License, Version 1.3 or *
* any later version published by the Free Software Foundation; with no *
* Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A *
* A copy of the license is included in the section entitled "GNU Free *
* Documentation License". *
* *
* Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic) *
* g++ (Ubuntu 6.2.0-5ubuntu12) 6.2.0 20161005 *
*************************************************************************/
#ifndef DEQUEUE_HPP_
#define DEQUEUE_HPP_
#include "Node.hpp"
/**
* Interface responsavel pela especificacao do deque
*
* @param <T> tipo generico
*/
template <class T> class Dequeue
{
public:
/**
* Inicializar o deque
*/
Dequeue()
{
header = NULL;
tailer = NULL;
maximum = 10;
}
/**
* Inicializar o deque
*
* @param maximum limite maximo de nodos suportado
*/
Dequeue(int maximum)
{
header = NULL;
tailer = NULL;
if (maximum > 0)
{
Dequeue::maximum = maximum;
}
else
{
Dequeue::maximum = 0;
}
}
/**
* Copy constructor
*/
Dequeue (const Dequeue<T> &other)
{
header = other.header;
tailer = other.tailer;
maximum = other.maximum;
}
/**
* Destructor
*/
virtual ~Dequeue()
{
while (header != NULL)
{
Node<T>* node = header;
header = header->getNext();
free(node);
}
}
/**
* Verificar se o deque esta vazio
*
* @return true (1) se o deque esta vazio, ou false (0) caso contrario
*/
bool empty() const
{
return header == NULL;
}
/**
* Retornar o numero de elementos do deque
*
* @return numero de elementos do deque
*/
int size() const
{
Node<T>* node = header;
int count = 0;
while (node != NULL)
{
node = node->getNext();
count = count + 1;
}
return count;
}
protected:
/**
* Inserir o elemento especificado no inicio do deque
*
* @param element elemento especificado
*/
void offerFirst(const T element)
{
if (empty())
{
header = new Node<T>(element);
tailer = header;
}
else if (size() < maximum)
{
Node<T>* node = new Node<T>(element);
node->setNext(header);
header->setPrevious(node);
header = node;
}
}
/**
* Inserir o elemento especificado no final do deque
*
* @param element elemento especificado
*/
void offerLast(const T element)
{
if (empty())
{
header = new Node<T>(element);
tailer = header;
}
else if (size() < maximum)
{
Node<T>* node = new Node<T>(element);
node->setPrevious(tailer);
tailer->setNext(node);
tailer = node;
}
}
/**
* Recuperar o primeiro elemento do deque,
* ou retornar zero se o deque estiver vazio
*
* @return primeiro elemento do deque, ou zero se o deque estiver vazio
*/
T peekFirst() const
{
if (!empty())
{
return header->getElement();
}
return 0;
}
/**
* Recuperar o ultimo elemento do deque,
* ou retornar zero se o deque estiver vazio
*
* @return ultimo elemento do deque, ou zero se o deque estiver vazio
*/
T peekLast() const
{
if (!empty())
{
return tailer->getElement();
}
return 0;
}
/**
* Recuperar e remover o primeiro elemento do deque,
* ou retornar zero se o deque estiver vazio
*
* @return primeiro elemento do deque, ou zero se o deque estiver vazio
*/
T pollFirst()
{
T element = 0;
if (!empty())
{
element = header->getElement();
Node<T>* node = header;
header = header->getNext();
if (header != NULL)
{
header->setPrevious(NULL);
}
else
{
tailer = header;
}
node->setNext(NULL);
free(node);
}
return element;
}
/**
* Recuperar e remover o ultimo elemento do deque,
* ou retornar zero se o deque estiver vazio
*
* @return ultimo elemento do deque, ou zero se o deque estiver vazio
*/
T pollLast()
{
T element = 0;
if (!empty())
{
element = tailer->getElement();
Node<T>* node = tailer;
tailer = tailer->getPrevious();
if (tailer != NULL)
{
tailer->setNext(NULL);
}
else
{
header = tailer;
}
node->setPrevious(NULL);
free(node);
}
return element;
}
private:
/**
* Primeiro nodo do deque
*/
Node<T>* header;
/**
* Ultimo nodo do deque
*/
Node<T>* tailer;
/**
* Limite maximo de nodos suportado
*/
int maximum;
};
#endif/*************************************************************************
* Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br) *
* Ybadoo - Solucoes em Software Livre (ybadoo.com.br) *
* *
* Permission is granted to copy, distribute and/or modify this document *
* under the terms of the GNU Free Documentation License, Version 1.3 or *
* any later version published by the Free Software Foundation; with no *
* Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A *
* A copy of the license is included in the section entitled "GNU Free *
* Documentation License". *
* *
* Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic) *
* g++ (Ubuntu 6.2.0-5ubuntu12) 6.2.0 20161005 *
*************************************************************************/
#ifndef QUEUE_HPP_
#define QUEUE_HPP_
#include "Dequeue.hpp"
/**
* Interface responsavel pela especificacao da fila
*
* @param <T> tipo generico
*/
template <class T> class Queue : private Dequeue<T>
{
public:
/**
* Inicializar a fila
*/
Queue() : Dequeue<T>()
{
}
/**
* Inicializar a fila
*
* @param maximum limite maximo de nodos suportado
*/
Queue(int maximum) : Dequeue<T>(maximum)
{
}
/**
* Destructor
*/
virtual ~Queue()
{
}
/**
* Verificar se a fila esta vazia
*
* @return true (1) se a fila esta vazia, ou false (0) caso contrario
*/
bool empty() const
{
return Dequeue<T>::empty();
}
/**
* Inserir o elemento especificado no fim da fila
*
* @param element elemento especificado
*/
void offer(const T element)
{
Dequeue<T>::offerLast(element);
}
/**
* Recuperar o elemento no inicio da fila,
* ou retornar zero se a fila estiver vazia
*
* @return elemento no inicio da fila, ou zero se a fila estiver vazia
*/
T peek() const
{
return Dequeue<T>::peekFirst();
}
/**
* Recuperar e remover o elemento no inicio da fila,
* ou retornar zero se a fila estiver vazia
*
* @return elemento no inicio da fila, ou zero se a fila estiver vazia
*/
T poll()
{
return Dequeue<T>::pollFirst();
}
/**
* Retornar o numero de elementos da fila
*
* @return numero de elementos da fila
*/
int size() const
{
return Dequeue<T>::size();
}
};
#endif/*************************************************************************
* Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br) *
* Ybadoo - Solucoes em Software Livre (ybadoo.com.br) *
* *
* Permission is granted to copy, distribute and/or modify this document *
* under the terms of the GNU Free Documentation License, Version 1.3 or *
* any later version published by the Free Software Foundation; with no *
* Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A *
* A copy of the license is included in the section entitled "GNU Free *
* Documentation License". *
* *
* Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic) *
* g++ (Ubuntu 6.2.0-5ubuntu12) 6.2.0 20161005 *
*************************************************************************/
#ifndef STACK_HPP_
#define STACK_HPP_
#include "Dequeue.hpp"
/**
* Interface responsavel pela especificacao da pilha
*
* @param <T> tipo generico
*/
template <class T> class Stack : private Dequeue<T>
{
public:
/**
* Inicializar a pilha
*/
Stack() : Dequeue<T>()
{
}
/**
* Inicializar a pilha
*
* @param maximum limite maximo de nodos suportado
*/
Stack(int maximum) : Dequeue<T>(maximum)
{
}
/**
* Destructor
*/
virtual ~Stack()
{
}
/**
* Verificar se a pilha esta vazia
*
* @return true (1) se a pilha esta vazia, false (0) em caso contrario
*/
bool empty() const
{
return Dequeue<T>::empty();
}
/**
* Recuperar o elemento no topo da pilha,
* ou retornar zero se a pilha estiver vazia
*
* @return elemento no topo da pilha, ou zero se a pilha estiver vazia
*/
T peek() const
{
return Dequeue<T>::peekFirst();
}
/**
* Recuperar e remover o elemento no topo da pilha,
* ou retornar zero se a pilha estiver vazia
*
* @return elemento no topo da pilha, ou zero se a pilha estiver vazia
*/
T pop()
{
return Dequeue<T>::pollFirst();
}
/**
* Inserir o elemento especificado no topo da pilha
*
* @param element elemento especificado
*/
void push(const T element)
{
Dequeue<T>::offerFirst(element);
}
/**
* Retornar o numero de elementos na pilha
*
* @return numero de elementos na pilha
*/
int size() const
{
return Dequeue<T>::size();
}
};
#endif/*************************************************************************
* Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br) *
* Ybadoo - Solucoes em Software Livre (ybadoo.com.br) *
* *
* Permission is granted to copy, distribute and/or modify this document *
* under the terms of the GNU Free Documentation License, Version 1.3 or *
* any later version published by the Free Software Foundation; with no *
* Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A *
* A copy of the license is included in the section entitled "GNU Free *
* Documentation License". *
* *
* Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic) *
* g++ (Ubuntu 6.2.0-5ubuntu12) 6.2.0 20161005 *
*************************************************************************/
#include <iostream>
#include "Queue.hpp"
#include "Stack.hpp"
using namespace std;
/**
* Metodo principal da linguagem de programacao C++
*
* @param argc quantidade de argumentos na linha de comando (nao utilizado)
* @param argv argumentos da linha de comando (nao utilizado)
*/
int main(int argc, char** argv)
{
cout << "Queue Test" << endl;
Queue<int>* queue = new Queue<int>(10);
cout << "empty: " << queue->empty() << endl;
cout << "offer: 9" << endl;
queue->offer(9);
cout << "empty: " << queue->empty() << endl;
cout << "poll : " << queue->poll() << endl;
cout << "offer: 8" << endl;
queue->offer(8);
cout << "peek : " << queue->peek() << endl;
cout << "offer: 7" << endl;
queue->offer(7);
cout << "offer: 6" << endl;
queue->offer(6);
cout << "size : " << queue->size() << endl;
cout << "poll : " << queue->poll() << endl;
cout << "poll : " << queue->poll() << endl;
cout << "poll : " << queue->poll() << endl;
cout << "empty: " << queue->empty() << endl;
delete queue;
cout << endl;
cout << "Stack Test" << endl;
Stack<int>* stack = new Stack<int>(10);
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;
}##########################################################################
# Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br) #
# Ybadoo - Solucoes em Software Livre (ybadoo.com.br) #
# #
# Permission is granted to copy, distribute and/or modify this document #
# under the terms of the GNU Free Documentation License, Version 1.3 or #
# any later version published by the Free Software Foundation; with no #
# Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A #
# A copy of the license is included in the section entitled "GNU Free #
# Documentation License". #
# #
# Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic) #
# gcc/g++ (Ubuntu 6.2.0-5ubuntu12) 6.2.0 20161005 #
##########################################################################
g++ -o Application.o -c Application.cpp
g++ -o application Application.oYbadoo - Soluções em Software Livre • Copyright 2009/2024 • 