Pilhas (Stacks)

Ir em baixo

Pilhas (Stacks)

Mensagem por Evandro Abu Kamel em Sex 18 Set 2009, 21:46

Segue abaixo o código da implementação da pilha usando vetor.


TAD Pilha (Stack)

Código:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ClassStack
{
   class Stack
   {
      private int[] store;
      private int top;
      const int MaxTam = 10;

      // Construtor
      public Stack()
      {
         this.store = new int[MaxTam];
         this.top = 0;
      }

      // Empilha
      public void push(int x)
      {
         if (this.top == this.store.Length)
            grow();
         this.store[this.top] = x;
         this.top++;
      }

      // Desempilha
      public int pop()
      {
         if (!isEmpty())
         {
            int result = this.store[this.top - 1];
            this.top--;
            return result;
         }
         else
            Console.WriteLine("Pilha vazia!\n");
         return -1;
      }

      // Esta vazio?
      public bool isEmpty()
      {
         return (this.top == 0);
      }

      // Aumenta capacidade
      private void grow()
      {
         int[] newstore;
         newstore = new int[this.store.Length * 2];

         for (int i = 0; i < this.store.Length; i++)
            newstore[i] = this.store[i];
         this.store = newstore;
      }

      // Espia o topo
      public int peek()
      {
         if (!isEmpty())
            return this.store[this.top - 1];
         else
            Console.WriteLine("Pilha vazia!\n");
         return 0;
      }

      // Exibe a pilha
      public void print()
      {
         Console.WriteLine("");
         for (int i = this.top - 1; i >= 0; i--)
            Console.WriteLine("  {0}  ", this.store[i]);
      }
   }
   
   class Program
   {
      static void Main(string[] args)
      {
         Console.WriteLine("\n -= TAD Pilha (Stack) =-\n");

         Stack s = new Stack();

         s.push(10);
         s.push(4);
         s.push(1);
         s.push(7);
         s.push(8);
         s.push(5);
         s.push(2);
         s.peek();
         s.print();

         s.pop();
         s.pop();
         s.pop();
         s.peek();
         s.print();

         s.push(17);
         s.push(52);
         s.push(48);
         s.push(35);
         s.push(12);
         s.push(19);
         s.push(63);
         s.push(85);
         s.push(25);
         s.push(31);
         s.peek();
         s.print();

         Console.WriteLine("\n\n");
         Console.ReadLine();
      }
   }
}

A seguir, o código do programa com aqueles métodos de copiar a pilha em ordem normal e invetida, para isso, foi necessário adicionar o código da classe Fila no código deste programa.


Pilha (Stack) com métodos de copiar

Código:
using System;
using System.Collections.Generic;
using System.Text;

namespace ClassPilha
{
   class Pilha
   {
      private int[] item;
      private int numeroElementos;
      const int MaxTam = 20;

      // Construtor
      public Pilha()
      {
         this.item = new int[MaxTam];
         this.numeroElementos = 0;
      }

      // Empilha
      public void empilha(int x)
      {
         Console.WriteLine("Empilhando {0} ...", x);         
         if (this.numeroElementos == this.item.Length)
            grow();
         this.item[this.numeroElementos] = x;
         this.numeroElementos++;
      }

      // Desempilha
      public int desempilha()
      {
         if (!vazia())
         {
            Console.WriteLine("Desempilhando {0} ...", obtemElementoTopo());         
            int result = this.item[this.numeroElementos - 1];
            this.numeroElementos--;
            return result;
         }
         else
            Console.WriteLine("Pilha vazia!\n");
         return -1;
      }

      // Esta vazio?
      public bool vazia()
      {
         return (this.numeroElementos == 0);
      }

      // Aumenta capacidade
      private void grow()
      {
         int[] newitem;
         newitem = new int[(this.item.Length+1)];

         for (int i = 0; i < this.item.Length; i++)
            newitem[i] = this.item[i];
         this.item = newitem;
      }

