Definição Pilhas Filas Implementação Java

Yüklə 446 b.

tarix	18.04.2018
ölçüsü	446 b.
	#39094

Definição

Definição

Pilhas
Filas

Implementação Java
Implementação C++

Implementação Java

Implementação Java

Fundamentos
Pilhas

Implementação por arrays
Implementação por listas encadeadas

Filas

Implementação por arrays
Implementação por listas encadeadas

Implementação C++

Fundamentos
Pilhas

Implementação por arrays
Implementação por listas encadeadas

Filas

Implementação por arrays
Implementação por listas encadeadas

Pilha é o mais simples dos containers.

Pilha é o mais simples dos containers.
A operação de inclusão de elementos na pilha recebe o nome de empilhamento (push) e a operação de exclusão recebe o nome de desempilhamento (pop)
Um elemento empilhado vai ocupar a posição chamada de topo da pilha
Uma operação de desempilhamento provoca a exclusão do elemento no topo da pilha. Por esta razão as pilhas são chamadas de listas LIFO ( de “Last In First Out’).
Uma operação de desempilhamento em uma pilha vazia não tem sentido e configura uma situação denominada “underflow”
Pode-se verificar se uma pilha atingir a condição de contorno de pilha vazia através da função isEmpty que pode assumir os valores TRUE (pilha vazia) ou FALSE (pilha não vazia)

Operações de empilhamento podem levar à situação na qual o numero de elementos na pilha seja igual ao número máximo de elementos comportados pelo container

Operações de empilhamento podem levar à situação na qual o numero de elementos na pilha seja igual ao número máximo de elementos comportados pelo container
Tentativas subseqüentes de empilhamento são impossíveis e configuram situação de transbordamento ou “overflow”
A situação de “underflow” é lógica e impossível de ser contornada. Freqüentemente não constitui erro de algoritmo e sim teste de uma condição
A situação de “overflow” é física e não lógica

Pode ser contornada aumentando o tamanho do container” hospedeiro
Contudo, durante o processamento configura um erro e deve interromper o processo

Uma operação adicional sobre pilhas é a verificação do elemento no topo da pilha getTop.

Uma operação adicional sobre pilhas é a verificação do elemento no topo da pilha getTop.
Exemplos do dia a dia:

Pilhas de pratos
Pilhas de revistas

Fila é um container no qual todas as inclusões são efetuadas em uma extremidade chamada de retaguarda e todas as exclusões são efetuadas na outra extremidade denominada frente.

Fila é um container no qual todas as inclusões são efetuadas em uma extremidade chamada de retaguarda e todas as exclusões são efetuadas na outra extremidade denominada frente.
Como nas filas o primeiro elemento a entrar é o primeiro a sair, as filas são chamadas de listas FIFO (de First-In, First-Out).
Exemplos do dia a dia:

Filas de bancos
Filas de ônibus

A formulação espontânea contém dois ponteiros frente e retaguarda ou head e tail

A formulação espontânea contém dois ponteiros frente e retaguarda ou head e tail
Inicia-se a fila com a condição de contorno head = 0 e tail = -1
Caracteriza-se fila vazia quando tail < head
Fila cheia ocorre quando tail = array.length-1, onde array.length é o número máximo de elementos previstos no “array”.
Como as listas podem “correr na memória” este esquema não é eficiente
É mais vantajoso adotar filas circulares onde o primeiro elemento sucede o último e a implementação é feita por aritmética modular

O ajustamento de ponteiros por ocasião de inclusões e exclusões se torna diferente

O ajustamento de ponteiros por ocasião de inclusões e exclusões se torna diferente
Inclusão:

tail (tail + 1) mod array.length ao invés de
tail  tail + 1

Exclusão:

head (head + 1 ) mod array.length ao invés de
head  head + 1

A fila vazia seria caracterizada por head = tail e a fila cheia também, o que não é satisfatório
Pode-se melhorar esta solução apontando head para a posição do “array” precedendo o primeiro elemento da fila. Esta será a opção adotada
A condição de file cheia se torna
head = = (tail + 1) mod array.length

A solução adotada pelo Framework de Bruno Preiss para as filas circulares é adotar a mesma condição de contorno tanto para fila cheia como para fila vazia

