Saltar para o conteúdo

LIFO

Origem: Wikipédia, a enciclopédia livre.
 Nota: Se procura Pilha, uma bateria, veja Pilha.
Representação de uma LIFO com as operações push (empilhar) e pop (desempilhar).

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 estrutura 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.

Segue o exemplo abaixo a implementação de uma pilha de tamanho dinâmico, onde o usuário poderá interagir com a pilha(inserindo números , excluindo itens, listando itens da pilha) tudo isso usando alocação dinâmica de memória em C :

//(Micael Nascimento) 
#include <stdio.h>
#include <stdlib.h>

 typedef struct {
    int tam;
    int topo;
    int *vet;
}tp_pilha;

int pilha_vazia(tp_pilha *pilha){
    if(pilha->topo==-1){
        return 1;
    }
    else
        return 0;
}
void inserindo(tp_pilha *pilha){
    int numero;
    pilha->tam++;

    pilha->vet = (int*) realloc(pilha->vet,pilha->tam*sizeof(int));

    printf("insira numero:");
    scanf("%i",&numero);

    pilha->topo++;
    pilha->vet[pilha->topo]=numero;
}
void excluindo(tp_pilha *pilha){
    if(!pilha_vazia(pilha)){
        pilha->vet[pilha->topo]=NULL;
        pilha->topo--;
    }
    else
        printf("pilha vazia!\n");
}

void listar(tp_pilha *pilha){
    int i;
    int n = pilha->tam;

    if(!pilha_vazia(pilha)){
        for(i=n-1;i>=0;i--){
            if(pilha->vet[i]!=0){
            printf("%i\n",pilha->vet[i]);
       }
    }
    }
    else
         printf("pilha vazia!\n");
}

main(void){

    char verifica;

     tp_pilha pilha={0,-1,0};

    while(verifica!='s'){
        printf("(i)nserir/(l)istar/(e)xcluir/(s)air: ");
        fflush(stdin);
        scanf("%c",&verifica);

        switch(verifica){
            case'i':
                inserindo(&pilha);
                break;
            case'e':
                excluindo(&pilha);
                break;
            case'l':
                listar(&pilha);
                break;
            default:
                return 0;
        }
   }
//Micael Nascimento
}


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]

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.