Filas (Queues)

Ver o tópico anterior Ver o tópico seguinte Ir em baixo

Filas (Queues)

Mensagem por Evandro Abu Kamel em Sex 11 Set 2009, 20:43

Olá pessoal, enquanto estava na monitoria hoje, achei um PDF bem bacana que esplica bastante coisa sobre filas, coisas quem nem vimos ainda, e até um pouco complexas, mas o começo, creio que todos consigam entender.

Os códigos estão em C++, mas tentem abstrair a lógica, não se preocupem com picuinhas da linguagem.

Download - Filas (Queues)

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

Re: Filas (Queues)

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

Segue abaixo a implementação do TAD Pilha usando vetor.

TAD Fila (Queue)

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

namespace ClassQueue
{
   class Queue
   {
      const int MaxTam = 10;
      int[] store;
      int head, n;

      public Queue()
      {
         this.store = new int[MaxTam];
         this.head = 1;
         this.n = 0;
      }

      public void enqueue(int x)
      {
         Console.WriteLine("Enfileirando: " + x);
         if (this.n == this.store.Length)
            grow();
         int pos = (this.n + this.head) % this.store.Length;
         this.store[pos] = x;
         this.n++;
      }

      public int dequeue()
      {
         if (isEmpty())
            Console.WriteLine("\nA fila está vazia!");
         int pos = this.head % this.store.Length;
         this.n--;
         this.head++;
         return this.store[pos];
      }

      public int peek()
      {
         if (isEmpty())
            Console.WriteLine("\nA fila está vazia!\n");
         int pos = this.head % this.store.Length;
         return this.store[pos];
      }

      public bool isEmpty()
      {
         return (this.n == 0);
      }

      public void grow()
      {
         int ntam = this.store.Length + 1;
         int[] newstore = new int[ntam];
         int back = ((this.head + this.n) % this.store.Length) - 1; // ultimo da fila           
         int pos = this.head; // primeiro da fila
         int cont = 0;

         do
         {
            newstore[cont + 1] = this.store[pos];
            pos++;
            if (pos >= this.store.Length)
               pos = 0;
            cont++;
         }
         while (cont < this.store.Length);

         this.store = newstore;
      }

      public void print()
      {
         Console.WriteLine("\nA fila esta assim: ");
         int pos = this.head; // primeiro da fila
         int back = ((this.head + this.n) % this.store.Length) - 1; // ultimo da fila
         int cont = 0;

         do
         {
            Console.Write(" {0} ", this.store[pos]);
            pos++;
            if (pos >= this.store.Length)
               pos = 0;
            cont++;
         }
         while (cont < n);
      }
   }