A solução adotada pelo Framework de Bruno Preiss para as filas circulares é adotar a mesma condição de contorno tanto para fila cheia como para fila vazia
head = tail
A diferença entre um caso e outro é dada pelo contador count sendo count == array.length para fila cheia e
count == 0 para fila vazia
Esta solução permite a ocupação de todos os espaços do array enquanto a solução sem usar count (o conteúdo do container) exige que uma posição do array permaneça desocupada antes do início da fila

public interface Comparable

public interface Comparable
{
boolean isLT (Comparable object);
boolean isLE (Comparable object);
boolean isGT (Comparable object);
boolean isGE (Comparable object);
boolean isEQ (Comparable object);
boolean isNE (Comparable object);
int compare (Comparable object);
}

// pgm05_02.java

// pgm05_02.java
public abstract class AbstractObject implements Comparable
{
public final boolean isLT (Comparable object)
{ return compare (object) < 0; }
public final boolean isLE (Comparable object)
{ return compare (object) <= 0; }
public final boolean isGT (Comparable object)
{ return compare (object) > 0; }
public final boolean isGE (Comparable object)
{ return compare (object) >= 0; }
public final boolean isEQ (Comparable object)
{ return compare (object) == 0; }
public final boolean isNE (Comparable object)
{ return compare (object) != 0; }

public final boolean equals (Object object) {

public final boolean equals (Object object) {
if(object instanceof Comparable)
return isEQ ((Comparable) object);
else
return false;
}
public final int compare (Comparable arg) {
if(getClass () == arg.getClass())
return compareTo (arg);
else
return getClass().getName().compareTo( arg.getClass().getName() );
}
protected abstract int compareTo (Comparable arg);
}

public interface Container

public interface Container
extends Comparable
{
int getCount ();
boolean isEmpty ();
boolean isFull ();
void purge ();
void accept (Visitor visitor);
Enumeration getEnumeration ();
}

public abstract class AbstractContainer

public abstract class AbstractContainer
extends AbstractObject
implements Container
{
protected int count;
public int getCount ()
{ return count; }
public boolean isEmpty ()
{ return getCount () == 0; }
public boolean isFull ()
{ return false; }
// ...
}

// pgm06_01.java

// pgm06_01.java
public interface Stack
extends Container
{
Object getTop ();
void push (Object object);
Object pop ();
}

// pgm06_13.java

// pgm06_13.java
public interface Queue
extends Container
{
Object getHead ();
void enqueue (Object object);
Object dequeue ();
}

// pgm06_02.txt

// pgm06_02.txt
public class StackAsArray
extends AbstractContainer
implements Stack
{
protected Object[] array;
// ...
}

// pgm06_03.java

// pgm06_03.java
public class StackAsArray
extends AbstractContainer implements Stack
{
protected Object[] array;
public StackAsArray (int size)
{ array = new Object [size]; }
public void purge ()
{
while (count > 0)
array [--count] = null;
}
// ...
}

// pgm06_04.java

// pgm06_04.java
public class StackAsArray
extends AbstractContainer implements Stack
{
protected Object[] array;
public void push (Object object)
{
if(count == array.length)
throw new ContainerFullException();
array [count++] = object;
}

// pgm06_04.java (Continuação)

// pgm06_04.java (Continuação)
public Object pop ()
{
if(count == 0)
throw new ContainerEmptyException();
Object result = array [--count];
array[count] = null;
return result;
}
public Object getTop ()
{
if(count == 0)
throw new ContainerEmptyException ();
return array [count - 1];
}
// ...
}

// pgm06_05.java

// pgm06_05.java
public class StackAsArray
extends AbstractContainer implements Stack
{
protected Object[] array;
public void accept (Visitor visitor)
{
for (int i = 0; i < count; ++i)
{
visitor.visit (array [i]);
if(visitor.isDone ())
return;
}
}
// ...
}

Considere-se o código que se segue

Considere-se o código que se segue
Stack stack = new StackAsArray (57);
stack.push (new Integer (3));
stack.push (new Integer (1));
stack.push (new Integer (4));
Enumeration e = stack.getEnumeration ();
while (e.hasMoreElements ())
{
Object obj = e.nextElement ();
System.out.println (obj);
}

Este código cria uma instância da classe StackAsArray e a atribui à variável stack.

Este código cria uma instância da classe StackAsArray e a atribui à variável stack.
Diversos objetos do tipo Integer são empilhados.
Finalmente uma enumeração é usada para imprimir de maneira sistemática todos os objetos na pilha.

Uma classe interior é uma classe definida dentro de outra.

Uma classe interior é uma classe definida dentro de outra.
A menos que seja declarada estática, cada instância de uma classe interior é suposta dentro de uma instância da classe exterior sendo as classes interiores não estáticas por default.
Instâncias de classes interiores podem invocar métodos de instâncias da classe exterior e ter acesso a seus membros.membros.
Pode haver mais de uma instância de classe interior para uma instância de classe exterior.
Uma classe anônima é uma classe sem nome.
Estas classes são criadas estendendo uma classe existente ou implementando uma interface bem no ponto do código aonde a classe está sendo instanciada.

// pgm06_06.java

// pgm06_06.java
public class StackAsArray
extends AbstractContainer implements Stack {
protected Object[] array;
public Enumeration getEnumeration() {
return new Enumeration() {
protected int position = 0;
public boolean hasMoreElements() { return position < getCount (); }
public Object nextElement() {
if(position >= getCount ())
throw new NoSuchElementException();
return array [position++];
}
};
}
}

// pgm06_07.java

// pgm06_07.java
public class StackAsLinkedList
extends AbstractContainer
implements Stack
{
protected LinkedList list;
// ...
}

// pgm06_08.java

// pgm06_08.java
public class StackAsLinkedList
extends AbstractContainer implements Stack
{
protected LinkedList list;
public StackAsLinkedList ()
{ list = new LinkedList (); }
public void purge ()
{
list.purge ();
count = 0;
}
// ...
}

// pgm06_09.java

// pgm06_09.java
public class StackAsLinkedList
extends AbstractContainer
implements Stack
{
protected LinkedList list;
public void push (Object object)
{
list.prepend (object);
++count;
}

// pgm06_09.java (Continuação)

// pgm06_09.java (Continuação)
public Object pop ()
{
if(count == 0)
throw new ContainerEmptyException ();
Object result = list.getFirst ();
list.extract (result);
--count;
return result;
}
public Object getTop ()
{
if(count == 0)
throw new ContainerEmptyException ();
return list.getFirst ();
}
// ...
}

// pgm06_10.java

// pgm06_10.java
public class StackAsLinkedList
extends AbstractContainer implements Stack
{
protected LinkedList list;
public void accept (Visitor visitor) {
for(LinkedList.Element ptr = list.getHead ();
ptr != null; ptr = ptr.getNext ()) {
visitor.visit (ptr.getDatum ());
if(visitor.isDone ())
return;
}
}
// ...
}

// pgm06_11.java

// pgm06_11.java
public class StackAsLinkedList
extends AbstractContainer
implements Stack
{
protected LinkedList list;

// pgm06_11.java (Continuação)

// pgm06_11.java (Continuação)
public Enumeration getEnumeration () {
return new Enumeration () {
protected LinkedList.Element position =list.getHead();
public boolean hasMoreElements ()
{ return position != null; }
public Object nextElement () {
if(position == null)
throw new NoSuchElementException ();
Object result = position.getDatum ();
position = position.getNext ();
return result;
}
};
}
// ...
}

// pgm06_14.java

// pgm06_14.java
public class QueueAsArray
extends AbstractContainer
implements Queue
{
protected Object[] array;
protected int head;
protected int tail;
// ...
}

// pgm06_15.java

// pgm06_15.java
public class QueueAsArray
extends AbstractContainer
implements Queue
{
protected Object[] array;
protected int head;
protected int tail;
public QueueAsArray (int size)
{
array = new Object [size];
head = 0;
tail = size - 1;
}

// pgm06_15.java (Continuação)

// pgm06_15.java (Continuação)
public void purge ()
{
while (count > 0)
{
array [head] = null;
if (++head == array.length)
head = 0;
--count;
}
}
// ...
}

// pgm06_16.java

// pgm06_16.java
public class QueueAsArray
extends AbstractContainer
implements Queue
{
protected Object[] array;
protected int head;
protected int tail;
public Object getHead ()
{
if(count == 0)
throw new ContainerEmptyException ();
return array [head];
}

public void enqueue (Object object) {

public void enqueue (Object object) {
if(count == array.length)
throw new ContainerFullException ();
if(++tail == array.length)
tail = 0;
array [tail] = object;
++count;
}
public Object dequeue () {
if(count == 0)
throw new ContainerEmptyException ();
Object result = array [head];
array [head] = null;
if(++head == array.length)
head = 0;
--count;
return result;
} // ...
}

// pgm06_17.java

// pgm06_17.java
public class QueueAsLinkedList
extends AbstractContainer
implements Queue
{
protected LinkedList list;
// ...
}

// pgm06_18.java

// pgm06_18.java
public class QueueAsLinkedList
extends AbstractContainer
implements Queue
{
protected LinkedList list;
public QueueAsLinkedList ()
{ list = new LinkedList (); }
public void purge ()
{
list.purge ();
count = 0;
}
// ...
}

// pgm06_19.java

// pgm06_19.java
public class QueueAsLinkedList
extends AbstractContainer
implements Queue
{
protected LinkedList list;
public Object getHead ()
{
if(count == 0)
throw new ContainerEmptyException ();
return list.getFirst ();
}

// pgm06_19.java (Continuação)

// pgm06_19.java (Continuação)
public void enqueue (Object object)
{
list.append (object);
++count;
}
public Object dequeue ()
{
if(count == 0)
throw new ContainerEmptyException ();
Object result = list.getFirst ();
list.extract(result);
--count;
return result;
}
// ...
}

// pgm05_01.cpp

// pgm05_01.cpp
class Object
{
protected:
virtual int CompareTo (Object const&) const = 0;
public:
virtual ~Object ();
virtual bool IsNull () const;
virtual int Compare (Object const&) const;
virtual HashValue Hash () const = 0;
virtual void Put (ostream&) const = 0;
};

// pgm05_02.cpp

// pgm05_02.cpp
inline bool operator == (Object const& left, Object const& right)
{ return left.Compare (right) == 0; }
inline bool operator != (Object const& left, Object const& right)
{ return left.Compare (right) != 0; }
inline bool operator <= (Object const& left, Object const& right)
{ return left.Compare (right) <= 0; }
inline bool operator < (Object const& left, Object const& right)
{ return left.Compare (right) < 0; }
inline bool operator >= (Object const& left, Object const& right)
{ return left.Compare (right) >= 0; }
inline bool operator > (Object const& left, Object const& right)
{ return left.Compare (right) > 0; }
inline ostream& operator << (ostream& s, Object const& object)
{ object.Put (s); return s; }

// pgm05_03.cpp

// pgm05_03.cpp
#include
Object::~Object ()
{}
bool Object::IsNull () const
{ return false; }
int Object::Compare (Object const& object) const
{
if(typeid (*this) == typeid (object))
return CompareTo (object);
else
if(typeid (*this).before (typeid (object)))
return -1;
else
return 1;
}

//pgm05_04.cpp

//pgm05_04.cpp
class NullObject : public Object
{
static NullObject instance;
NullObject ();
protected:
int CompareTo (Object const&) const;
public:
bool IsNull () const;
HashValue Hash () const;
void Put (ostream& s) const;
static NullObject& Instance ();
};

//pgm05_05.cpp

//pgm05_05.cpp
NullObject NullObject::instance;
NullObject::NullObject ()
{}
bool NullObject::IsNull () const
{ return true; }
int NullObject::CompareTo (Object const&) const
{ return 0; }
HashValue NullObject::Hash () const
{ return 0; }
void NullObject::Put (ostream& s) const
{ s << "NullObject"; }
NullObject& NullObject::Instance ()
{ return instance; }

//pgm05_06.cpp

//pgm05_06.cpp
template
class Wrapper : public Object
{
protected:
T datum;
int CompareTo (Object const&) const;
public:
Wrapper ();
Wrapper (T const&);
Wrapper& operator = (T const&);
operator T const& () const;
HashValue Hash() const;
void Put(ostream&) const;
};

//pgm05_07.cpp

//pgm05_07.cpp
template
Wrapper::Wrapper () :
datum ()
{}
template
Wrapper::Wrapper (T const& d) :
datum (d)
{}
template
Wrapper& Wrapper::operator = (T const& d)
{
datum = d;
return *this;
}

//pgm05_07.cpp (Continuação)

//pgm05_07.cpp (Continuação)
template
Wrapper::operator T const& () const
{ return datum; }
template
int Wrapper::CompareTo (Object const& obj) const
{
Wrapper const& arg = dynamic_cast const&> (obj);
return ::Compare (datum, arg.datum);
}
template
void Wrapper::Put (ostream& s) const
{ s << datum; }

// pgm05_09.cpp

// pgm05_09.cpp
class Container : public virtual Object, public virtual Ownership
{
protected:
unsigned int count;
Container ();
public:
virtual unsigned int Count () const;
virtual bool IsEmpty () const;
virtual bool IsFull () const;
virtual HashValue Hash () const;
virtual void Put (ostream&) const;
virtual Iterator& NewIterator () const;
virtual void Purge () = 0;
virtual void Accept (Visitor&) const = 0;
};

//pgm05_10.cpp

//pgm05_10.cpp
Container::Container () :
count (0)
{}
unsigned int Container::Count () const
{ return count; }
bool Container::IsEmpty () const
{ return Count () == 0; }
bool Container::IsFull () const
{ return false; }

//pgm05_11.cpp

//pgm05_11.cpp
class Visitor
{
public:
virtual void Visit (Object&) = 0;
virtual bool IsDone () const
{ return false; }
};

//pgm05_12.cpp

//pgm05_12.cpp
#include
class PuttingVisitor : public Visitor
{
ostream& stream;
bool comma;
public:
PuttingVisitor (ostream& s) : stream (s), comma (false) {}
void Visit (Object& object)
{
if (comma)
stream << ", ";
stream << object;
comma = true;
}
};

// pgm05_12.cpp (Conyinuação)

// pgm05_12.cpp (Conyinuação)
void Container::Put (ostream& s) const
{
PuttingVisitor visitor (s);
s << typeid (*this).name () << " {";
Accept (visitor);
s << "}";
}

//pgm05_13.cpp

//pgm05_13.cpp
class Iterator
{
public:
virtual ~Iterator ();
virtual void Reset () = 0;
virtual bool IsDone () const = 0;
virtual Object& operator * () const = 0;
virtual void operator ++ () = 0;
};

Iterator& SomeContainer::NewIterator () const

Iterator& SomeContainer::NewIterator () const
{ return *new SomeIterator (*this); }
SomeContainer c;
Iterator& i = c.NewIterator ();
while (!i.IsDone ()) {
cout << *i << endl;
++i;
}
delete &i;

//pgm05_14.cpp

//pgm05_14.cpp
class NullIterator : public Iterator
{
public:
NullIterator ();
void Reset ();
bool IsDone () const;
Object& operator * () const;
void operator ++ ();
};

//pgm05_15.cpp

//pgm05_15.cpp
NullIterator::NullIterator ()
{}
void NullIterator::Reset ()
{}
bool NullIterator::IsDone () const
{ return true; }
Object& NullIterator::operator * () const
{ return NullObject::Instance (); }
void NullIterator::operator ++ ()
{}
// pgm05_16.cpp
Iterator& Container::NewIterator () const
{ return *new NullIterator (); }

// pgm06_01.cpp

// pgm06_01.cpp
class Stack : public virtual Container
{
public:
virtual Object& Top () const = 0;
virtual void Push (Object&) = 0;
virtual Object& Pop () = 0;
};

// pgm06_01.cpp

// pgm06_01.cpp
class Stack : public virtual Container
{
public:
virtual Object& Top () const = 0;
virtual void Push (Object&) = 0;
virtual Object& Pop () = 0;
};

A variável array é declarada instanciando o template da classe Array com T=Object*, ou seja, um array de ponteiros para Object

A variável array é declarada instanciando o template da classe Array com T=Object*, ou seja, um array de ponteiros para Object
O uso de ponteiros é consistente com a implementação de containers por armazenamento indireto

// pgm06_02.cpp

// pgm06_02.cpp
class StackAsArray : public Stack {
Array array;
class Iter;
public:
StackAsArray (unsigned int);
// ...
friend class Iter;
};
class StackAsArray::Iter : public Iterator {
StackAsArray const& stack;
unsigned int position;
public:
Iter (StackAsArray const&);
// ...
};

// pgm06_03.cpp

// pgm06_03.cpp
StackAsArray::StackAsArray (unsigned int size) :
array(size)
{}
void StackAsArray::Purge ()
{
if(IsOwner ())
{
for(unsigned int i = 0; i < count; ++i)
delete array [i];
}
count = 0;
}
StackAsArray::~StackAsArray ()
{ Purge (); }

// pgm06_04.cpp

// pgm06_04.cpp
void StackAsArray::Push (Object& object) {
if(count == array.Length ())
throw domain_error ("stack is full");
array [count++] = &object;
}
Object& StackAsArray::Pop (){
if(count == 0)
throw domain_error ("stack is empty");
return *array [--count];
}
Object& StackAsArray::Top () const{
if(count == 0)
throw domain_error ("stack is empty");
return *array [count - 1U];
}

// pgm06_05.cpp

// pgm06_05.cpp
void StackAsArray::Accept (Visitor& visitor) const
{
for(unsigned int i = 0; i < count && !visitor.IsDone(); ++i)
{
visitor.Visit (*array [i]);
}
}

Na definição da classe StackAsArray foi definida uma classe embutida Iter

Na definição da classe StackAsArray foi definida uma classe embutida Iter
A classe StackAsArray::Iter é uma classe friend da classe StackAsArray tendo acesso às variáveis membro e funções privados daquela classe
A implementação do iterator depende da implementação do container

// pgm06_06.cpp

// pgm06_06.cpp
StackAsArray::Iter::Iter (StackAsArray const& _stack) :
stack (_stack)
{ Reset (); }
bool StackAsArray::Iter::IsDone () const
{ return position >= stack.count; }
Object& StackAsArray::Iter::operator * () const
{
if(position < stack.count)
return *stack.array [position];
else
return NullObject::Instance ();
}

// pgm06_06.cpp (ContinuaçÃo)

// pgm06_06.cpp (ContinuaçÃo)
void StackAsArray::Iter::operator ++ ()
{
if(position < stack.count)
++position;
}
void StackAsArray::Iter::Reset ()
{ position = 0; }

Considere-se o código que se segue

Considere-se o código que se segue
StackAsArray stack;
stack.Push (*new Int (3));
stack.Push (*new Int (1));
stack.Push (*new Int (4));
Iterator& i = stack.NewIterator ();
while (!i.IsDone ()) {
cout << *i << endl;
++i;
}
delete &i;

Este código declara uma variável stack

Este código declara uma variável stack
Diversos objetos do tipo Integer são empilhados.
Finalmente um Iterator é usado para imprimir de maneira sistemática todos os objetos na pilha.

// pgm06_07.cpp

// pgm06_07.cpp
class StackAsLinkedList : public Stack {
LinkedList list;
class Iter;
public:
StackAsLinkedList ();
// ...
friend class Iter;
};
class StackAsLinkedList::Iter : public Iterator {
StackAsLinkedList const& stack;
ListElement const* position;
public:
Iter (StackAsLinkedList const&);
// ...
};

// pgm06_08.cpp

// pgm06_08.cpp
StackAsLinkedList::StackAsLinkedList () :
list ()
{}
void StackAsLinkedList::Purge ()
{
if(IsOwner()) {
ListElement const* ptr;
for (ptr = list.Head (); ptr != 0; ptr = ptr->Next ())
delete ptr->Datum ();
}
list.Purge ();
count = 0;
}
StackAsLinkedList::~StackAsLinkedList ()
{ Purge (); }

// pgm06_09.cpp

// pgm06_09.cpp
void StackAsLinkedList::Push (Object& object)
{
list.Prepend (&object);
++count;
}
Object& StackAsLinkedList::Pop ()
{
if(count == 0)
throw domain_error ("stack is empty");
Object& const result = *list.First ();
list.Extract (&result);
--count;
return result;
}

// pgm06_09.cpp (Continuação)

// pgm06_09.cpp (Continuação)
Object& StackAsLinkedList::Top () const
{
if(count == 0)
throw domain_error ("stack is empty");
return *list.First ();
}

// pgm06_10.cpp

// pgm06_10.cpp
void StackAsLinkedList::Accept (Visitor& visitor) const
{
ListElement const* ptr;
for(ptr = list.Head ();ptr != 0 && !visitor.IsDone (); ptr = ptr->Next ())
{
visitor.Visit (*ptr->Datum ());
}
}

// pgm06_11.cpp

// pgm06_11.cpp
StackAsLinkedList::Iter::Iter (
StackAsLinkedList const& _stack) :
stack (_stack)
{ Reset (); }
bool StackAsLinkedList::Iter::IsDone () const
{ return position == 0; }
Object& StackAsLinkedList::Iter::operator * () const
{
if(position != 0)
return *position->Datum ();
else
return NullObject::Instance ();
}

// pgm06_11.cpp (Continuação)

// pgm06_11.cpp (Continuação)
void StackAsLinkedList::Iter::operator ++ ()
{
if(position != 0)
position = position->Next ();
}
void StackAsLinkedList::Iter::Reset ()
{ position = stack.list.Head (); }

// pgm06_13.cpp

// pgm06_13.cpp
class Queue : public virtual Container
{
public:
virtual Object& Head () const = 0;
virtual void Enqueue (Object&) = 0;
virtual Object& Dequeue () = 0;
};

// pgm06_14.cpp

// pgm06_14.cpp
class QueueAsArray : public virtual Queue
{
protected:
Array array;
unsigned int head;
unsigned int tail;
public:
QueueAsArray (unsigned int);
~QueueAsArray ();
// ...
};

// pgm06_15.cpp

// pgm06_15.cpp
QueueAsArray::QueueAsArray (unsigned int size) :
array (size),
head (0),
tail (size - 1U)
{}

// pgm06_15.cpp (Continuação)

// pgm06_15.cpp (Continuação)
void QueueAsArray::Purge ()
{
if(IsOwner ())
{
for(unsigned int i = 0; i < count; ++i)
{
delete array [head];
if(++head == array.Length ())
head = 0;
}
}
count = 0;
}
QueueAsArray::~QueueAsArray ()
{ Purge (); }

// pgm06_16.cpp

// pgm06_16.cpp
Object& QueueAsArray::Head () const
{
if(count == 0)
throw domain_error ("queue is empty");
return *array [head];
}
void QueueAsArray::Enqueue (Object& object)
{
if(count == array.Length ())
throw domain_error ("queue is full");
if(++tail == array.Length ())
tail = 0;
array [tail] = &object;
++count;
}

// pgm06_16.cpp (Continuação)

// pgm06_16.cpp (Continuação)
Object& QueueAsArray::Dequeue ()
{
if (count == 0)
throw domain_error ("queue is empty");
Object& result = *array [head];
if (++head == array.Length ())
head = 0;
--count;
return result;
}

// pgm06_17.cpp

// pgm06_17.cpp
class QueueAsLinkedList : public virtual Queue
{
protected:
LinkedList list;
public:
QueueAsLinkedList ();
~QueueAsLinkedList ();
// ...
};

// pgm06_18.cpp

// pgm06_18.cpp
QueueAsLinkedList::QueueAsLinkedList () :
list ()
{}
void QueueAsLinkedList::Purge () {
if(IsOwner ()) {
ListElement const* ptr;
for(ptr = list.Head (); ptr != 0; ptr = ptr->Next ())
delete ptr->Datum ();
}
list.Purge ();
count = 0;
}
QueueAsLinkedList::~QueueAsLinkedList ()
{ Purge (); }

// pgm06_19.cpp

// pgm06_19.cpp
Object& QueueAsLinkedList::Head () const
{
if (count == 0)
throw domain_error ("queue is empty");
return *list.First ();
}
void QueueAsLinkedList::Enqueue (Object& object)
{
list.Append (&object);
++count;
}

// pgm06_19.cpp (Continuação)

// pgm06_19.cpp (Continuação)
Object& QueueAsLinkedList::Dequeue ()
{
if(count == 0)
throw domain_error ("queue is empty");
Object& result = *list.First ();
list.Extract (&result);
--count;
return result;
}

Yüklə 446 b.

Dostları ilə paylaş:

Definição Pilhas Filas Implementação Java

Definição

Definição

Implementação Java

Implementação C++

Implementação Java

Implementação Java

Implementação C++

Pilha é o mais simples dos containers.

Pilha é o mais simples dos containers.

A operação de inclusão de elementos na pilha recebe o nome de empilhamento (push) e a operação de exclusão recebe o nome de desempilhamento (pop)

Um elemento empilhado vai ocupar a posição chamada de topo da pilha

Uma operação de desempilhamento provoca a exclusão do elemento no topo da pilha. Por esta razão as pilhas são chamadas de listas LIFO ( de “Last In First Out’).

Uma operação de desempilhamento em uma pilha vazia não tem sentido e configura uma situação denominada “underflow”

Pode-se verificar se uma pilha atingir a condição de contorno de pilha vazia através da função isEmpty que pode assumir os valores TRUE (pilha vazia) ou FALSE (pilha não vazia)

Operações de empilhamento podem levar à situação na qual o numero de elementos na pilha seja igual ao número máximo de elementos comportados pelo container

Operações de empilhamento podem levar à situação na qual o numero de elementos na pilha seja igual ao número máximo de elementos comportados pelo container

Tentativas subseqüentes de empilhamento são impossíveis e configuram situação de transbordamento ou “overflow”

A situação de “underflow” é lógica e impossível de ser contornada. Freqüentemente não constitui erro de algoritmo e sim teste de uma condição

A situação de “overflow” é física e não lógica

Uma operação adicional sobre pilhas é a verificação do elemento no topo da pilha getTop.

Uma operação adicional sobre pilhas é a verificação do elemento no topo da pilha getTop.

Exemplos do dia a dia:

Fila é um container no qual todas as inclusões são efetuadas em uma extremidade chamada de retaguarda e todas as exclusões são efetuadas na outra extremidade denominada frente.

Fila é um container no qual todas as inclusões são efetuadas em uma extremidade chamada de retaguarda e todas as exclusões são efetuadas na outra extremidade denominada frente.

Como nas filas o primeiro elemento a entrar é o primeiro a sair, as filas são chamadas de listas FIFO (de First-In, First-Out).

Exemplos do dia a dia:

A formulação espontânea contém dois ponteiros frente e retaguarda ou head e tail

A formulação espontânea contém dois ponteiros frente e retaguarda ou head e tail

Inicia-se a fila com a condição de contorno head = 0 e tail = -1

Caracteriza-se fila vazia quando tail < head

Fila cheia ocorre quando tail = array.length-1, onde array.length é o número máximo de elementos previstos no “array”.

Como as listas podem “correr na memória” este esquema não é eficiente

É mais vantajoso adotar filas circulares onde o primeiro elemento sucede o último e a implementação é feita por aritmética modular

O ajustamento de ponteiros por ocasião de inclusões e exclusões se torna diferente

O ajustamento de ponteiros por ocasião de inclusões e exclusões se torna diferente

Inclusão:

Exclusão:

A fila vazia seria caracterizada por head = tail e a fila cheia também, o que não é satisfatório

Pode-se melhorar esta solução apontando head para a posição do “array” precedendo o primeiro elemento da fila. Esta será a opção adotada

A condição de file cheia se torna

head = = (tail + 1) mod array.length

A solução adotada pelo Framework de Bruno Preiss para as filas circulares é adotar a mesma condição de contorno tanto para fila cheia como para fila vazia

A solução adotada pelo Framework de Bruno Preiss para as filas circulares é adotar a mesma condição de contorno tanto para fila cheia como para fila vazia

head = tail

A diferença entre um caso e outro é dada pelo contador count sendo count == array.length para fila cheia e

count == 0 para fila vazia

Esta solução permite a ocupação de todos os espaços do array enquanto a solução sem usar count (o conteúdo do container) exige que uma posição do array permaneça desocupada antes do início da fila

public interface Comparable

public interface Comparable

{

boolean isLT (Comparable object);

boolean isLE (Comparable object);

boolean isGT (Comparable object);

boolean isGE (Comparable object);

boolean isEQ (Comparable object);

boolean isNE (Comparable object);

int compare (Comparable object);

}

// pgm05_02.java

// pgm05_02.java

public abstract class AbstractObject implements Comparable

{

public final boolean isLT (Comparable object)

{ return compare (object) < 0; }

public final boolean isLE (Comparable object)

{ return compare (object) <= 0; }

public final boolean isGT (Comparable object)

{ return compare (object) > 0; }

public final boolean isGE (Comparable object)

{ return compare (object) >= 0; }

public final boolean isEQ (Comparable object)

{ return compare (object) == 0; }

public final boolean isNE (Comparable object)

{ return compare (object) != 0; }

public final boolean equals (Object object) {

public final boolean equals (Object object) {

if(object instanceof Comparable)

return isEQ ((Comparable) object);

else