Estruturas de Dados em C#: Pilhas, Filas e Listas

Pilha Estática

public class Pilha
{
private const int CAPACIDADE = 5; // define o tamanho máximo desta pilha.
private string[] dados = new string[CAPACIDADE]; // vetor para guardar os dados da pilha.
private int topo = -1; // variável que irá indicar a posição no vetor do topo da pilha.
public int Tamanho()
{
return topo + 1; // lembre-se que o vetor inicia da posição zero...
}
public bool Vazia()
{
return Tamanho() == 0;
}
public void Empilha(string p_valor)
{
if (Tamanho() != CAPACIDADE)
{
topo++;
dados[topo] = p_valor;
}
else
{
throw new Exception("A pilha está cheia!!!");
}
}
public string Desempilha()
{
if (Vazia() == true)
{
throw new Exception("A pilha está vazia!!!");
}
else
{
topo--;
return dados[topo + 1];
}
}
public string RetornaTopo()
{
if (Vazia() == true)
throw new Exception("A pilha está vazia!!!");
else
return dados[topo];
}
}

Fila Estática

class FilaEstatica
{
const int CAPACIDADE = 5; // capacidade máxima da fila
private int quantidade = 0; // qtde de elementos enfileirados
private int inicio = 0; // indica qual a primeira posição da fila
private int fim = 0; // indica a próxima posição
private string[] dados = new string[CAPACIDADE]; // armazenar os dados da fila
public int tamanho()
{
return quantidade;
}
public void enfileirar(string p_valor)
{
if (tamanho() == CAPACIDADE)
{
throw new Exception("A fila está cheia!!!!");
}
else
{
dados[fim] = p_valor;
fim = (fim + 1) % CAPACIDADE;
quantidade++;
}
}
public string desenfileira()
{
if (tamanho() == 0)
{
throw new Exception("A fila está vazia!");
}
else
{
string valor = dados[inicio];
inicio = (inicio + 1) % CAPACIDADE;
quantidade--;
return valor;
}
}
public string RetornaInicio()
{
return dados[inicio];
}
public string RetornaFim()
{
if (tamanho() == 0)
{
throw new Exception("A fila está vazia!");
}
else
{
if (fim == 0)
return dados[CAPACIDADE - 1];
else
return dados[fim - 1];
}
}
public string Listar()
{
int totalImpresso = tamanho();
string retorno = "";
int posicaoAtual = inicio;
while (totalImpresso > 0)
{
retorno = retorno + dados[posicaoAtual] + " - ";
posicaoAtual = (posicaoAtual + 1) % CAPACIDADE;
totalImpresso--;
}
return retorno;
}
}

Lista Estática

class ListaEstatica
{
private const int CAPACIDADE = 10;
private string[] dados = new string[CAPACIDADE];
private int quantidade = 0;
public int tamanho()
{
return quantidade;
}
public void insereNaPosicao(int p_posicao, string p_valor)
{
if (tamanho() == CAPACIDADE)
throw new Exception("A lista está cheia!!!\n\n");
else if (p_posicao > tamanho())
throw new Exception("Não é possível inserir nesta posição");
else
{
quantidade++;
for (int i = tamanho() - 1; i > p_posicao; i--)
{
dados[i] = dados[i - 1];
}
dados[p_posicao] = p_valor;
}
}
public string removeDaPosicao(int posicao)
{
if (tamanho() == 0)
throw new Exception("A lista está vazia!!!");
else if (posicao > tamanho() - 1)
throw new Exception("Posição inválida!!!");
else
{
string aux = dados[posicao];
for (int i = posicao; i < tamanho() - 1; i++)
{
dados[i] = dados[i + 1];
}
quantidade--;
return aux;
}
}
public void insereNoInicio(string p_valor)
{
insereNaPosicao(0, p_valor);
}
public void insereNoFim(string p_valor)
{
insereNaPosicao(tamanho(), p_valor);
}
public void imprimeLista()
{
Console.WriteLine("\n\nImpressão dos dados da lista:\n");
for (int i = 0; i < tamanho(); i++)
{
Console.WriteLine(dados[i]);
}
}
}

Pilha Dinâmica

class Nodo
{
private string valor;
private Nodo anterior;
public string Valor
{ get { return valor; } set { valor = value; } }
public Nodo Anterior
{ get { return anterior; } set { anterior = value; } }
}
class PilhaDinamica
{
private Nodo topo = null;
int quantidade = 0;
public int Quantidade
{
get { return quantidade; }
}
public void Empilhar(string valor)
{
Nodo novoNodo = new Nodo();
novoNodo.Valor = valor;
novoNodo.Anterior = topo;
topo = novoNodo;
quantidade++;
}
public string Desempilhar()
{
if (quantidade == 0)
throw new Exception("A pilha está vazia!");
else
{
string retorno = topo.Valor;
topo = topo.Anterior;
quantidade--;
return retorno;
}
}
public string RetornaTopo()
{
if (quantidade == 0)
throw new Exception("A pilha está vazia!");
else
{
return topo.Valor;
}
}
public string Listar()
{
Nodo aux = topo;
string retorno = "";
while (aux != null)
{
retorno = retorno + " - " + aux.Valor;
aux = aux.Anterior;
}
return retorno;
}
}

Fila Dinâmica

