LIFO

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em ciência da computação, LIFO (acrônimo para a expressão inglesa Last In, First Out que, em português significa último a entrar, primeiro a sair) refere-se a estruturas de dados do tipo pilha. É equivalente a FILO, que significa First In, Last Out .

O conceito de pilha é amplamente utilizado na informática, como, por exemplo, durante a execução de um programa, para o armazenamento de valores de variável local a um bloco e também para conter o endereço de retorno do trecho de programa que chamou a função ou procedimento atualmente em execução.

Usa-se os termos push e pop para denominar a inserção e remoção de elementos da pilha, respectivamente. Usa-se o termo top para consultar o elemento do topo da pilha, sem o remover.

Uma pilha é uma lista linear na qual o primeiro elemento a entrar é o último elemento a sair. Ela possui apenas uma entrada, chamada de topo, a partir da qual os dados entram e saem dela.

Inserção, remoção e consulta do elemento de topo[editar | editar código-fonte]

A inserção (PUSH) é o método que insere um elemento no topo de uma Pilha. Já a remoção (POP) é o método que remove um elemento do topo de uma Pilha.

Em programação estruturada temos:

/** Protótipo Na Linguagem C
 *  Para uma PILHA de elementos inteiros
 */
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include "pilha.h"
#define N 200
 
struct pilha{
 
   int v[N];
   int topo;
};
 
Pilha* criar(){
   Pilha *p = (Pilha*) malloc(sizeof(Pilha));
   p->topo = -1;
    return(p);
}
 
void inserir(Pilha *p, int valor){
   if(p->topo == N-1) printf("A fila está cheia");
   else{
      p->topo++;
      p->v[p->topo] = valor;	
   }
}
 
int vazia(Pilha *p){
  if(p->topo == -1) return 1;
  else return 0;
}
 
int remover(Pilha *p){
   int i, valor;
   if(vazia(p)){ printf("A fila está vazia, não é possivel fazer remoção");
    exit(1);
   }
   valor = p-> v[p->topo];
   p->topo--;
   return(valor); 
}
 
void imprimir(Pilha *p){
 
    printf("\nO topo da Pilha é  %d", p->v[p->topo]);
}
 
void liberar(Pilha *p){
  free(p);
}


Exemplo de utilização da pilha substituindo recursão no cálculo do Fatorial de N, implementado em Java no mais puro estilo da linguagem C

/**
* Fatorial de N utilizando o conceito de pilha
*@autor Tarcnux
*@param N Inteiro
*
* Para compilar
* javac Fatorial.java
*
* Para rodar
* java Fatorial
*/
 
import java.util.Stack;
import java.util.Scanner;
 
class Fatorial 
{
  public static void main (String[] args)
  {
    Scanner scan = new Scanner ( System.in );
    int n=1;
    System.out.print("\nDigite um numero: ");   
    n = scan.nextInt();
    Fatorialx(n);
 
  }
 
  public static void Fatorialx( int N )
  {
 
        Stack <Integer> pilha = new Stack<Integer>();
	int fatorial = 1, aux = N;
 
	//Empilha
	while(aux > 1)
		pilha.push(aux--); //Empilha e depois decrementa
 
	while(!pilha.empty()) //Enquanto há elementos na pilha
		fatorial *= pilha.pop(); //Desempilha e calcula o Fatorial
 
	System.out.println("O fatorial de " + N + " eh: " + fatorial);
  }
}

Outras estruturas algébricas usadas em Ciências da Computação[editar | editar código-fonte]

Ver também[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]

Ícone de esboço Este artigo sobre Informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.