Stack implementation of Linked List

A

arnuld

Any advice, implemented only one operation yet. Will implement others if
this one is okay:


/* A Stack implementation of a singly linked list with 4 operations: Pop, Push, Top and Print elements in the list.
*
* VERISON 0.0
*
*/

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

enum { STACK_ARR_SIZE = 10 };

struct my_stack
{
char arrc[STACK_ARR_SIZE];
struct my_stack* next;
};

struct stack_list
{
struct my_stack* head;
};


struct stack_list* push( struct stack_list*, const char* );
struct stack_list* pop( struct stack_list* );
struct stack_list* top( struct stack_list* );

struct stack_list* stack_new( void );
void stack_print( const struct stack_list* );
void stack_print_element( const struct my_stack* );
void stack_free( struct my_stack* );


int main( void )
{
struct stack_list* ms = NULL;
ms = stack_new();

stack_print(ms);

push(ms, "comp");
push(ms, "(dot)");
push(ms, "lang");
push(ms, "(dot)");
push(ms, "c");

stack_print(ms);



return 0;
}


struct stack_list* push(struct stack_list* s, const char* c )
{
struct my_stack* p = malloc( 1 * sizeof *p );
struct my_stack* n = NULL;

if( NULL == p )
{
fprintf(stderr, "malloc() failed\n");
return s;
}

strcpy(p->arrc, c);
p->next = NULL;

if( NULL == s )
{
fprintf(stderr, "Stack not initialized ?\n");
return s;
}
else if( NULL == s->head )
{
/* printf("Stack is Empty, adding first element\n"); */
s->head = p;
return s;
}
else
{
/* printf("Stack not Empty, adding in front of first element\n"); */
n = s->head; /* save current head */
s->head = p; /* push new element onto the head */
s->head->next = n; /* attach the earlier saved head to the next of new element */
}

return s;
}



/* ---------- small helper functions -------------------- */
struct stack_list* stack_new( void )
{
struct stack_list* p = malloc( 1 * sizeof *p );

if( NULL == p )
{
fprintf(stderr, "malloc() in Stack Initialization failed\n");
}

p->head = NULL;

return p;
}


void stack_print( const struct stack_list* s )
{
struct my_stack* p = NULL;

if( NULL == s )
{
printf("Can not print an Empty Stack\n");
}
else
{
for( p = s->head; p; p = p->next ) stack_print_element(p);
}
}


void stack_print_element(const struct my_stack* s)
{
printf("arrc = %s\n", s->arrc);
}



==================== OUTPUT =============================
[arnuld@dune programs]$ gcc -std=c99 -pedantic -Wall -Wextra stack.c
[arnuld@dune programs]$ ./a.out
arrc = c
arrc = (dot)
arrc = lang
arrc = (dot)
arrc = comp
[arnuld@dune programs]$
 
K

Kenny McCormack

Any advice, implemented only one operation yet. Will implement others if
this one is okay:


/* A Stack implementation of a singly linked list with 4 operations:
Pop, Push, Top and Print elements in the list.
Click to expand...

Keep in mind that you are not allowed to use "the S word" in this newsgroup.

Any minute now, some helpful reg will be along to tell you that the S
word need not exist, doesn't exist, isn't specified in the C standards
documents, blah, blah, blah, etc, etc, etc.
 
M

mark.bluemel

On 12 May said:
struct stack_list* push(struct stack_list* s, const char* c )
{
  struct my_stack* p = malloc( 1 * sizeof *p ); /* This variable isn't needed
  struct my_stack* n = NULL; */

  if( NULL == p )
    {
      fprintf(stderr, "malloc() failed\n");
      return s;
    }

  strcpy(p->arrc, c);
  p->next = NULL;

  if( NULL == s )
    {
      fprintf(stderr, "Stack not initialized ?\n");
      return s;
    }
Click to expand...

