Jump to content
polska

Stack, bem implementado?

Recommended Posts

polska

Depois de ver o texto da USACO, "More Search Techniques", onde falava de DFS, BFS e ID, fui pesquisar mais sobre estas técnicas e li que era comum implementar uma DFS com stacks e uma BFS com queus, então decidi tentar implementar uma stack, e isto foi o que fiz:

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

typedef struct stack
{
int nums[MAX];
int top;
}STACK;

//inicia stack
STACK init_stack( STACK *stack )
{
stack->top = -1;
return *stack;
}

//adiciona valor ao stack
void push( STACK *stack, int valor )
{
stack->top++; //incrementa 1
if( stack->top < MAX )
{
	stack->nums[stack->top] = valor; //se o stack não está cheio, adiciona valor no top (topo)
}
   else
    stack->top--; //decrementa caso falhe a condição
}

//apaga valor do stack
void pop( STACK *stack )
{
// Regra LIFO , last in - first out
if( stack->top > -1 )
{
	stack->nums[stack->top] = NULL; //se o stack não está vazio, coloca o valor do topo a NULL
	stack->top--; //decrementa o topo
}
}

void main()
{
STACK myStack;
int evento;

//inicializa o stack criado
init_stack( &myStack );

printf( "Insere elementos para adicionar ao stack ( 0 = sair ):\n ");
scanf( "%d", &evento );
while( evento != 0 )
{
 push( &myStack, evento );
 scanf( "%d", &evento );
}

if( myStack.top != -1 )
{
 printf( "Inseriste:\n" );
 for( int i=0; i<=myStack.top; i++ )
 {
  printf( "%d ", myStack.nums[i] );
 }

 while( myStack.top != -1 )
  pop( &myStack );

 printf( "\nExecutei a funcao de remover, ate o top ficar a -1 , vamos ver se funcionou!" );
 printf( "\nTop do stack: %d", myStack.top );
 printf( "\n" );

}

system( "PAUSE" );

Corrijam-me se estou a implementar mal, ou se falta alguma coisinha :D

Agradeço desde já :)

Edited by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
Rui Carlos

//adiciona valor ao stack
void push( STACK *stack, int valor )
{
stack->top++; //incrementa 1
if( stack->top < MAX )
{
	stack->nums[stack->top] = valor; //se o stack não está cheio, adiciona valor no top (topo)
}
}

Incrementar o top com a stack cheia é capaz de não ser lá muito boa ideia :)

Share this post


Link to post
Share on other sites
polska

//adiciona valor ao stack
void push( STACK *stack, int valor )
{
stack->top++; //incrementa 1
if( stack->top < MAX )
{
	stack->nums[stack->top] = valor; //se o stack não está cheio, adiciona valor no top (topo)
}
}

Incrementar o top com a stack cheia é capaz de não ser lá muito boa ideia :)

ahah, certo :D , de resto esta tudo bem?


Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
HappyHippyHippo

DFS (Depth first search) e BFS (Breadth first search) são metodologias de pesquisa em grafos ou nas suas degenerações, árvores.

Dizer que uma é mais usada em stacks e outra em queues é esticar o conceito, tanto do método de pesquisa como dos objectos a serem pesquisados


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
pmg

1) a tua funcao init_stack devolve um 'struct stack' (atraves do typedef STACK). Era melhor se ela nao devolvesse nada; a 'struct stack' completa sao mais de 400 bytes!

void init_stack(struct stack *stack) {
   stack->top = -1;
}

2) A funcao 'push' podia (devia?) devolver um status indicando se a operação correu bem ou a razão de ter corrido mal

int push(struct stack *stack, int valor) {
   stack->top++;
   if (stack->top < MAX) {
       stack->nums[stack->top] = valor;
   } else {
       stack->top--;
       return 1; /* SEM ESPACO */
   }
   return 0; /* OK */
}

3) a funcao 'pop' devia devolver o valor "popado" e um status para indicar se correu tudo bem ou se houve erro (tentativa de popar duma stack vazia)

4) void main() ... Não!

A função main devolve um int, excepto em compiladores especificos que aceitam, além do int, outras formas. Usando outra forma estás-te a limitar, sem necessidade, a esse compilador especifico.

int main(void) { /* ... */ return 0; }

PS: numa versao mais lá para a frente, podes tentar fazer a stack 'opaca', isto é, escondê-la num ficeiro próprio e limitar o acesso aos seus membros através de funções específicas. Deste modo, se mudares de array para lista ligada, não precisas de mudar o código que usa a stack (mais ou menos o que se faz com OOP).

Edited by pmg

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
polska

1) a tua funcao init_stack devolve um 'struct stack' (atraves do typedef STACK). Era melhor se ela nao devolvesse nada; a 'struct stack' completa sao mais de 400 bytes!

void init_stack(struct stack *stack) {
stack->top = -1;
}

2) A funcao 'push' podia (devia?) devolver um status indicando se a operação correu bem ou a razão de ter corrido mal

int push(struct stack *stack, int valor) {
stack->top++;
if (stack->top < MAX) {
	stack->nums[stack->top] = valor;
} else {
	stack->top--;
	return 1; /* SEM ESPACO */
}
return 0; /* OK */
}

3) a funcao 'pop' devia devolver o valor "popado" e um status para indicar se correu tudo bem ou se houve erro (tentativa de popar duma stack vazia)

4) void main() ... Não!

A função main devolve um int, excepto em compiladores especificos que aceitam, além do int, outras formas. Usando outra forma estás-te a limitar, sem necessidade, a esse compilador especifico.

int main(void) { /* ... */ return 0; }

