[Tutorial] Entendendo o que é uma Pilha "Stack"

cooler_ · Fevereiro 16, 2010

este “post” voltamos com assunto mais Geek

com nosso “C ansi” algo mais “rock and roll” para aqueles que esta boiando

em artigos de segurança ou de sistemas operacionais por ai…

Uma pilha(stack) é um inverso de uma fila ou seja ultimo a entrar primeiro

a sair o que é chamado de “LIFO” pelos programadores em C, o que quer

dizer “Last in,First out”,muitos compiladores usam pilha para

passar argumentos inclusive sistemas operacionais usam isso em

escalonamento de memória.

veja nesta imagem as moedas são como se fosse uma pilha

Imagem Postada

Bem se você estuda segurança em “T.I” você

tem obrigação em saber o que é “stack” pois no caso do “Buffer Overflow”

nada mais é que uma pilha que é passada do seu limite,Voltamos para Pilha

vou mostrar um exemplo simples de pois um exemplo de caso de uso.

Claro que não vou dar exemplo avançado usando “threads” ou mesmo “fork”

um exemplo usando lógica ja vai ajudar…

Primeiro exemplo meio mediogre mais demonstra a idéia

#include <stdio.h>
#include <stdlib.h>
 
//maximo da pilha
#define SIZE 10
#define w printf
 
// funções de colocar dado na pilha e retirar
void push(int i);
int pop(void);
 
//definindo ponteiros
int *tos, *p1, stack[SIZE];
 
//nosso programa
int main() {
	int value;
	tos = stack; 
	p1 = stack;
	do{
		w("Digite o valor(0 para ver o topo): ");
		scanf("%d",&value);
		if(value!=0)push(value);
		else w("\nValor do topo é %d\n", pop());
	}while(value!=-1);
	return 0;
}
 
void push(int i) {
	p1++;
	if(p1==(tos+SIZE)) {
		w("\nEstouro da pilha(push)");
		exit(1);
	}
	*p1 = i;
}
 
int pop(void) {
	if(p1==tos) {
		w("\nEstouro da pilha(pop)");
		exit(1);
	}
	p1--;
	return *(p1+1);
}

para quem não pegou a idéia olhe a imagem

Imagem Postada

Agora vamos um exemplo para gente grande com problema e solução para o mesmo

//  Site: BotecoUnix.com.br
//  Autor: Antonio Cooler  e-mail:tony.unix@yahoo.com.br
//  Licença: BSD
//  Baseado nos ensinamentos do livro do K&R e do livro C completo e total
// 
// = Objetivo
//  Um deposito de Bebidas precisa manter o controle de caixas empilhadas
//  cada caixa tem no máximo 12 garrafas,faça um programa para cadastrar
//  nome da caixa,quantidade de garrafas e preço de cada garrafa,programa
//  deve ter opção de remover caixa empilhada e mostrar caixas empilhadas com
//  total de custo da caixa somando as garrafas...
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
// Número maximo de chars nas vars
#define MAX 30
// Número maximo de caixas
#define BOX 20
// Macro do printf
#define w printf 
 
// estrutura usada
typedef struct caixa {
  char nome[MAX];
  int garrafas;
  float valor;
} caixa;
 
//pegando entrada do usuário e retorna com os mesmos
caixa adiciona_caixa() {
 int i;
 caixa p;
 w("informe alguns dados\n");
 w("o Nome: \n");
 getchar();
 fgets(p.nome, MAX, stdin);
 i = strlen(p.nome)-1;
  if(p.nome[i] == '\n') {
      p.nome[i] = '\0';
  }
 w("A quantidade de garrafas:\n"); scanf("%d",&(p.garrafas));
// maximo de garrafas por caixa é 12 setamos isso aqui numa condição magica do C
 p.garrafas=(p.garrafas>12)?12:p.garrafas;
 w("O preço:\n"); scanf("%f",&(p.valor));
 return p;
}
//mostrando banner do programa de konsole
char opcao_menu() {
 int i;
 char escolha[MAX];
 char *banner[] = {
        "--------------------------",
	"Programa Pilha de caixas",
	"coded by Cooler",
	"(L)istar Caixas Empilhadas",
	"(E)mpilhar Caixa",
	"(D)esempilhar Caixa",
	"(S)air do programa",
        "--------------------------",
	"> ",
	};
	for(i=0; i<=9; i++) w(" %s\n",banner[i]); 
        scanf("%s", &escolha[MAX]);
        return escolha[MAX];
}
 