/* This is unnecessary...
  else if( NULL == s->head )
    {
      /*      printf("Stack is Empty, adding first element\n"); */
      s->head = p;
      return s;
    } */
  else
    {
      /*      printf("Stack not Empty, adding in front of first element\n"); */
      n = s->head;  /* save current head */
      s->head = p;  /* push new element onto the head */
      s->head->next = n; /* attach the earlier saved head to the next of new element */
Click to expand...

Why not use this (save a variable and an assignment) :-

p->next = s->head;
s->head = p;
 
K

Kenny McCormack

No one here has ever said that there's no such thing as a "stack", given
that we all know that a "stack" is merely another name for a LIFO queue.

What you are confused about is the use of the term when referring to where
the compiler and the CPU place things such as automatic variables, function
parameters, and call/return information, which may or may not be a "stack".

But, then again, you probably already knew that.
Click to expand...

I can certainly point you to articles where the merest mention of the S
word has caused one or more of our dear regs to go simply non-linear (at
the merest mention...)

Yet, I do approve of your post. Thanks for posting.
 
G

gw7rib

/* A Stack implementation of a singly linked list with 4 operations: Pop, Push, Top and Print elements in the list.
Click to expand...

The code looks OK at a quick glance. It's slightly odd to include the
"1 *" in lines such as
  struct my_stack* p = malloc( 1 * sizeof *p );
Click to expand...

but if you like it then feel free to stick with it.

The only real comment is that I would have called your program a
linked list implementation of a stack. The structure is a linked list
really, and you are using it to act rather like a stack, so you are
implementing (what looks like) a stack using a linked list.
 
J

jfbode1029

Keep in mind that you are not allowed to use "the S word" in this newsgroup.

Any minute now, some helpful reg will be along to tell you that the S
word need not exist, doesn't exist, isn't specified in the C standards
documents, blah, blah, blah, etc, etc, etc.
Click to expand...

Jesus H. Tapdancing Christ on a giraffe, this is getting tiresome even
by Kenny standards.

Discussing C code that implements a stack data structure != discussing
machine architecture. You know this. Stop being a dick for the sake
of being a dick.
 
K

Keith Thompson

On May 12, 8:05 am, (e-mail address removed) (Kenny McCormack)
wrote: [more of the same]
Jesus H. Tapdancing Christ on a giraffe, this is getting tiresome even
by Kenny standards.

Discussing C code that implements a stack data structure != discussing
machine architecture. You know this. Stop being a dick for the sake
of being a dick.
Click to expand...

He won't. I recommend a killfile.

If I'd wanted to read what he wrote, I would have done so; why quote
it and inflict it on the rest of us?
 
K

Kenny McCormack

Jesus H. Tapdancing Christ on a giraffe, this is getting tiresome even
by Kenny standards.

Discussing C code that implements a stack data structure != discussing
machine architecture. You know this. Stop being a dick for the sake
of being a dick.
Click to expand...

But surely even you can see that there is no mention of the S word in
the C standards documents, so, therefore, and without possible fear of
contradiction, we all know that it is off topic in this newsgroup and
cannot be discussed here. Just as clearly there is (as far as I know)
no mention in any of the C standards documents of beach balls, and
therefore (again, with no fear of contradiction), I can state that
discussion of beach balls would, quite correctly, get beaned here as
being OT.

However, the point (and yes, we are all aware of this) is that for some
reason, discussion of beach balls doesn't send the regs into fits of
apoplexy (like the merest mention of the S word can and does). I guess
they are more OK with things on the beach...

Hope this clears things up for you...
 
P

Phil Carmody

arnuld said:
Any advice, implemented only one operation yet. Will implement others if
this one is okay:


/* A Stack implementation of a singly linked list with 4 operations: Pop, Push, Top and Print elements in the list.
*
* VERISON 0.0
*
*/

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

enum { STACK_ARR_SIZE = 10 };

struct my_stack
{
char arrc[STACK_ARR_SIZE];
struct my_stack* next;
};

struct stack_list
{
struct my_stack* head;
};


struct stack_list* push( struct stack_list*, const char* );
struct stack_list* pop( struct stack_list* );
struct stack_list* top( struct stack_list* );

struct stack_list* stack_new( void );
void stack_print( const struct stack_list* );
void stack_print_element( const struct my_stack* );
void stack_free( struct my_stack* );


int main( void )
{
struct stack_list* ms = NULL;
ms = stack_new();

stack_print(ms);

push(ms, "comp");
push(ms, "(dot)");
push(ms, "lang");
push(ms, "(dot)");
push(ms, "c");

stack_print(ms);



return 0;
}


struct stack_list* push(struct stack_list* s, const char* c )
Click to expand...

You're merging the code which manages the payloads with the
code that manages the linked list. That's usually a bad design,
as it hinders code reuse.
{
struct my_stack* p = malloc( 1 * sizeof *p );
struct my_stack* n = NULL;
Why?

if( NULL == p )
{
fprintf(stderr, "malloc() failed\n");
return s;
}

strcpy(p->arrc, c);
Click to expand...

Buffer overrun.
p->next = NULL;
Why?

if( NULL == s )
{
fprintf(stderr, "Stack not initialized ?\n");
return s;
Leak.

}
else
Click to expand...

At this point, consider p->next = s->head; ...

if( NULL == s->head )
{
Click to expand...

.... because here it is the same as p->next = NULL, what you had before ...
/* printf("Stack is Empty, adding first element\n"); */
s->head = p;
return s;
}
else
{
Click to expand...

.... and here it would be the same as p->next = s->head; ...
/* printf("Stack not Empty, adding in front of first element\n"); */
n = s->head; /* save current head */
s->head = p; /* push new element onto the head */
s->head->next = n; /* attach the earlier saved head to the next of new element */
Click to expand...

.... which is what 2 of these 3 lines do.
}

return s;
Click to expand...

You're never using that return value - what's it for?
}
Click to expand...

Rest not examined, as I think you need to go back to the drawing
board generally.

Phil
 
P

Phil Carmody

Piggybacking, for obvious reasons.


Wow. Never before have I seen such an example of either a complete
inability to understand what the regulars are talking about when
then mention the *fact* that one may not assume that there's such
a thing as a stack on a system, or a deliberate attempt to spread
completely garbage misinformation. Kenny - you truly are a fuckwit.
OP - ignore everything Kenny says. Killfile him if you have the
opportunity, he'll never have anything of worth to say.
No one here has ever said that there's no such thing as a "stack",
given that we all know that a "stack" is merely another name for a
LIFO queue.
Click to expand...

Exactly. According to the standard, there's no function called qux()
but it's perfectly legal for the programmer to implement one with
that name himself (or uses a 3rd party library). Likewise, there's
not necessarily any concept of a stack until the programmer implements
one (or uses a third party library).
No one here has ever said that there's no such thing as a "stack",
What you are confused about is the use of the term when referring to
where the compiler and the CPU place things such as automatic
variables, function parameters, and call/return information, which may
or may not be a "stack".

But, then again, you probably already knew that.
Click to expand...

Evaluating the faculties of a fuckwit is sometimes pretty hard.

Phil
 
P

Phil Carmody

Eric Sosman said:
[... elided, with prejudice ...]
Click to expand...
You know this. Stop being a dick for the sake
of being a dick.
Click to expand...

He can't. He follows Polonius' advice.
Click to expand...

"Give thy thoughts no tongue"?

I wish he did follow that advice. However, I'm not sure the processes
behind his newsgroup droppings can be called 'thoughts'.

Phil
 
K

Kenny McCormack

Kenneth Brody said:
<mode type="CLC reg">
But the C Standard makes no mention of "Polonius", "thoughts", or "tongue",
so this must be OT.
</mode>

:)
Click to expand...