      // Obtem o elemento do topo
      public int obtemElementoTopo()
      {
         if (!vazia())
            return this.item[this.numeroElementos - 1];
         else
            Console.WriteLine("Pilha vazia!\n");
         return 0;
      }

      // Procura elemento e troca de lugar com o do numeroElementoso
      public bool procuraElemento(int x)
      {
         bool found = false;
         int pos = this.numeroElementos - 1;
         int elemtop = desempilha();
         int temp;
         Pilha aux = new Pilha();

         Console.WriteLine("Procurando elemento {0} ...", x);

         do
         {
            temp = desempilha();
            aux.empilha(temp);
            pos--;
         } while (this.item[pos] != x);

         if (this.item[pos] == x)
         {
            found = true;
            empilha(elemtop);
            elemtop = aux.desempilha();
            do
            {
               empilha(aux.desempilha());
            } while (aux.obtemTamanho() > 0);
            empilha(elemtop);
         }

         return found;
      }

      // Obtem tamanho da pilha
      public int obtemTamanho()
      {
         return this.numeroElementos;
      }

      // Exibe a pilha
      public void imprime()
      {
         Console.WriteLine("");
         for (int i = this.numeroElementos - 1; i >= 0; i--)
            Console.WriteLine("  {0}  ", this.item[i]);
         Console.WriteLine("");
      }

      // Copia a pilha em ordem normal
      public Pilha copiaNormal()
      {
         Pilha saux = new Pilha();
         Pilha sfinal = new Pilha();

         do
         {
            saux.empilha(this.desempilha());

         } while (!this.vazia());

         do
         {
            sfinal.empilha(saux.desempilha());
         } while (!saux.vazia());

         return sfinal;
      }

      // Copia a pilha em ordem invertida
      public Pilha copiaInvertida()
      {
         Pilha sfinal = new Pilha();

         do
         {
            sfinal.empilha(this.desempilha());
         } while (!this.vazia());

         return sfinal;
      }
   }

   class Program
   {
      static void Main(string[] args)
      {
         Console.WriteLine("\n -= TAD Pilha (Stack) =-\n");

         Pilha s = new Pilha();

         s.empilha(10);
         s.empilha(4);
         s.empilha(1);
         s.empilha(7);
         s.empilha(8);
         s.empilha(5);
         s.empilha(2);
         s.obtemElementoTopo();

         Console.WriteLine("\nA pilha tem {0} elementos.", s.obtemTamanho());
         s.imprime();
         Console.ReadLine();

         if (!s.procuraElemento(1))
            Console.WriteLine("Elemento 1 nao encontrado!\n");
         s.imprime();
         Console.ReadLine();

         Console.WriteLine("Copiando a pilha em ordem normal...");
         s = s.copiaNormal();
         s.imprime();
         Console.ReadLine();

         Console.WriteLine("Copiando a pilha em ordem invertida...");
         s = s.copiaInvertida();
         s.imprime();
         Console.ReadLine();

         s.desempilha();
         s.desempilha();
         s.desempilha();
         s.obtemElementoTopo();

         Console.WriteLine("\nA pilha tem {0} elementos.", s.obtemTamanho());
         s.imprime();
         Console.ReadLine();

         s.empilha(17);
         s.empilha(52);
         s.empilha(48);
         s.empilha(35);
         s.empilha(12);
         s.empilha(19);
         s.empilha(63);
         s.empilha(85);
         s.empilha(25);
         s.empilha(31);
         s.obtemElementoTopo();

         Console.WriteLine("\nA pilha tem {0} elementos.", s.obtemTamanho());
         s.imprime();

         Console.WriteLine("\n");
         Console.ReadLine();
      }
   }
}

Até a próxima.

_________________
"Faça as coisas o mais simples que você puder,
porém, não as mais simples." Albert Einstein

avatar
Evandro Abu Kamel
Administrador
Administrador

Número de Mensagens : 222
Idade : 28
Data de inscrição : 11/03/2009

Ver perfil do usuário http://forum.clubedosistema.com

Voltar ao Topo Ir em baixo

Voltar ao Topo

- Tópicos similares

 
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum