Stack (LIFO)

Publicado por Enzo de Brito Ferber 08/04/2006

[ Hits: 8.408 ]

Homepage: http://www.maximasonorizacao.com.br

Download stack.c




Implementaçao de uma pilha, usando listas singularmente encadeadas. Muito bom para ententer o funcionamento de listas singularmente encadeadas.

  



Esconder código-fonte

/*
 * Programa: Stack
 * Arquivo: stack.c
 * Autor: Enzo Ferber 'Slackware_10'
 */
 
#include <stdio.H>
#include <stdlib.H>
#include <string.H>

//macros para simplificar alocacao de memoria
#define MALLOC(a) (a *)malloc(sizeof(a)); 
#define CALLOC(n,a) (a *)calloc(n,sizeof(a)); 

struct s__stack{
    int info;
    struct stack *next;
};

typedef struct s__stack stack; //novo tipo de dado 'stack'

stack *head; //variavel global para evitar muitas variaveis locais
stack *temp; //variavel global para evitar muitas variaveis locais

unsigned int num_entradas; //para contador do menu principal

//Protótipos de funcoes do programa
void push(int); //inserir
void pop(void); //deletar
void display(void); //mostar
void menu(void); //menu principal
void clear(void); //limpa tela
void ins(void); //valor a inserir
void flush(void); //limpa buffer do teclado

void push(int valor)
{
    num_entradas++; //apenas para o mostrador na tela principal
    temp = MALLOC(stack); //ou head = CALLOC(1,stack);
    temp->info = valor; //atribui o valor
    temp->next = head; //insere no inicio da lista
    head = temp; //coloca o novo elemento como primeiro (LIFO)
}

void ins(void){
    clear();
    int valor; 
    printf("Valor (decimal): ");
    flush(); 
    scanf("%d", &valor);
    push(valor);
    menu();
}   

void pop(void)
{
    num_entradas--; //apenas para o mostrador na tela principal
    stack *t; //novo ponteiro
    t = head->next; //t contem o endereco do segundo elemento (penultimo a entrar)
    free(head); //libera espaco previamente alocado para o ultimo elemento que entrou
    head = t; //transforma o segundo elemento em primeiro
}

void display(void)
{
    stack *aux = head; //para nao haver distruicao da pilha
    clear(); //limpa a tela
    printf("Pilha\n-----\n");
    if(!aux){ //se nao houver elementos...
        printf("Pilha vazia.\n"); //informa erro
        getch();  //espera uma tecla ser pressionada
        menu();  //retorna ao menu principal
    }
    while(aux){ //enquando nao for NULO
        printf("%d\n", aux->info); //imprimi o valor
        aux = aux->next; //faz aux apontar para o proximo item
    }
    getch(); //espera uma tecla ser pressionada
}

void clear(void){
    system("clear");
}

void flush(void){
    __fpurge(stdin);
}

void menu(void){
    int op;
    while(1){
        clear();
        if(num_entradas != 0) printf("\n\n\tSTACK\n\n\tTamanho: %d\n\n", num_entradas);
        else printf("\n\n\tSTACK\n\n\tTamanho: VAZIA\n\n");
        printf("\t1. Inserir\n");
        printf("\t2. Retirar\n");
        printf("\t3. Mostar\n");
        printf("\t4. Sair\n\n");
        printf("\tSua opcao: ");
        flush();
        scanf("%d", &op);
        switch(op){
            case 1:
                ins();
                break;
            case 2:
                pop();
                break;
            case 3:
                display();
                break;
            case 4:
                free(head);
                free(temp);
                exit(0);
        }
    }
}


int main(void){
    head = NULL;
    menu();
    return 0;
}

/*Nota:
 * 
 * Este código é uma implementação de 'stack'(pilha) usando o método de listas singularmente
 * encadeadas. O LIFO (Last In First Out - Ultimo a entrar, primeiro a sair), é
 * o usado na mémoria de nossos computadores. Segue abaixo um esquema de um programa 
 * escrito em C:
 *
 *    ______________
 *   | PILHA        |  ||  (seta para baixo - direção para onde a pilha cresce)
 *   |______________|  \/
 *   | HEAP         |  /\  (seta para cima - direção para onde o heap cresce)
 *   |______________|  ||
 *   | VARS GLOBAIS |
 *   |______________|
 *   | PROGRAMA     |
 *   |______________|
 *
 * P.S.: uma grande parte dos compiladores C usam pilhas quando passam argunmentos
 *       para funções.
 */

Scripts recomendados

[C] POSIX Threads

Jogo Snake (com gráficos)

Script MakePach para correção de platarforma 32 bits para 64

Imprimindo uma arvore graficamente

Rotina para controle de portas paralelas em C.


  

Comentários
[1] Comentário enviado por brunodias em 09/04/2006 - 00:22h

a funcao display(), nao esta utilizando o conseito de pilha !, deve-se desemplihar guardando numa pilha auxiliar enquanto exibimos os valores que estao sendo desempilhados, e depois reemplihar
novamente da pilha auxiliar parar a pilha.

Eu humildimente acho que este tipo de assunto nao deviria ser aboradado aqui na comunidade, pois se trata apenas de um coneito de programacao. concorda ?

um abraco !

[2] Comentário enviado por EnzoFerber em 09/04/2006 - 10:23h

Concordo, mas os que, como eu, gostam de entender o funcionamento das coisas, esse é um bom programa para entender o funcionamento da pilha de memoria de nossos computadores. E eu nao esqueci que quando acessamos dados em uma pilha, eles sao destruidos. Nestas funcoes, eu usei apenas ponteiros referencias. Achei que ficaria mais fácil de entender, pois o principal objetivo deste codigo é mostrar como listas encadeadas funcionam. A implementaçao de LIFO, normalmente é feita com vetores.

Obrigado pelo comentário. Discutir pontos de vista sempre aumentam o conhecimento.



Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts