Stack, bem implementado?

[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 😄

Agradeço desde já 🙂

Edited July 10, 2012 at 02:17 AM by polska

[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 🙂

[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 😄 , de resto esta tudo bem?

[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

[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 July 10, 2012 at 09:29 AM by pmg

[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 July 10, 2012 at 09:38 AM by polska

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

[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 July 10, 2012 at 09:57 AM by HappyHippyHippo

[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 😛 ) em C, mas nao da' assim tanto jeito:

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

[polska]

Obrigado pelas respostas 🙂

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

[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"