int main(int args, char * arg[]) {
 int x,y,n;
 float total;
 char op;
// ponteiro da nossa estrutura
 caixa *cad;
 y=0;
// alocamos dados na memória
 cad=(caixa *)calloc(BOX,sizeof(caixa));
 while(op!='S') {
  op=opcao_menu();
  if(op=='L') { 
// Mostra a lista de caixas
   w("\n Nome      Garrafas     Preço   Total\n");
   for(x=y-1; x>=0; x--) w(" %6s %8d %12.2f %7.2f\n", 
                             cad[x].nome, 
                             cad[x].garrafas, 
                             cad[x].valor,
                             total=cad[x].garrafas*cad[x].valor); 
  }
// Adiciona uma caixa e chama a função "adiciona caixa"
  if(op=='E') { cad[y]=adiciona_caixa(); y++; }
// remove caixa,subtrai o apontador da proxima adição de dados substitui o dado pelo
// Escolhido
  if(op=='D') { y--; }
 }
 return 0;
}

Bem galera espero ter ajudado

_Isis_ · Fevereiro 17, 2010

Alguns comentários:

[/size][color=#880000][size=2]#define w printf[/size][/color][size=2]

Nunca faça isso. Printf já é um nome bastante sugestivo. Trocar isso por uma letra do alfabeto é medonho e igual a declarar variáveis como 'x', 'p1' e constantes mágicas que aparecem perdidas em programas sem maiores explicações.

você não libera os ponteiros. Bem vindo, memory leak.

[/size][color=#880000][size=2]// maximo de garrafas por caixa é 12 setamos isso aqui numa condição magica do C[/size][/color][size=2]

Evite comentários que façam parecer que o código se parece com algo astrológico/esotérico/místico. Isso não existe. Linguagens possuem estruturas bem definidas. Aquilo não é uma condição mágica do C, aquilo se chama operador ternário.

[/size][size=2]fgets[/size][size=2]([/size][size=2]p[/size][size=2].[/size][size=2]nome[/size][size=2],[/size][size=2] MAX[/size][size=2],[/size][size=2] stdin[/size][size=2]);[/size]
[size=2]i = strlen(p.nome)-1;[/size]
[size=2]if (p.nome[i] == '\n') {[/size]
[size=2]  p.nome[i] == '\0';[/size]
[size=2]}[/size]
[size=2]

Poderia ser substituído por (*strchr(p.nome, '\n')) = '\0';

A atribuição de caixas também gera trabalho a mais para quem está controlando o estoque: se eu possuir N garrafas, sendo N > 12, vou ter que digitar N/12 vezes o número de garrafas p/ armazenar a quantidade correta de caixas, o que poderia ser feito automaticamente com ceil(N/12), alocando memória diretamente na inserção da caixa.

[/size][size=2]while(op!='S')

O que te dá certeza de que existe um 'S' em memória se você não definiu a variável?

A função de menu trabalha com leitura e retorno de string, apesar do tipo de retorno ser char e você usar um char no main.

cooler_ · Fevereiro 17, 2010

valeu _ISIS_ pelas dica, bom a macro w

geralmente eu uso o "sed" com "s/w/printf/",ou AWK para trocar tudo, o "w" uso para fazer o codigo rapidamente...

a respeito do memory leak vou dar uma olhada, o que você costuma fazer para evitar isso ?

esquema mágico la só condição simples com ? : como você falou ...

quanto a condição "S" esta definida em "escolha[macro]" na função do banner

_Isis_ · Fevereiro 17, 2010

valeu _ISIS_ pelas dica, bom a macro w

geralmente eu uso o "sed" com "s/w/printf/",ou AWK para trocar tudo, o "w" uso para fazer o codigo rapidamente...

Isso não justifica. Depois aparece gente enfiando macro em tudo quanto é canto nos programas, tornando eles mais ilegíveis que os programas que usam goto.

a respeito do memory leak vou dar uma olhada, o que você costuma fazer para evitar isso ?

Procure por memory leak no google.

quanto a condição "S" esta definida em "escolha[macro]" na função do banner

E onde no main você lê a opção antes de entrar no while?

char op;
// ponteiro da nossa estrutura
caixa *cad;
y=0;
// alocamos dados na memória
cad=(caixa *)calloc(BOX,sizeof(caixa));
while(op!='S') {

cooler_ · Fevereiro 17, 2010

_ISIS_ novamente obrigado, implementei o programa tirei as POG e resolvi o problema do memory leak

agora só tem um problema que resolvi um "getchar" não sei se pessoal vê como POG...

/*
  Site: BotecoUnix.com.br
  Autor: Antonio Cooler  e-mail:tony.unix@yahoo.com.br
 Licença: BSD
  Baseado nos ensinamentos do livro do K&R e do livro C completo e total
 
 = Objetivo
  Um deposito de Bebidas precisa manter o controle de caixas empilhadas
  cada caixa tem no máximo 12 garrafas,faça um programa para cadastrar
  nome da caixa,quantidade de garrafas e preço de cada garrafa,programa
  deve ter opção de remover caixa empilhada e mostrar caixas empilhadas com
 total de custo da caixa somando as garrafas...
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Número maximo de chars nas vars
#define MAX 30
// Número maximo de caixas
#define BOX 20 

void opcao_menu() {
 int i;
 char *banner[] = {
        "--------------------------",
	"Programa Pilha de caixas",
	"coded by Cooler",
	"(1)Listar Caixas Empilhadas",
	"(2)Empilhar Caixa",
	"(3)Desempilhar Caixa",
	"(4)Sair do programa",
        "--------------------------",
	"> "
	};
 for(i=0; i<=7; i++) printf("%s\n",banner[i]);
}

// estrutura usada
typedef struct caixa {
  char nome[MAX];
  int garrafas;
  float valor;
} caixa;

//pegando entrada do usuário e retorna com os mesmos
caixa adiciona_caixa() {
 caixa p;

 printf("informe alguns dados\n");
 printf("o Nome: \n");
  fgets(p.nome, sizeof(p.nome), stdin);
  p.nome[strlen(p.nome)-1] = '\0';
 printf("A quantidade de garrafas:\n"); 
 scanf("%d",&(p.garrafas));
// maximo de garrafas por caixa é 12 setamos isso aqui numa condição simples
 p.garrafas=(p.garrafas>12)?12:p.garrafas;
 printf("O preço:\n"); scanf("%f",&(p.valor));
 return p;
}

int main(int args, char * arg[]) {
 int x,y,op;
 float total;
// ponteiro da nossa estrutura
 caixa *cad;
 y=0;
// alocamos dados na memória
 cad=(caixa *)calloc(BOX,sizeof(caixa));
 while(op!=4) {
   opcao_menu();
   scanf("%d",&op); 
   getchar();
  if(op==1) { 
// Mostra a lista de caixas
   printf("\n Nome      Garrafas     Preço   Total\n");
   for(x=y-1; x>=0; x--) printf(" %6s %8d %12.2f %7.2f\n", 
                             cad[x].nome, 
                             cad[x].garrafas, 
                             cad[x].valor,
                             total=cad[x].garrafas*cad[x].valor); 
  }
// Adiciona uma caixa e chama a função "adiciona caixa"
  if(op==2) { 
    cad[y]=adiciona_caixa(); 
    y++;
  }
// remove caixa,subtrai o apontador da proxima adição de dados substitui o dado pelo
// Escolhido
  if(op==3) y--; 
 }
// isso deve resolver memory leak, pensei que tinha isso no code até fiquei confuso xD
 free(cad);
 return 0;
}

_Isis_ · Fevereiro 18, 2010

Mano, você continua não lendo nada antes de usar no while...Presta atenção.

int x,y,op;
float total;
// ponteiro da nossa estrutura
caixa *cad;
y=0;
// alocamos dados na memória
cad=(caixa *)calloc(BOX,sizeof(caixa));
while(op!=4) {

Essa variável tem um valor totalmente desconhecido em tempo de execução.

cooler_ · Fevereiro 18, 2010

setei var OP para zero agora

mas então testei com GCC num gentoo linux sem problemas

com gcc -Wall -o code code.c

/*
  Site: BotecoUnix.com.br
  Autor: Antonio Cooler  e-mail:tony.unix@yahoo.com.br
 Licença: BSD
  Baseado nos ensinamentos do livro do K&R e do livro C completo e total
 
 = Objetivo
  Um deposito de Bebidas precisa manter o controle de caixas empilhadas
  cada caixa tem no máximo 12 garrafas,faça um programa para cadastrar
  nome da caixa,quantidade de garrafas e preço de cada garrafa,programa
  deve ter opção de remover caixa empilhada e mostrar caixas empilhadas com
 total de custo da caixa somando as garrafas...
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Número maximo de chars nas vars
#define MAX 30
// Número maximo de caixas
#define BOX 20 

void opcao_menu() {
 int i;
 char *banner[] = {
        "--------------------------",
        "Programa Pilha de caixas",
        "coded by Cooler",
        "(1)Listar Caixas Empilhadas",
        "(2)Empilhar Caixa",
        "(3)Desempilhar Caixa",
        "(4)Sair do programa",
        "--------------------------",
        "> "
        };
 for(i=0; i<=7; i++) printf("%s\n",banner[i]);
}

// estrutura usada
typedef struct caixa {
  char nome[MAX];
  int garrafas;
  float valor;
} caixa;

//pegando entrada do usuário e retorna com os mesmos
caixa adiciona_caixa() {
 caixa p;

 printf("informe alguns dados\n");
 printf("o Nome: \n");
  fgets(p.nome, sizeof(p.nome), stdin);
  p.nome[strlen(p.nome)-1] = '\0';
 printf("A quantidade de garrafas:\n"); 
 scanf("%d",&(p.garrafas));
// maximo de garrafas por caixa é 12 setamos isso aqui numa condição simples
 p.garrafas=(p.garrafas>12)?12:p.garrafas;
 printf("O preço:\n"); scanf("%f",&(p.valor));
 return p;
}

int main(int args, char * arg[]) {
 int x,y,op=0;
 float total;
// ponteiro da nossa estrutura
 caixa *cad;
 y=0;
// alocamos dados na memória
 cad=(caixa *)calloc(BOX,sizeof(caixa));
 while(op!=4) {
   opcao_menu();
   scanf("%d",&op); 
   getchar();
  if(op==1) { 
// Mostra a lista de caixas
   printf("\n Nome      Garrafas     Preço   Total\n");
   for(x=y-1; x>=0; x--) printf(" %6s %8d %12.2f %7.2f\n", 
                             cad[x].nome, 
                             cad[x].garrafas, 
                             cad[x].valor,
                             total=cad[x].garrafas*cad[x].valor); 
  }
// Adiciona uma caixa e chama a função "adiciona caixa"
  if(op==2) { 
    cad[y]=adiciona_caixa(); 
    y++;
  }
// remove caixa,subtrai o apontador da proxima adição de dados substitui o dado pelo
// Escolhido
  if(op==3) y--; 
 }
// isso deve resolver memory leak, pensei que tinha isso no code até fiquei confuso xD
 free(cad);
 return 0;
}

mas uma ves obrigado ;)

_Isis_ · Fevereiro 18, 2010

Warnings não são erros.

Se o compilador exibir somente warnings, o programa ainda executa, mas nada garante que vai funcionar do jeito que você quer sem problemas. Os exemplos clássicos são o uso do gets (que aqui a gente repete a cada usuário novo que posta, porque parece difícil demais p/ um professor falar sobre buffer overflow) e conversões entre tipos (principalmente ponteiros).

Os erros é que não geram o binário.

Mesmo usando o -Wall o compilador não avisa sobre certas coisas. Para ter o resto dos avisos você precisa usar -Wextra.

Um detalhe: mesmo compilando com -O3 e -Wuninitialized, o gcc 4.3.2 não avisa sobre as variáveis não inicializadas. No Bugzilla marcaram p/ o 4.3.5, mas não sei se foi realmente corrigido.

cooler_ · Fevereiro 18, 2010

Warnings não são erros.

Se o compilador exibir somente warnings, o programa ainda executa, mas nada garante que vai funcionar do jeito que você quer sem problemas. Os exemplos clássicos são o uso do gets (que aqui a gente repete a cada usuário novo que posta, porque parece difícil demais p/ um professor falar sobre buffer overflow) e conversões entre tipos (principalmente ponteiros).

Os erros é que não geram o binário.

Mesmo usando o -Wall o compilador não avisa sobre certas coisas. Para ter o resto dos avisos você precisa usar -Wextra.

Um detalhe: mesmo compilando com -O3 e -Wuninitialized, o gcc 4.3.2 não avisa sobre as variáveis não inicializadas. No Bugzilla marcaram p/ o 4.3.5, mas não sei se foi realmente corrigido.

bom este argv do "-Wextra" nem sabia obrigado mesmo...

do bugzilla acho que já foi corrigido pois olhe versão que estou usando

cooler@gentoo ~ $ gcc --version
gcc (Gentoo 4.4.1 p1.0) 4.4.1
Copyright (C) 2009 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

pelo visto tenho milhares de programas meus para arrumar :(

Arquivado

[Tutorial] Entendendo o que é uma Pilha "Stack"

Recommended Posts

cooler_ 0

Compartilhar este post

Link para o post

Compartilhar em outros sites

_Isis_ 202

Compartilhar este post

Link para o post

Compartilhar em outros sites

cooler_ 0

Compartilhar este post

Link para o post

Compartilhar em outros sites

_Isis_ 202

Compartilhar este post

Link para o post

Compartilhar em outros sites

cooler_ 0

Compartilhar este post

Link para o post

Compartilhar em outros sites

_Isis_ 202

Compartilhar este post

Link para o post

Compartilhar em outros sites

cooler_ 0

Compartilhar este post

Link para o post

Compartilhar em outros sites

_Isis_ 202

Compartilhar este post

Link para o post

Compartilhar em outros sites

cooler_ 0

Compartilhar este post

Link para o post

Compartilhar em outros sites

Fixar div até atingir uma certa altura

Ajuda com Extends e envio para o banco

PHP+Codeginiter - Orientação para Impressão

Fóruns

Tempo Real

Informação importante