PS: numa versao mais lá para a frente, podes tentar fazer a stack 'opaca', isto é, escondê-la num ficeiro próprio e limitar o acesso aos seus membros através de funções específicas. Deste modo, se mudares de array para lista ligada, não precisas de mudar o código que usa a stack (mais ou menos o que se faz com OOP).

Sinceramente não sei porque fiz aquela função com STACK, mas pronto ;D ....

Nas funções push e pop, inicialmente eu tinha código com essas verificações, mas foi código de pesquisa da net, então quando criei o meu código retirei, apenas para simplificar, mas sei disso :) .

Eu fiz uma stack com OOP, é isto que te referes ? :

#include <stdio.h>

#define MAX 5	  


class stack
{

private:
int nums[MAX];
int top;

public:
stack()
{
 //constructor
 top = -1;
}

void push( int n )
{
 //adiciona elemento
 top++;
 if( top < MAX )
  nums[top] = n;
 else
  top--;
}

void pop()
{
 //remove elemento
 //LIFO: last in - first out
 if( top != -1 )
 {
  nums[top] = NULL;
  top--;
 }
}

void show()
{
 if( top != -1 )
 {
  for( int i=0; i<=top; i++ )
  {
printf( "%d ", nums[i] );
  }
  printf( "\n\n" );
 }
}
};


int main()
{
   stack a;

   a.push(3);
   printf( "3 is Pushed\n" );
   a.push(10);
   printf( "10 is Pushed\n" );
   a.push(1);
   printf( "1 is Pushed\n" );
   a.push(15);
   printf( "15 is Pushed\n\n" );

   a.show();

   a.pop();
   printf( "last is Popped\n" );
   a.pop();
   printf( "last is Popped\n" );
   a.pop();
   printf( "last is Popped\n\n" );

   a.show();

   a.push(20);

   printf( "20 is Pushed\n" );
   a.push(40);
   printf( "40 is Pushed\n\n" );

   a.show();

   return 0;
}

Edited by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
pmg

Eu fiz uma stack com OOP, é isto que te referes ? :

Isto já não é C. Mas, se a minha interpretação do código está correcta, é isso (mais ou menos: respeitando as regras da linguagem C) a que me referia.


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
HappyHippyHippo

Stack opaca :

// stack.h

typedef struct Stack Stack;

Stack * stackCreate();
int stackdestroy(Stack ** stack);

int stackSize(Stack * stack, int * size);
int stackMax(Stack * stack, int * max);

int stackPush(Stack * stack, int value);
int stackPop(Stack * stack, int * value);
int stackClear(Stack * stack);

// stack.c

struct Stack {
   int list[100];
   int top;
};

Stack * stackCreate()
{
 // alocar memoria para a estrutura e inicializa-la
 // retornar a posição de memoria da stack criada
}

int stackdestroy(Stack ** stack)
{
 // libertação de memória previamente alocada
}

int stackSize(Stack * stack, int * size)
{
 // atribuir ao ponteiro "size" o número de elementos na stack
}

int stackMax(Stack * stack, int * max)
{
 // atribuir ao ponteiro "max" o máximo número de elementos que a stack pode conter
}

int stackPush(Stack * stack, int value)
{
 // adicionar o elemento value à stack
}

int stackPop(Stack * stack, int * value)
{
 // remover o elemento da stack e atribui-lo ao ponteiro "value"
}

int stackClear(Stack * stack)
{
 // remover todos os elementos da stack
}

desta forma, ao efetuares a inclusão do ficheiro .h, não sabes como a stack está implementada, logo será mais difícil criares código que "estrague" a implementação, porque deste modo a maneira de manipulares a stack é pelos métodos fornecidos programados por ti.

PS : podes alterar o código para que a função de criação possa aceitar um número que será o tamanho do array interno, usando depois malloc/free

Edited by HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
pikax

Eu fiz uma stack com OOP, é isto que te referes ? :

Penso que seria mais algo como aproveitar as vantagens de linguagens OOP como C++.


template<typename T>
 class stack
 {
 T m_objects[MAX];
   //....etc
 }

Pode-se fazer algo "similar"(Muito diferente :P ) em C, mas nao da' assim tanto jeito:


typedef struct stack
{
  void* m_objects[MAX];
  //...etc...
};


Por muito mais que que estude só aprendo uma coisa, que ainda tenho muita coisa para aprender.

A beleza de um código está em decompor problemas complexos em pequenos blocos simples.

"learn how to do it manually first, then use the wizzy tool to save time."

"Kill the baby, don't be afraid of starting all over again. Fail soon, learn fast."

Share this post


Link to post
Share on other sites
polska

Obrigado pelas respostas :)


Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites
Rui Carlos

DFS (Depth first search) e BFS (Breadth first search) são metodologias de pesquisa em grafos ou nas suas degenerações, árvores.

Dizer que uma é mais usada em stacks e outra em queues é esticar o conceito, tanto do método de pesquisa como dos objectos a serem pesquisados

Acho que o que ele queria dizer é que para fazeres uma travessia DFS de um grafo é comum usares uma stack com estrutura de dados auxiliar, e para fazeres uma travessia BFS de um grafo é comum usares uma queue como estrutura de dados auxiliar.

Share this post


Link to post
Share on other sites
polska

Acho que o que ele queria dizer é que para fazeres uma travessia DFS de um grafo é comum usares uma stack com estrutura de dados auxiliar, e para fazeres uma travessia BFS de um grafo é comum usares uma queue como estrutura de dados auxiliar.

Isto foi uma das pequenas coisas que li e o que quis dizer , neste caso refere-se ao BFS:

"In this case, it is desirable to try all the solutions with only k knights before moving on to those with k+1 knights. This is called breadth first search. The usual way to implement breadth first search is to use a queue of states"


Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.