Hey, I learned from the best!
I'm just doing my best to be a good CLC citizen, to emulate the behavior
of the leaders.
 
A

arnuld

You're merging the code which manages the payloads with the
code that manages the linked list. That's usually a bad design,
as it hinders code reuse.
Click to expand...


I don't get what you said. I am trying to create a LIFO and this is the
best what I have thought.



Why?
Click to expand...

"n" is later used to save the current head pointer.


Buffer overrun.
Click to expand...


It will overrun if the user gives the input larger than what I have have
asked, which is user's intention. He can also do a "rm -v stack.c" if this
is his intention. I can't do anything about it.



Why?
Click to expand...


Because there is no next element, yet.

Leak.
Click to expand...

???





You're never using that return value - what's it for?
Click to expand...

For later use, as I have written only 30% of the code. There is no
function that returns void, I have the habit of making functions
always return something, except those print functions.


Rest not examined, as I think you need to go back to the drawing
board generally.
Click to expand...


You have not provided any reason on why things are bad, how am I suppose
to rewrite it without knowing Why ?
 
A

arnuld

On Tue, 12 May 2009 17:37:37 +0500, arnuld wrote:


Okay, here is the 2nd and complete version with pop() and top()
implemented, see if I can have some improvements:


/* A Stack implementation of a singly linked list with 4 operations: Pop, Push, Top and Print elements in the list.
*
* VERISON 0.1
*
*/

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

enum { STACK_ARR_SIZE = 10 };

struct my_stack
{
char arrc[STACK_ARR_SIZE];
struct my_stack* next;
};

struct stack_list
{
struct my_stack* head;
};


struct stack_list* push( struct stack_list*, const char* );
struct stack_list* pop( struct stack_list* );
struct my_stack* top( struct stack_list* );

struct stack_list* stack_new( void );
void stack_print( const struct stack_list* );
void stack_print_element( const struct my_stack* );
struct stack_list* stack_free( struct stack_list* );


