Structures like this stack are called C++ containers or java collections, and in the literature they appear as ADT, abstract data structures. And you have to bring your program closer to that, on the abstract side. I’ll show you an example below.
Overall the container is a set S
possibly empty of records X
, and each record has a content that usually contains a key k
. And so you write all functions in terms of pointers to nodes and nodes in general have only one pointer to the record, which in turn contains the key.
In programs for study often the registration is the only key itself, as a letter or in your case a simple int
:
typedef int TYPEKEY;
You did not use a pointer but a key allocated INSIDE the record.
In the first version you were allocating the wrong size in push()
. Now it feels right. But understand that when inserting something into the stack or returning you should copy the data into the stack and when removing you should return a copy of them.
The problem is that the stack user can pass multiple times the same record, or pass a key to key
from a pointer that came from I don’t know where. If you put that in the pile a pop()
will later cancel your program. Or a restart()
or delete()
. There can be no hands loose by the program referring to areas within the stack. And vice versa.
Another point, and what you can see in an answer just above, is that access to the stack elements is done in terms of the key, not in terms of the node itself: the node structure is an internal thing to the stack.
In your case, you make a push()
of a TYPEKEY
, not of a ELEMENT
. And top()
returns a pointer to key
, not for a knot.
EXAMPLE
I changed your program a little and can compare the functions. First of all the structures
typedef int Key;
typedef struct aux_
{
Key key;
struct aux_* next;
} Element;
typedef struct
{
Element* top;
unsigned size;
} Stack;
I used the common convention to reserve names with the first letter capitalized for the typedef
and although it is not common, I kept in Ode the key and not the pointer to it, which is the most common. size
is a practical question: it is good to have an updated counter. it is normal to implement the stack using a vector dynamically allocated and there would also be the value of capacity, and everything would be much faster, using pointers as indexes and not Element*
The functions
int empty (Stack*);
int pop (Stack*);
int push (Key*,Stack*);
int size (Stack*);
Key* top (Stack*);
These are the names as used in C++, for example. But note that
- there is no
void
: always returns a status, negative for error, 0 for success, as is common in C.
push()
receives a pointer to Key
and not to Element
: Element
is something internal
top()
returns a pointer to the key, but a pointer to a copy from the registry, and it’s important to understand this: you don’t know what the user will do with the key, and so you have to return a copy, and the API user is responsible --- Owner --- by the pointer and must free the memory when no longer using the record. Several calls to top()
followed return pointers to copies of the same record and if the API user releases one will not mock the other. It is important to understand this. See in the example program.
The other functions
Stack* deleteStack (Stack*);
int restartStack (Stack*); // empties
int showStack (Stack*,const char*); // list all
Stack* startStack (unsigned); // return new
deleteStack()
returns NULL. Only to be used in an expression and invalidate the stack pointer itself in the program. See in the example.
restartStack()
it does not need but it can and has been written here in terms of pop()
to avoid repeating code
showStack()
is a test function. It does not exist on a normal stack and makes no sense: on a stack you only see one element at a time. I added a parameter, a const char*
, to show an optional title, because it is a "hand on the wheel" in the tests.
The sample program
The program creates a stack with a certain number of records, shows, deletes half of them and lists the rest. Then tests the restart()
, the delete()
and closes. I have not tested much but it can serve.
Here’s the code:
int main(void)
{
const int tamanho = 10;
Stack* nova = startStack(tamanho);
showStack(nova,"teste: pilha vazia ainda...");
printf("Vai inserir 1..10\n");
for( int i = 1; i<=tamanho; i+=1) push(&i,nova);
showStack(nova,"teste: pilha agora");
printf("Tenta remover metade dos elementos\n");
Key* p = NULL;
int n = nova->size/2;
for ( int i = 0; i<n; i+= 1)
{
printf("Vai remover '%d'\n", *(p = top(nova)));
free(p); // nao vai usar mais
pop(nova);
}; // for()
showStack(nova,"teste: pilha agora:");
printf("Usando restart() na pilha\n");
restartStack(nova);
showStack(nova,"teste: depois do restart()");
printf("Apagando a pilha\n");
nova = deleteStack(nova);
printf("Apagando a pilha\n");
showStack(nova,"vazia?");
showStack(nova,NULL);
return 0;
}
The output of the example
toninho@DSK-2009:~/projects/triangle$ ./build/stan
teste: pilha vazia ainda...
Pilha com 0 elementos
Vai inserir 1..10
teste: pilha agora
Pilha com 10 elementos
10 9 8 7 6 5 4 3 2 1
Tenta remover metade dos elementos
Vai remover '10'
Vai remover '9'
Vai remover '8'
Vai remover '7'
Vai remover '6'
teste: pilha agora:
Pilha com 5 elementos
5 4 3 2 1
Usando restart() na pilha
teste: depois do restart()
Pilha com 0 elementos
Apagando a pilha
Apagando a pilha
Pilha nao construida!
Pilha nao construida!
push()
int push (Key* k, Stack* s)
{
// cria um elemento e coloca na pilha.
// retorna o tamanho se ok, ou algo negativo
if ( s == NULL ) return -1;
if ( k == NULL ) return -2;
Element* el = (Element*) malloc(sizeof(Element));
if ( el == NULL ) return -3;
el->key = *k; // shallow copy here!!
el->next = s->top; // new at the TOP
s->top = el;
s->size += 1;
return s->size;
}
Just note that an element is created and the key is copied inside. So if the API user releases the pointer then it will not destroy the stack...
re-start()
int restartStack(Stack* s)
{
if ( s == NULL ) return -1;
while ( s->size > 0 ) pop(s);
return 0;
}
Note that it is simpler to write Restart() from pop(), besides being one less place to test :)
The whole program
#include <stdio.h>
#include <malloc.h>
typedef int Key;
typedef struct aux_
{
Key key;
struct aux_* next;
} Element;
typedef struct
{
Element* top;
unsigned size;
} Stack;
// classic
int empty (Stack*);
int pop (Stack*);
int push (Key*,Stack*);
int size (Stack*);
Key* top (Stack*);
// support
Stack* deleteStack (Stack*);
int restartStack (Stack*); // empties
int showStack (Stack*,const char*); // list all
Stack* startStack (unsigned); // return new
int main(void)
{
const int tamanho = 10;
Stack* nova = startStack(tamanho);
showStack(nova,"teste: pilha vazia ainda...");
printf("Vai inserir 1..10\n");
for( int i = 1; i<=tamanho; i+=1) push(&i,nova);
showStack(nova,"teste: pilha agora");
printf("Tenta remover metade dos elementos\n");
Key* p = NULL;
int n = nova->size/2;
for ( int i = 0; i<n; i+= 1)
{
printf("Vai remover '%d'\n", *(p = top(nova)));
free(p); // nao vai usar mais
pop(nova);
}; // for()
showStack(nova,"teste: pilha agora:");
printf("Usando restart() na pilha\n");
restartStack(nova);
showStack(nova,"teste: depois do restart()");
printf("Apagando a pilha\n");
nova = deleteStack(nova);
printf("Apagando a pilha\n");
showStack(nova,"vazia?");
showStack(nova,NULL);
return 0;
}
int empty (Stack* S)
{
return S->size == 0;
}
int pop (Stack* S)
{
if ( S == NULL ) return -1;
if ( empty(S) ) return -2;
Element* to_delete = S->top;
S->top = S->top->next;
S->size -= 1;
free(to_delete);
return S->size;
}
int push (Key* k, Stack* s)
{
// cria um elemento e coloca na pilha.
// retorna o tamanho se ok, ou algo negativo
if ( s == NULL ) return -1;
if ( k == NULL ) return -2;
Element* el = (Element*) malloc(sizeof(Element));
if ( el == NULL ) return -3;
el->key = *k; // shallow copy here!!
el->next = s->top; // new at the TOP
s->top = el;
s->size += 1;
return s->size;
}
int size(Stack* s)
{
if ( s == NULL ) return -1;
return s->size;
}
Key* top(Stack* s)
{
if ( s == NULL ) return NULL;
Key* k = (Key*) malloc(sizeof(k));
*k = s->top->key;
return k;
}
Stack* deleteStack(Stack* s)
{
if ( s == NULL ) return NULL;
while ( s->size > 0 ) pop(s);
return NULL;
}
int restartStack(Stack* s)
{
if ( s == NULL ) return -1;
while ( s->size > 0 ) pop(s);
return 0;
}
int showStack (Stack* s, const char* msg)
{
// prints stack nodes along with optional message
if ( s == NULL )
{
printf("Pilha nao construida!\n");
return -1;
};
if ( msg != NULL )
{
printf("%s\n", msg);
}
printf("Pilha com %d elementos\n", s->size);
Element* p = s->top;
while ( p != NULL )
{
printf( "%d ", p->key );
p = p->next;
}
printf("\n\n");
return s->size;
}
Stack* startStack (unsigned sz)
{
const unsigned dflt = 1000; // default size
Stack* stack = (Stack*) malloc(sizeof(Stack));
if ( stack == NULL ) return NULL;
stack->top = NULL;
stack->size = 0;
return stack;
}
Use more meaningful names. That’s sweet
struct aux
? Why didn’t you leave a version ofmain()
with a test?– arfneto
Oops. Sorry, I forgot to declare aux upon the struct. I edited. In case it would be a reference of the struct itself. I put an example of main as well.
– Staniack
You’ve allocated memory in the stack and are trying to clear it.
– sgtcortez
I’m sorry, I don’t understand your answer
– Staniack
memory was allocated normally, in heap by a previous push... it was wrong sizeof() before, but the author corrected
– arfneto
is not the compiler that gets "looping". It is your program that cancels. The compiler only generates the program
– arfneto