Publicado em 16 de fev.

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

#cc

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

/applications/core/interface/imageproxy/imageproxy.php?img=http://www.businessburrito.com/images/coin-stack-small.jpg&key=b68f99333cfcf1b275327b9a386f8e2652925e7f5809c739848a54f515b08eaf" alt="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

/applications/core/interface/imageproxy/imageproxy.php?img=http://upload.wikimedia.org/wikibooks/en/a/a8/Programming-stack.png&key=0c2ee4052f3768c62b734f60b4535ece018393dead7f00217a4330fea9294c71" alt="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

Discussão (8)

Entre ou cadastre-se para participar da discussão

Entrar Criar conta

_Isis_· 17 de fev.

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]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_· 17 de fev.

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_· 17 de fev.

>
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_· 17 de fev.

_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_· 18 de fev.

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_· 18 de fev.

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

// 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_· 18 de fev.

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_· 18 de fev.

>
Warnings não são erros.

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 :(