Estruturas de Dados: Pilha, Fila e Lista Estática em C#

Computação28 out. 202621,41 KB

O TAD define o que cada operação faz, mas não como o faz. Transformar este TAD em um tipo de dados concreto exige considerar as medidas de eficiência da implementação, sobretudo, as suas necessidades de espaço de armazenamento e tempo de execução.

Computabilidade e Complexidade

Um problema é computável se existe um procedimento que o resolve em um número finito de passos, isto é, um algoritmo que leve à sua solução.
A complexidade computacional de um algoritmo diz respeito aos recursos computacionais (espaço de memória e tempo de máquina) requeridos para solucionar um problema.
O tamanho de um problema é o tamanho da entrada do algoritmo que resolve o problema.
A complexidade de tempo de um problema é o número de passos necessários para resolver uma instância do problema.

Principais classes de complexidade

O(1) – tempo constante
O(log N) – tempo de execução logarítmico
O(N) – tempo de execução linear
O(N²) – tempo de execução quadrático
O(2^N) – tempo de execução exponencial

Implementação de uma Pilha em C#

public class Pilha {
private const int CAPACIDADE = 5;
private string[] dados = new string[CAPACIDADE];
private int topo = -1;
public int Tamanho() {
    return topo + 1;
}
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];
}
}

Programa de teste da Pilha

int opcao = 0;
string valor;
Pilha minhaPilha = new Pilha();
do {
try {
Console.Write("\n\n Escolha: 1-> Empilha 2-> Desempilha " + " 3-> Topo 4-> Tamanho 9-> Sair : ");
opcao = Convert.ToInt32(Console.ReadLine());
if (opcao == 1) {
Console.Write(">>Digite o valor que deseja empilhar: ");
valor = Console.ReadLine();
minhaPilha.Empilha(valor);
}
else if (opcao == 2) {
valor = minhaPilha.Desempilha();
Console.WriteLine(">>Desempilhado: {0} \n\n", valor);
}
else if (opcao == 3) {
valor = minhaPilha.RetornaTopo();
Console.WriteLine(">>Valor no topo: {0} \n\n", valor);
}
else if (opcao == 4) {
Console.WriteLine(">>Tamanho da pilha: {0}", minhaPilha.Tamanho());
}
}
catch (Exception erro) {
Console.WriteLine("Erro: " + erro.Message);
}
} while (opcao != 9);

Operações adicionais sobre a Pilha

else if (opcao == 5) { // Lista dados
Pilha pilhaAux = new Pilha();
while (minhaPilha.Tamanho() != 0) {
func = minhaPilha.Desempilha();
Console.WriteLine(">>Valor no topo: {0} - {1} \n\n", func.Nome, func.Salario);
pilhaAux.Empilha(func);
}
while (pilhaAux.Tamanho() != 0)
minhaPilha.Empilha(pilhaAux.Desempilha());
}
else if (opcao == 6) { // Soma salário
double soma = 0;
Pilha pilhaAux = new Pilha();
while (minhaPilha.Tamanho() != 0) {
func = minhaPilha.Desempilha();
soma += func.Salario;
pilhaAux.Empilha(func);
}
while (pilhaAux.Tamanho() != 0)
minhaPilha.Empilha(pilhaAux.Desempilha());
Console.WriteLine("Soma total: " + soma);
}
else if (opcao == 7) { // Remove a base
Pilha pilhaAux = new Pilha();
while (minhaPilha.Tamanho() != 1)
pilhaAux.Empilha(minhaPilha.Desempilha());
func = minhaPilha.Desempilha();
Console.WriteLine(">>Valor na base que foi desempilhado: {0} - {1} \n\n", func.Nome, func.Salario);
while (pilhaAux.Tamanho() != 0)
minhaPilha.Empilha(pilhaAux.Desempilha());
}

Implementação de uma Fila Circular em C#

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];
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() {
if (tamanho() == 0) {
throw new Exception("A fila está vazia!");
} else {
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;
}

Programa de teste da Fila

string opcao = "", valor;
Fila minhaFila = new Fila();
Console.WriteLine("Sistema em C# para testar a execução de uma fila circular\n");
do {
try {
Console.WriteLine("\n\nDigite: 1->Enfileirar 2->Desenfileirar " + "3-> Tamanho 9->Sair");
opcao = Console.ReadLine();
switch (opcao) {
case "1":
Console.WriteLine("Digite um valor para enfileirar:");
valor = Console.ReadLine();
minhaFila.enfileirar(valor);
break;
case "2":
Console.WriteLine("Desenfileirado: {0}", minhaFila.desenfileira());
break;
case "3":
Console.WriteLine("Tamanho da fila: {0}", minhaFila.tamanho());
break;
case "9":
Console.WriteLine("Saindo do sistema...");
break;
default:
Console.WriteLine("Opção inválida!!!");
break;
}
} catch (Exception erro) {
Console.WriteLine(erro.Message);
}
} while (opcao != "9");

Operação auxiliar sobre a Fila (caso 7)

case "7":
Pilha pilhaAux = new Pilha();
while (minhaFila.tamanho() > 0)
pilhaAux.Empilha(minhaFila.desenfileira());
while (pilhaAux.Tamanho() > 0)
minhaFila.enfileirar(pilhaAux.Desempilha());

Implementação de uma Lista Estática em C#

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]);
}
}

Programa de teste da Lista

string opcao = "", valor;
int posicao;
Lista minhaLista = new Lista();
Console.WriteLine("Sistema em C# para testar a execução de uma lista estática\n");
do {
try {
Console.WriteLine("\nDigite: \n 1-> Inserir no início \n " +
"2-> Inserir no fim \n " +
"3-> Inserir em uma posição (lembre-se que inicia do zero!)\n " +
"4-> Tamanho \n 5-> Listar \n " +
"6-> Remover elemento de uma posição \n 9-> Sair");
opcao = Console.ReadLine();
switch (opcao) {
case "1":
Console.WriteLine("Digite um valor para inserir no início:");
valor = Console.ReadLine();
minhaLista.insereNoInicio(valor);
break;
case "2":
Console.WriteLine("Digite um valor para inserir no fim:");
valor = Console.ReadLine();
minhaLista.insereNoFim(valor);
break;
case "3":
Console.WriteLine("Digite um valor para inserir:");
valor = Console.ReadLine();
Console.WriteLine("Digite a posição:");
posicao = Convert.ToInt32(Console.ReadLine());
minhaLista.insereNaPosicao(posicao, valor);
break;
case "4":
Console.WriteLine("Tamanho da lista: {0}", minhaLista.tamanho());
break;
case "5":
minhaLista.imprimeLista();
break;
case "6":
Console.WriteLine("Digite a posição que deseja remover:");
posicao = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Removido: {0}", minhaLista.removeDaPosicao(posicao));
break;
case "9":
Console.WriteLine("Saindo do sistema...");
break;
default:
Console.WriteLine("Opção inválida!!!");
break;
}
} catch (Exception erro) {
Console.WriteLine(erro.Message);
}
} while (opcao != "9");

Baixar

PDF Word HTML