class Nodo
{
string valor = "";
public string Valor
{ get { return valor; } set { valor = value; } }
Nodo proximo = null;
public Nodo Proximo
{ get { return proximo; } set { proximo = value; } }
}
class Fila
{
private int quantidade = 0; // qtde de elementos enfileirados
private Nodo inicio = null; // indica qual a primeira posição da fila
private Nodo fim = null; // indica a próxima posição
public int tamanho()
{ return quantidade; }
public void enfileirar(string p_valor)
{
Nodo novo = new Nodo();
novo.Valor = p_valor;
novo.Proximo = null;
if (quantidade == 0)
{ inicio = novo; }
else
{ fim.Proximo = novo; }
fim = novo;
quantidade++;
}
public string desenfileira()
{
if (tamanho() == 0)
{ throw new Exception("A fila está vazia!"); }
else
{
string valor = inicio.Valor;
inicio = inicio.Proximo;
quantidade--;
if (quantidade == 0)
fim = null;
return valor;
}
}
public string Listagem()
{
string retorno = "";
Nodo aux = inicio;
while (aux != null)
{
retorno = retorno + aux.Valor + " - ";
aux = aux.Proximo;
}
return retorno;
}
public string Retornafim()
{
if (tamanho() != 0)
return fim.Valor;
else { throw new Exception("A fila está vazia!"); }
}
}

Lista Dinâmica

class Nodo
{
string dado;
public string Dado
{ get { return dado; } set { dado = value; } }
Nodo proximo;
public Nodo Proximo
{ get { return proximo; } set { proximo = value; } }
}
class Lista
{
Nodo primeiro = null;
int qtde = 0;
public void InserirNaPosicao(Nodo anterior, string valor)
{
Nodo novo = new Nodo();
novo.Dado = valor;
if (anterior == null)
{
if (primeiro == null)
primeiro = novo;
else
{
novo.Proximo = primeiro;
primeiro = novo;
}
}
else
{
novo.Proximo = anterior.Proximo;
anterior.Proximo = novo;
}
qtde++;
}
public void InserirNoInicio(string valor)
{
InserirNaPosicao(null, valor);
}
public void InserirNoFim(string valor)
{
if (qtde == 0)
{
InserirNoInicio(valor);
}
else
{
Nodo aux = primeiro;
while (aux.Proximo != null)
{
aux = aux.Proximo;
}
InserirNaPosicao(aux, valor);
}
}
public void InserirNaPosicao(string valor, int posicao)
{
if (posicao > qtde || posicao <= 0)
throw new Exception("Não é possível inserir.");
if (posicao == 1)
InserirNoInicio(valor);
else
{
Nodo aux = primeiro;
for (int i = 1; i < posicao - 1; i++)
aux = aux.Proximo;
InserirNaPosicao(aux, valor);
}
}
public string RemoverDaPosicao(int posicao)
{
if (posicao > qtde || posicao <= 0)
throw new Exception("Não é possível remover.");
string valor = "";
if (posicao == 1)
{
valor = primeiro.Dado;
primeiro = primeiro.Proximo;
}
else
{
Nodo aux = primeiro;
for (int i = 1; i < posicao - 1; i++)
aux = aux.Proximo;
valor = aux.Proximo.Dado;
aux.Proximo = aux.Proximo.Proximo;
}
qtde--;
return valor;
}
public bool Pesquisa(string dado)
{
Nodo aux = primeiro;
while (aux != null)
{
if (aux.Dado == dado) return true;
aux = aux.Proximo;
}
return false;
}
public string Listar()
{
string r = string.Empty;
Nodo aux = primeiro;
while (aux != null)
{
r = r + Environment.NewLine + aux.Dado;
aux = aux.Proximo;
}
return r.Trim();
}
public void Listar(Nodo e)
{
if (e != null)
Console.WriteLine(e.Dado);
if (e.Proximo != null)
Listar(e.Proximo);
}
public Nodo RetornaPrimeiro()
{
return primeiro;
}
}

Lista Duplamente Encadeada

public class Nodo
{
private string valor = string.Empty;
public string Valor
{ get { return valor; } set { valor = value; } }
private Nodo anterior = null;
internal Nodo Anterior
{ get { return anterior; } set { anterior = value; }}
private Nodo proximo = null;
internal Nodo Proximo
{ get { return proximo; } set { proximo = value; } }
}
public class ListaDup
{
private Nodo primeiro;
private Nodo ultimo;
int quantidade = 0;
public Nodo Localizar(string valor)
{
Nodo aux = primeiro;
while (aux != null)
{
if (aux.Valor == valor)
{ return aux; }
aux = aux.Proximo;
}
return null;
}
public void InsereDepoisDe(string oque, string depoisDeQue)
{
Nodo nodo = Localizar(depoisDeQue);
if (nodo == null)
throw new Exception("O valor [ " + depoisDeQue + " ] não existe na lista!");
Nodo novo = new Nodo();
novo.Valor = oque;
novo.Anterior = nodo;
novo.Proximo = nodo.Proximo;
if (nodo.Proximo != null)
nodo.Proximo.Anterior = novo;
nodo.Proximo = novo;
}
public void InsereNoInicio(string valor)
{
Nodo novo = new Nodo();
novo.Valor = valor;
novo.Proximo = primeiro;
if (primeiro != null)
primeiro.Anterior = novo;
if (ultimo == null)
ultimo = novo;
primeiro = novo;
quantidade++;
}
public void InsereNoFim(string valor)
{
Nodo novo = new Nodo();
novo.Valor = valor;
if (ultimo != null)
ultimo.Proximo = novo;
if (primeiro == null)
primeiro = novo;
novo.Anterior = ultimo;
ultimo = novo;
quantidade++;
}
public List Listar()
{
List lista = new List();
Nodo aux = primeiro;
while (aux != null)
{
lista.Add(aux.Valor);
aux = aux.Proximo;
}
return lista;
}
}