   class Program
   {
      static void Main(string[] args)
      {
         Queue q = new Queue();

         Console.WriteLine("\n -= TAD Fila =-\n");

         q.enqueue(3);
         q.enqueue(6);
         q.enqueue(11);
         q.enqueue(17);
         q.enqueue(23);
         q.enqueue(25);
         q.enqueue(28);
         q.enqueue(31);
         q.enqueue(36);
         q.enqueue(38);

         Console.ReadLine();

         q.print();
         Console.WriteLine("\nO primeiro da fila eh: {0} \n", q.peek());

         q.enqueue(44);
         q.enqueue(56);

         q.print();
         Console.WriteLine("\nO primeiro da fila eh: {0} \n", q.peek());

         Console.WriteLine("Desenfileirando " + q.dequeue());
         Console.WriteLine("Desenfileirando " + q.dequeue());
         Console.WriteLine("Desenfileirando " + q.dequeue());

         q.print();
         Console.WriteLine("\nO primeiro da fila eh: {0} \n", q.peek());

         q.enqueue(61);

         q.print();
         Console.WriteLine("\nO primeiro da fila eh: {0} \n", q.peek());

         Console.WriteLine("Desenfileirando " + q.dequeue());

         q.print();
         Console.WriteLine("\nO primeiro da fila eh: {0} \n", q.peek());

         Console.WriteLine("\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 Pilha no código deste programa.


Fila (Queue) com métodos de copiar

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

namespace ClassFila
{
   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 Fila
   {
      const int MaxTam = 20;
      int[] item;
      int frente, n;

      // Construtor padrao
      public Fila()
      {
         this.item = new int[MaxTam];
         this.frente = 1;
         this.n = 0;
      }

      // Insere um elemento no final da fila
      public void insere(int x)
      {
         Console.WriteLine("Enfileirando: " + x);
         if (this.n == this.item.Length)
            grow();
         int pos = (this.n + this.frente) % this.item.Length;
         this.item[pos] = x;
         this.n++;
      }

      // Retorna e Retira o primeiro elemento da fila
      public int retira()
      {
         if (vazia())
            Console.WriteLine("\nA fila esta vazia!");
         int pos = this.frente % this.item.Length;
         this.n--;
         this.frente++;
         return this.item[pos];
      }

      // Retorna o primeiro elemento da fila
      public int obtemPrimeiro()
      {
         if (vazia())
            Console.WriteLine("\nA fila esta vazia!\n");
         int pos = this.frente % this.item.Length;
         return this.item[pos];
      }

      // Retorna se a fila esta vazia ou nao
      public bool vazia()
      {
         return (this.n == 0);
      }

      // Aumenta em uma posicao o tamanho da fila
      public void grow()
      {
         int ntam = this.item.Length + 1;
         int[] newitem = new int[ntam];
         int back = ((this.frente + this.n) % this.item.Length) - 1; // ultimo da fila           
         int pos = this.frente; // primeiro da fila
         int cont = 0;

         do
         {
            newitem[cont + 1] = this.item[pos];
            pos++;
            if (pos >= this.item.Length)
               pos = 0;
            cont++;
         }
         while (cont < this.item.Length);

         this.item = newitem;
      }

      // Imprime a fila
      public void imprime()
      {
         Console.WriteLine("\nA fila esta assim: ");
         int pos = this.frente; // primeiro da fila
         int back = ((this.frente + this.n) % this.item.Length) - 1; // ultimo da fila
         int cont = 0;

         do
         {
            Console.Write(" {0} ", this.item[pos]);
            pos++;
            if (pos >= this.item.Length)
               pos = 0;
            cont++;
         }
         while (cont < n);
      }

      // Copia a fila em ordem normal
      public Fila copiaNormal()
      {
         Fila qfinal = new Fila();

         Console.WriteLine("\nCopiando fila em ordem normal...");

         do
         {
            qfinal.insere(this.retira());
         } while (!this.vazia());

         return qfinal;
      }

      // Copia a fila em ordem invertida
      public Fila copiaInvertida()
      {
         Pilha saux = new Pilha();
         Fila qfinal = new Fila();

         Console.WriteLine("\nCopiando fila em ordem invertida...");

         do
         {
            saux.empilha(this.retira());
         } while (!this.vazia());

         do
         {
            qfinal.insere(saux.desempilha());
         } while (!saux.vazia());

         return qfinal;
      }
   }

   class Program
   {
      static void Main(string[] args)
      {
         Fila q = new Fila();

         Console.WriteLine("\n -= TAD Fila =-\n");

         q.insere(3);
         q.insere(6);
         q.insere(11);
         q.insere(17);
         q.insere(23);
         q.insere(25);
         q.insere(28);
         q.insere(31);
         q.insere(36);
         q.insere(38);

         q.imprime();
         Console.WriteLine("\nO primeiro da fila eh: {0} \n", q.obtemPrimeiro());
         Console.ReadLine();

         q = q.copiaNormal();
         q.imprime();
         Console.ReadLine();

         q = q.copiaInvertida();
         q.imprime();
         Console.ReadLine();

         q.insere(44);
         q.insere(56);

         q.imprime();
         Console.WriteLine("\nO primeiro da fila eh: {0} \n", q.obtemPrimeiro());
         Console.ReadLine();

         Console.WriteLine("Retirando " + q.retira());
         Console.WriteLine("Retirando " + q.retira());
         Console.WriteLine("Retirando " + q.retira());

         q.imprime();
         Console.WriteLine("\nO primeiro da fila eh: {0} \n", q.obtemPrimeiro());
         Console.ReadLine();

         q.insere(61);

         q.imprime();
         Console.WriteLine("\nO primeiro da fila eh: {0} \n", q.obtemPrimeiro());
         Console.ReadLine();

         Console.WriteLine("Retirando " + q.retira());

         q.imprime();
         Console.WriteLine("\nO primeiro da fila eh: {0} \n", q.obtemPrimeiro());

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

Bons estudos.

_________________
"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

Ver o tópico anterior Ver o tópico seguinte Voltar ao Topo

- Tópicos similares

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