int main( void )
{
struct my_stack* p = NULL;
struct stack_list* ms = NULL;
ms = stack_new();

stack_print(ms);

push(ms, "comp");
push(ms, "(dot)");
push(ms, "lang");
push(ms, "(dot)");
push(ms, "c");

stack_print(ms);

pop(ms);
p = top(ms);
stack_print_element(p);
stack_print(ms);

stack_free(ms);
free(ms);
ms = NULL;

return 0;
}


struct stack_list* push(struct stack_list* s, const char* c )
{
struct my_stack* p = malloc( 1 * sizeof *p );

if( NULL == p )
{
fprintf(stderr, "malloc() failed\n");
return s;
}

strcpy(p->arrc, c);
p->next = NULL;

if( NULL == s )
{
fprintf(stderr, "Stack not initialized ?\n");
return s;
}
else if( NULL == s->head )
{
/* printf("Stack is Empty, adding first element\n"); */
s->head = p;
return s;
}
else
{
/* printf("Stack not Empty, adding in front of first element\n"); */
p->next = s->head;
s->head = p; /* push new element onto the head */
}

return s;
}


struct stack_list* pop( struct stack_list* s )
{
struct my_stack* p = NULL;

if( NULL == s )
{
printf("There is no stack list ?\n");
}
else if( NULL == s->head )
{
printf("There is no element on the stack\n");
}
else
{
p = s->head;
s->head = s->head->next;
free(p);
}

return s;
}


struct my_stack* top( struct stack_list* s)
{
if( NULL == s )
{
printf("There is no stack list ?\n");
}
else if( NULL == s->head )
{
printf("There is no element on the stack\n");
}


return s->head;
}



/* ---------- small helper functions -------------------- */
struct stack_list* stack_free( struct stack_list* s )
{
if( NULL == s )
{
printf("Can't free a NULL stack list\n");
}

while( s->head ) pop(s);

return s;
}


struct stack_list* stack_new( void )
{
struct stack_list* p = malloc( 1 * sizeof *p );

if( NULL == p )
{
fprintf(stderr, "malloc() in Stack Initialization failed\n");
}

p->head = NULL;

return p;
}


void stack_print( const struct stack_list* s )
{
struct my_stack* p = NULL;

if( NULL == s )
{
printf("Can not print an Empty Stack\n");
}
else
{
for( p = s->head; p; p = p->next ) stack_print_element(p);
}

printf("-------------------------- \n");
}


void stack_print_element(const struct my_stack* s)
{
printf("arrc = %s\n", s->arrc);
}
 
J

James Kuyper

arnuld said:
"n" is later used to save the current head pointer.
Click to expand...

Which means there's no need to set it to anything right now.
It will overrun if the user gives the input larger than what I have have
asked, which is user's intention. He can also do a "rm -v stack.c" if this
is his intention. I can't do anything about it.
Click to expand...

You can't do anything about the rm command, but nothing is forcing you
to copy over more bytes than the destination can hold. You can't prevent
misuse of your code. You can, however, make it fail gracefully, with
defined behavior, when misused.
Because there is no next element, yet.
Click to expand...

But you're not going to make any use of p->next unless and until it's
been set to point at what's currently s->head. Therefore, setting it to
NULL is a waste of time.
???
Click to expand...

At this point, you've allocated a block of memory, pointed at by 'p'.
You haven't free()d that block, and when you return from this function,
p will disappear. You have no copies of that pointer value anywhere
else, so it will be impossible to either use or free() that memory at
any later time.
 
K

Kenny McCormack

And I jumped when I saw around 10 replies but nothing technical here :(
Click to expand...

CLC is not a technical newsgroup. Hasn't been for decades.

But stick around - it has other, er, attractions, to enjoy
 
R

Richard Bos

Jesus H. Tapdancing Christ on a giraffe, this is getting tiresome even
by Kenny standards.

Discussing C code that implements a stack data structure !=3D discussing
machine architecture. You know this. Stop being a dick for the sake
of being a dick.
Click to expand...

What, and eliminate his entire raison d'être? If he did that, the
implosion would leave a greater void than the Tunguska event.

Richard
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Stack using doubly linked list 1
Array implementation of Stack 80
LIFO in C 11
dequeue() not working 9
A Queue implementation of doubly linked list in C 44
Stack using Array 16
pointer to pointer 7
linked list 26

Members online

Total: 33 (members: 3, guests: 30)
Robots: 206

Forum statistics

Threads
473,766
Messages
2,569,569
Members
45,042
Latest member
icassiem

Latest Threads

Top