Referência da Template de Classe persistence::stack::Stack< T >

Descrição Detalhada

template<class T>
class persistence::stack::Stack< T >

Pilha persistente.

Uma pilha implementada usando lista ligada, é automaticamente persistente pois este método nunca modifica nenhum nó, e portanto esta é uma implementação funcional. Para podermos ter acesso ao k-ésimo elemento, utilizamos uma técnica desenvolvida por Myers [3] , que se aproveita da representação em skew-binary de um número para subir k links na lista ligada em tempo logaritmico, apenas armazenando um ponteiro e um inteiro em cada nó.

A pilha armazena elementos do tipo T, e só assume que esse tipo tem um construtor de cópia. Uma diferença do código discutido no Capítulo 2 da tese é que aqui as funções não recebem a pilha, mas são métodos desta.

Um objeto Stack é apenas um ponteiro para um nó (Node) que é o último elemento da pilha. O objeto é imutável, e continua válido mesmo após chamadas de Push e Pop, já que estas devolvem uma cópia modificada da estrutura. Dessa forma, é possível acessar (e modificar) versões antigas da estrutura, como no exemplo abaixo:

using namespace persistence::stack;
Stack<int> p1; // ()
Stack<int> p2 = p1.Push(1); // (1)
Stack<int> p3 = p2.Push(2); // (1, 2)
Stack<int> p4 = p3.Push(0); // (1, 2, 0)
Stack<int> p5 = p2.Pop(); // (1)

Note que, quando usados em um contexto persistente, os nós da pilha não formam mais uma lista ligada, mas sim uma árvore, já que vários nós podem apontar para o mesmo nó. Adicionar um nó no começo da lista é na verdade adicionar uma folha nesta árvore.

Métodos Públicos
	Stack ()
	Construtor de pilha vazia. Mais...
Stack &	operator= (const Stack &o)
	Stack (const Stack &o)

Campos de Dados
Node< T > *	node
	Topo da pilha. Mais...

Operações de Acesso
const T &	Top () const
	Topo da pilha. Mais...
const T &	K_th (int k) const
	k-ésimo elemento. Mais...
int	Size () const
	Tamanho da pilha. Mais...

Operações de Modificação
Estas funções devolvem uma cópia modificada da pilha, e não alteram o objeto na qual são chamadas.
Stack< T >	Push (const T &x) const
	Inserção da valor. Mais...
Stack< T >	Pop () const
	Remoção do topo. Mais...

Construtores & Destrutores

template<class T>

persistence::stack::Stack< T >::Stack

(

)

Construtor de pilha vazia.

Contrói uma pilha sem nenhum elemento.

Métodos

template<class T>

const T& persistence::stack::Stack< T >::K_th

(

int

k

)

const

k-ésimo elemento.

Parâmetros

k	O elemento desejado. 1 é o primeiro elemento da pilha.

Retorna

O valor do k-ésimo elemento da pilha.

Pré-Condição

1 ≤ k ≤ n, onde n é o tamanho da pilha.

Anotações

Top() é equivalente a K_th(n)

Exemplo

stack::Stack<int> st;
st = st.Push(2);
st = st.Push(3);
st.K_th(0); // devolve 2
st.K_th(1); // devolve 3

template<class T>

Stack<T> persistence::stack::Stack< T >::Pop

(

)

const

Remoção do topo.

Retorna

Uma cópia desta pilha sem seu último elemento.

Pré-Condição

A pilha não deve estar vazia.

template<class T>

Stack<T> persistence::stack::Stack< T >::Push

(

const T &

x

)

const

Inserção da valor.

Parâmetros

x	Valor a ser adicionado.

Retorna

Uma cópia desta pilha com o valor x em seu fim.

template<class T>

int persistence::stack::Stack< T >::Size

(

)

const

Tamanho da pilha.

Retorna

O tamanho da pilha

template<class T>

const T& persistence::stack::Stack< T >::Top

(

)

const

Topo da pilha.

Retorna

O valor do último elemento da pilha.

Pré-Condição

A pilha não deve estar vazia.

Veja também

K_th

Exemplo

stack::Stack<int> st;
st = st.Push(2);
st = st.Push(3);
st.Top(); // devolve 3
st.Pop().Top(); // devolve 2

Campos

template<class T>

Node<T>* persistence::stack::Stack< T >::node

Topo da pilha.

O nó node é o último elemento da pilha.

Veja também

Node

---

A documentação para esta classe foi gerada a partir do seguinte arquivo:

• /home/travis/build/yancouto/mestrado/source/persistence/Stack.hpp