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) 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:
Forneça métodos public para cada um dos itens a seguir da classe Queue:
/*************************************************************************
* 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.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;
}
}/*************************************************************************
* 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.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();
}/*************************************************************************
* 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.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;
}
}/*************************************************************************
* 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.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();
}/*************************************************************************
* 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.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();
}
}/*************************************************************************
* 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.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();
}/*************************************************************************
* 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.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);
}
}/*************************************************************************
* 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.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());
}
}
/*************************************************************************
* 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_
/**
* 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/*************************************************************************
* 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 <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;
}/*************************************************************************
* 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
*/
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/*************************************************************************
* 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 <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;
}/*************************************************************************
* 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
*/
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/*************************************************************************
* 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 <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();
}/*************************************************************************
* 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
*/
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/*************************************************************************
* 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 <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();
}/*************************************************************************
* 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* 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;
}##########################################################################
# 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 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.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 • 