Tutoriais - Programação Orientada a ObjetosImplemente o digrama de classes especificado a seguir, que especifica os tipos abstratos de dados fila (Queue) e pilha (Stack), a partir do tipo abstrato de dados deque (Dequeue), nos quais os elementos podem ser inseridos e/ou removidos em ambas as extremidades da lista (Goodrich, 2007). Os elementos devem ser armazenados numa lista encadeada simples (singly linked list) de inteiros.
Os métodos especificados para o tipo abstrato de dados deque (Dequeue) são:
empty - verificar se o deque está vazio.offerFirst - inserir o elemento especificado no início do deque.offerLast - inserir o elemento especificado no final do deque.peekFirst - recuperar o primeiro elemento do deque, ou retornar zero se o deque estiver vazio.peekLast - recuperar o último elemento do deque, ou retornar zero se o deque estiver vazio.pollFirst - recuperar e remover o primeiro elemento do deque, ou retornar zero se o deque estiver vazio.pollLast - recuperar e remover o último elemento do deque, ou retornar zero se o deque estiver vazio.size - retornar o número de elementos do deque.Os métodos especificados para o tipo abstrato de dados fila (Queue) são:
empty - verificar se a fila está vazia.offer - inserir o elemento especificado no fim da fila.peek - recuperar o elemento no início da fila, ou retornar zero se a fila estiver vazia.poll - recuperar e remover o elemento no início da fila, ou retornar zero se a fila estiver vazia.size - retornar o número de elementos da fila.Os métodos especificados para o tipo abstrato de dados pilha (Stack) são:
empty - verificar se a pilha está vazia.peek - recuperar o elemento no topo da pilha, ou retornar zero se a pilha estiver vazia.pop - recuperar e remover o elemento no topo da pilha, ou retornar zero se a pilha estiver vazia.push - inserir o elemento especificado no topo da pilha.size - retornar o número de elementos da 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.exercicio05;
/**
* Classe responsavel pela representacao do nodo
*
* @param <T> tipo generico
*/
public class Node<T>
{
/**
* Elemento do nodo
*/
private T element;
/**
* Proximo nodo
*/
private Node<T> next;
/**
* Constructor
*
* @param element elemento do nodo
*/
public Node(T element)
{
this(element, null);
}
/**
* Constructor
*
* @param element elemento do nodo
* @param next proximo nodo
*/
public Node(T element, Node<T> next)
{
this.element = element;
setNext(next);
}
/**
* Retornar o elemento do nodo
*
* @return elemento do nodo
*/
public T getElement()
{
return element;
}
/**
* Retornar o proximo nodo
*
* @return proximo nodo
*/
public Node<T> getNext()
{
return next;
}
/**
* Configurar o proximo nodo
*
* @param next proximo nodo
*/
public void setNext(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.exercicio05;
/**
* Interface responsavel pela especificacao do deque
*
* @param <T> tipo generico
*/
public interface Dequeue<T>
{
/**
* Verificar se o deque esta vazio
*
* @return true se o deque esta vazio, ou false caso contrario
*/
public boolean empty();
/**
* Inserir o elemento especificado no inicio do deque
*
* @param element elemento especificado
*/
public void offerFirst(T element);
/**
* Inserir o elemento especificado no final do deque
*
* @param element elemento especificado
*/
public void offerLast(T element);
/**
* Recuperar o primeiro elemento do deque,
* ou retornar null se o deque estiver vazio
*
* @return primeiro elemento do deque, ou null se o deque estiver vazio
*/
public T peekFirst();
/**
* Recuperar o ultimo elemento do deque,
* ou retornar null se o deque estiver vazio
*
* @return ultimo elemento do deque, ou null se o deque estiver vazio
*/
public T peekLast();
/**
* Recuperar e remover o primeiro elemento do deque,
* ou retornar null se o deque estiver vazio
*
* @return primeiro elemento do deque, ou null se o deque estiver vazio
*/
public T pollFirst();
/**
* Recuperar e remover o ultimo elemento do deque,
* ou retornar null se o deque estiver vazio
*
* @return ultimo elemento do deque, ou null se o deque estiver vazio
*/
public T pollLast();
/**
* Retornar o numero de elementos do deque
*
* @return numero de elementos do deque
*/
public int size();
}/*************************************************************************
* 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.exercicio05;
/**
* Classe responsavel pela implementacao do deque,
* utilizando uma Singly Linked List
*
* @param <T> tipo generico
*/
public class DequeueSinglyLinkedList<T> implements Dequeue<T>
{
/**
* Primeiro nodo do deque
*/
private Node<T> header;
/**
* Constructor
*/
public DequeueSinglyLinkedList()
{
header = null;
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio05.Dequeue#empty()
*/
@Override
public boolean empty()
{
return header == null;
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio05.Dequeue#offerFirst(java.lang.Object)
*/
@Override
public void offerFirst(T element)
{
if(empty())
{
header = new Node<T>(element);
}
else
{
header = new Node<T>(element, header);
}
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio05.Dequeue#offerLast(java.lang.Object)
*/
@Override
public void offerLast(T element)
{
if(empty())
{
header = new Node<T>(element);
}
else
{
Node<T> trailer = header;
while(trailer.getNext() != null)
{
trailer = trailer.getNext();
}
Node<T> node = new Node<T>(element);
trailer.setNext(node);
}
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio05.Dequeue#peekFirst()
*/
@Override
public T peekFirst()
{
if(!empty())
{
return header.getElement();
}
return null;
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio05.Dequeue#peekLast()
*/
@Override
public T peekLast()
{
if(!empty())
{
Node<T> trailer = header;
while(trailer.getNext() != null)
{
trailer = trailer.getNext();
}
return trailer.getElement();
}
return null;
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio05.Dequeue#pollFirst()
*/
@Override
public T pollFirst()
{
if(!empty())
{
Node<T> node = header;
header = header.getNext();
node.setNext(null);
return node.getElement();
}
return null;
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio05.Dequeue#pollLast()
*/
@Override
public T pollLast()
{
if(!empty())
{
Node<T> trailer = header;
Node<T> node = null;
while(trailer.getNext() != null)
{
node = trailer;
trailer = trailer.getNext();
}
if(node != null)
{
node.setNext(null);
}
else
{
header = null;
}
return trailer.getElement();
}
return null;
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio05.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.exercicio05;
/**
* Interface responsavel pela especificacao da fila
*
* @param <T> tipo generico
*/
public interface Queue<T>
{
/**
* Verificar se a fila esta vazia
*
* @return true se a fila esta vazia, ou false caso contrario
*/
public boolean empty();
/**
* Inserir o elemento especificado no fim da fila
*
* @param element elemento especificado
*/
public void offer(T element);
/**
* Recuperar o elemento no inicio da fila,
* ou retornar null se a fila estiver vazia
*
* @return elemento no inicio da fila, ou null se a fila estiver vazia
*/
public T peek();
/**
* Recuperar e remover o elemento no inicio da fila,
* ou retornar null se a fila estiver vazia
*
* @return elemento no inicio da fila, ou null se a fila estiver vazia
*/
public T poll();
/**
* Retornar o numero de elementos da fila
*
* @return numero de elementos da fila
*/
public int size();
}/*************************************************************************
* 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.exercicio05;
/**
* Classe responsavel pela implementacao da fila,
* utilizando uma Singly Linked List
*
* @param <T> tipo generico
*/
public class QueueSinglyLinkedList<T> extends DequeueSinglyLinkedList<T>
implements Queue<T>
{
/**
* Constructor
*/
public QueueSinglyLinkedList()
{
super();
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio05.Queue#offer(java.lang.Object)
*/
@Override
public void offer(T element)
{
offerLast(element);
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio05.Queue#peek()
*/
@Override
public T peek()
{
return peekFirst();
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio05.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.exercicio05;
/**
* Interface responsavel pela especificacao da pilha
*
* @param <T> tipo generico
*/
public interface Stack<T>
{
/**
* Verificar se a pilha esta vazia
*
* @return true se a pilha esta vazia, false em caso contrario
*/
public boolean empty();
/**
* Recuperar o elemento no topo da pilha,
* ou retornar null se a pilha estiver vazia
*
* @return elemento no topo da pilha, ou null se a pilha estiver vazia
*/
public T peek();
/**
* Recuperar e remover o elemento no topo da pilha,
* ou retornar null se a pilha estiver vazia
*
* @return elemento no topo da pilha, ou null se a pilha estiver vazia
*/
public T pop();
/**
* Inserir o elemento especificado no topo da pilha
*
* @param element elemento especificado
*/
public void push(T element);
/**
* Retornar o numero de elementos na pilha
*
* @return numero de elementos na pilha
*/
public int size();
}/*************************************************************************
* 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.exercicio05;
/**
* Classe responsavel pela implementacao da pilha,
* utilizando uma Singly Linked List
*
* @param <T> tipo generico
*/
public class StackSinglyLinkedList<T> extends DequeueSinglyLinkedList<T>
implements Stack<T>
{
/**
* Constructor
*/
public StackSinglyLinkedList()
{
super();
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio05.Stack#peek()
*/
@Override
public T peek()
{
return peekFirst();
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio05.Stack#pop()
*/
@Override
public T pop()
{
return pollFirst();
}
/* (non-Javadoc)
* @see com.ybadoo.tutoriais.poo.tutorial04.exercicio05.Stack#push(java.lang.Object)
*/
@Override
public void push(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.exercicio05;
/**
* Classe responsavel pela execucao da aplicacao
*/
public class Application
{
/**
* Construtor padrao
*/
private Application()
{
}
/**
* Metodo principal da linguagem de programacao Java
*
* @param args argumentos da linha de comando (nao utilizado)
*/
public static void main(String[] args)
{
System.out.println("Queue Test");
Queue<Integer> queue = new QueueSinglyLinkedList<Integer>();
System.out.println("empty: " + queue.empty());
System.out.println("offer: 9");
queue.offer(9);
System.out.println("empty: " + queue.empty());
System.out.println("poll : " + queue.poll());
System.out.println("offer: 8");
queue.offer(8);
System.out.println("peek : " + queue.peek());
System.out.println("offer: 7");
queue.offer(7);
System.out.println("offer: 6");
queue.offer(6);
System.out.println("size : " + queue.size());
System.out.println("poll : " + queue.poll());
System.out.println("poll : " + queue.poll());
System.out.println("poll : " + queue.poll());
System.out.println("empty: " + queue.empty());
System.out.println();
System.out.println("Stack Test");
Stack<Integer> stack = new StackSinglyLinkedList<Integer>();
System.out.println("empty: " + stack.empty());
System.out.println("push : 9");
stack.push(9);
System.out.println("empty: " + stack.empty());
System.out.println("pop : " + stack.pop());
System.out.println("push : 8");
stack.push(8);
System.out.println("peek : " + stack.peek());
System.out.println("push : 7");
stack.push(7);
System.out.println("push : 6");
stack.push(6);
System.out.println("size : " + stack.size());
System.out.println("pop : " + stack.pop());
System.out.println("pop : " + stack.pop());
System.out.println("pop : " + stack.pop());
System.out.println("empty: " + stack.empty());
}
}
/*************************************************************************
* 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;
setNext(NULL);
}
/**
* Constructor
*
* @param element elemento do nodo
* @param next proximo nodo
*/
Node(const T element, Node<T>* next)
{
Node::element = element;
setNext(next);
}
/**
* Copy constructor
*/
Node(const Node<T> &other)
{
element = other.element;
next = other.next;
}
/**
* Destructor
*/
virtual ~Node()
{
setNext(NULL);
}
/**
* Retornar o elemento do nodo
*
* @return elemento do nodo
*/
T getElement() const
{
return element;
}
/**
* Retornar o proximo nodo
*
* @return proximo nodo
*/
Node<T>* getNext() const
{
return next;
}
/**
* Configurar o proximo nodo
*
* @param next proximo nodo
*/
void setNext(Node<T>* next)
{
Node::next = next;
}
private:
/**
* Elemento do nodo
*/
T element;
/**
* Proximo nodo
*/
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:
/**
* Constructor
*/
Dequeue()
{
header = NULL;
}
/**
* Copy constructor
*/
Dequeue(const Dequeue<T> &other)
{
header = other.header;
}
/**
* Destructor
*/
virtual ~Dequeue()
{
while(header != NULL)
{
Node<T>* node = header;
header = header->getNext();
free(node);
}
}
/**
* Verificar se o deque esta vazio
*
* @return true (1) se o deque esta vazio, ou false (0) caso contrario
*/
bool empty() const
{
return header == NULL;
}
/**
* Inserir o elemento especificado no inicio do deque
*
* @param element elemento especificado
*/
void offerFirst(const T element)
{
if(empty())
{
header = new Node<T>(element);
}
else
{
header = new Node<T>(element, header);
}
}
/**
* Inserir o elemento especificado no final do deque
*
* @param element elemento especificado
*/
void offerLast(const T element)
{
if(empty())
{
header = new Node<T>(element);
}
else
{
Node<T>* trailer = header;
while(trailer->getNext() != NULL)
{
trailer = trailer->getNext();
}
Node<T>* node = new Node<T>(element);
trailer->setNext(node);
}
}
/**
* Recuperar o primeiro elemento do deque,
* 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())
{
Node<T>* 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
*/
T pollFirst()
{
T element = 0;
if(!empty())
{
Node<T>* 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
*/
T pollLast()
{
T element = 0;
if(!empty())
{
Node<T>* trailer = header;
Node<T>* 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 size() const
{
Node<T>* node = header;
int count = 0;
while(node != NULL)
{
node = node->getNext();
count = count + 1;
}
return count;
}
private:
/**
* Primeiro nodo do deque
*/
Node<T>* header;
};
#endif/*************************************************************************
* 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:
/**
* Constructor
*/
Queue() : Dequeue<T>()
{
}
/**
* Destructor
*/
virtual ~Queue()
{
}
/**
* Verificar se a fila esta vazia
*
* @return true (1) se a fila esta vazia, ou false (0) caso contrario
*/
bool empty() const
{
return Dequeue<T>::empty();
}
/**
* Inserir o elemento especificado no fim da fila
*
* @param element elemento especificado
*/
void offer(const T element)
{
Dequeue<T>::offerLast(element);
}
/**
* Recuperar o elemento no inicio da fila,
* ou retornar zero se a fila estiver vazia
*
* @return elemento no inicio da fila, ou zero se a fila estiver vazia
*/
T peek() const
{
return Dequeue<T>::peekFirst();
}
/**
* Recuperar e remover o elemento no inicio da fila,
* ou retornar zero se a fila estiver vazia
*
* @return elemento no inicio da fila, ou zero se a fila estiver vazia
*/
T poll()
{
return Dequeue<T>::pollFirst();
}
/**
* Retornar o numero de elementos da fila
*
* @return numero de elementos da fila
*/
int size() const
{
return Dequeue<T>::size();
}
};
#endif/*************************************************************************
* 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:
/**
* Constructor
*/
Stack() : Dequeue<T>()
{
}
/**
* Destructor
*/
virtual ~Stack()
{
}
/**
* Verificar se a pilha esta vazia
*
* @return true (1) se a pilha esta vazia, false (0) em caso contrario
*/
bool empty() const
{
return Dequeue<T>::empty();
}
/**
* Recuperar o elemento no topo da pilha,
* ou retornar zero se a pilha estiver vazia
*
* @return elemento no topo da pilha, ou zero se a pilha estiver vazia
*/
T peek() const
{
return Dequeue<T>::peekFirst();
}
/**
* Recuperar e remover o elemento no topo da pilha,
* ou retornar zero se a pilha estiver vazia
*
* @return elemento no topo da pilha, ou zero se a pilha estiver vazia
*/
T pop()
{
return Dequeue<T>::pollFirst();
}
/**
* Inserir o elemento especificado no topo da pilha
*
* @param element elemento especificado
*/
void push(const T element)
{
Dequeue<T>::offerFirst(element);
}
/**
* Retornar o numero de elementos na pilha
*
* @return numero de elementos na pilha
*/
int size() const
{
return Dequeue<T>::size();
}
};
#endif/*************************************************************************
* 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>();
cout << "empty: " << queue->empty() << endl;
cout << "offer: 9" << endl;
queue->offer(9);
cout << "empty: " << queue->empty() << endl;
cout << "poll : " << queue->poll() << endl;
cout << "offer: 8" << endl;
queue->offer(8);
cout << "peek : " << queue->peek() << endl;
cout << "offer: 7" << endl;
queue->offer(7);
cout << "offer: 6" << endl;
queue->offer(6);
cout << "size : " << queue->size() << endl;
cout << "poll : " << queue->poll() << endl;
cout << "poll : " << queue->poll() << endl;
cout << "poll : " << queue->poll() << endl;
cout << "empty: " << queue->empty() << endl;
delete queue;
cout << endl;
cout << "Stack Test" << endl;
Stack<int>* stack = new Stack<int>();
cout << "empty: " << stack->empty() << endl;
cout << "push : 9" << endl;
stack->push(9);
cout << "empty: " << stack->empty() << endl;
cout << "pop : " << stack->pop() << endl;
cout << "push : 8" << endl;
stack->push(8);
cout << "peek : " << stack->peek() << endl;
cout << "push : 7" << endl;
stack->push(7);
cout << "push : 6" << endl;
stack->push(6);
cout << "size : " << stack->size() << endl;
cout << "pop : " << stack->pop() << endl;
cout << "pop : " << stack->pop() << endl;
cout << "pop : " << stack->pop() << endl;
cout << "empty: " << stack->empty() << endl;
delete stack;
return 0;
}##########################################################################
# 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.oGoodrich, Michael. (2007). Estrutura de Dados e Algoritmos em Java. 4ª edição. Porto Alegre: Bookman. 600 páginas.
Ybadoo - Soluções em Software Livre • Copyright 2009/2024 • 