Stack implementation of Linked List
arnuld
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]$
--
www.lispmachine.wordpress.com
my email is @ the above blog.
Kenny McCormack
arnuld <sun...@invalid.address> wrote:
>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.
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.
mark.b...@googlemail.com
...
>
> 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;
> }
/* 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 */
Why not use this (save a variable and an assignment) :-
p->next = s->head;
Kenneth Brody
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.
--
Kenneth Brody
Kenny McCormack
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.
Richard
Wow. Way to reinforce Kenny's point about pedantic, useless, boring side
tracking and point scoring.
--
"Avoid hyperbole at all costs, its the most destructive argument on
the planet" - Mark McIntyre in comp.lang.c
gw7...@aol.com
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 );
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.
jfbod...@gmail.com
wrote:
> In article <pan.2009.05.12.12.37.32.310...@invalid.address>,
>
> arnuld <sunr...@invalid.address> wrote:
> >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.
>
> 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.
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.
Keith Thompson
> On May 12, 8:05�am, gaze...@shell.xmission.com (Kenny McCormack)
> wrote:
> 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.
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?
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Kenny McCormack
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...
Eric Sosman
> You know this. Stop being a dick for the sake
> of being a dick.
He can't. He follows Polonius' advice.
--
Eric Sosman
eso...@ieee-dot-org.invalid
luserXtrog
> jfbode1...@gmail.com wrote:
> > On May 12, 8:05 am, gaze...@shell.xmission.com (Kenny McCormack)
> > wrote:
> >> [... elided, with prejudice ...]
>
> > You know this. Stop being a dick for the sake
>
> > of being a dick.
>
> He can't. He follows Polonius' advice.
>
Could perhaps be constrewn to violate:
Give thy thoughts no tongue,
Nor any unproportioned thought his act.
--
elextee
Phil Carmody
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);
Buffer overrun.
> p->next = NULL;
Why?
> if( NULL == s )
> {
> fprintf(stderr, "Stack not initialized ?\n");
> return s;
Leak.
> }
> else
At this point, consider p->next = s->head; ...
if( NULL == s->head )
> {
... 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
> {
... 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 */
... which is what 2 of these 3 lines do.
> }
>
> return s;
You're never using that return value - what's it for?
> }
Rest not examined, as I think you need to go back to the drawing
board generally.
Phil
--
Marijuana is indeed a dangerous drug.
It causes governments to wage war against their own people.
-- Dave Seaman (sci.math, 19 Mar 2009)
Phil Carmody
Kenneth Brody <kenb...@spamcop.net> writes:
> Kenny McCormack wrote:
>> In article <pan.2009.05.12....@invalid.address>,
>> arnuld <sun...@invalid.address> wrote:
>>> 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.
>>
>> 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.
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.
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.
Evaluating the faculties of a fuckwit is sometimes pretty hard.
Phil Carmody
> jfbod...@gmail.com wrote:
>> On May 12, 8:05 am, gaze...@shell.xmission.com (Kenny McCormack)
>> wrote:
>>> [... elided, with prejudice ...]
>> You know this. Stop being a dick for the sake
>> of being a dick.
>
> He can't. He follows Polonius' advice.
"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'.
arnuld
And I jumped when I saw around 10 replies but nothing technical here :(
Kenneth Brody
>>Discussing C code that implements a stack data structure != discussing
>>of being a dick.
> 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.
As I'm sure you are aware, there is a difference between discussing, or
assuming that there exists, a hardware stack, where things such as automatic
variables and call/return information may be stored, and discussing a FIFO
queue which one is implementing in ISO C.
> 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, discussing implementing beach balls in ISO C would be on topic.
> 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...
--
Kenneth Brody
Kenneth Brody
> Eric Sosman <eso...@ieee-dot-org.invalid> writes:
>> jfbod...@gmail.com wrote:
>>> On May 12, 8:05 am, gaze...@shell.xmission.com (Kenny McCormack)
>>> wrote:
>>>> [... elided, with prejudice ...]
>>> You know this. Stop being a dick for the sake
>>> of being a dick.
>> He can't. He follows Polonius' advice.
>
> "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'.
<mode type="Kenny">
But the C Standard makes no mention of "Polonius", "thoughts", or "tongue",
so this must be OT.
</mode>
:-)
--
Kenneth Brody
Kenny McCormack
Kenneth Brody <kenb...@spamcop.net> wrote:
...
><mode type="CLC reg">
>But the C Standard makes no mention of "Polonius", "thoughts", or "tongue",
>so this must be OT.
></mode>
>
>:-)
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.
arnuld
>> arnuld <sun...@invalid.address> wrote:
>> struct stack_list* push(struct stack_list* s, const char* c )
> 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.
I don't get what you said. I am trying to create a LIFO and this is the
best what I have thought.
>> struct my_stack* p = malloc( 1 * sizeof *p );
>> struct my_stack* n = NULL;
> Why?
"n" is later used to save the current head pointer.
>> if( NULL == p )
>> {
>> fprintf(stderr, "malloc() failed\n");
>> return s;
>> }
>>
>> strcpy(p->arrc, c);
> Buffer overrun.
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.
>> p->next = NULL;
>
> Why?
Because there is no next element, yet.
>> if( NULL == s )
>> {
>> fprintf(stderr, "Stack not initialized ?\n");
>> return s;
>
> Leak.
???
> You're never using that return value - what's it for?
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.
You have not provided any reason on why things are bad, how am I suppose
to rewrite it without knowing Why ?
arnuld
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);
}
James Kuyper
>> On Wed, 13 May 2009 08:55:02 +0300, Phil Carmody wrote:
>>> arnuld <sun...@invalid.address> wrote:
>>> struct my_stack* p = malloc( 1 * sizeof *p );
>>> struct my_stack* n = NULL;
>
>> Why?
>
> "n" is later used to save the current head pointer.
Which means there's no need to set it to anything right now.
>>> if( NULL == p )
>>> {
>>> fprintf(stderr, "malloc() failed\n");
>>> return s;
>>> }
>>>
>>> strcpy(p->arrc, c);
>
>> Buffer overrun.
>
>
> 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.
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.
>>> p->next = NULL;
>> Why?
>
>
> Because there is no next element, yet.
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.
>>> if( NULL == s )
>>> {
>>> fprintf(stderr, "Stack not initialized ?\n");
>>> return s;
>> Leak.
>
> ???
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.
Kenny McCormack
arnuld <sun...@invalid.address> wrote:
>
>And I jumped when I saw around 10 replies but nothing technical here :(
CLC is not a technical newsgroup. Hasn't been for decades.
But stick around - it has other, er, attractions, to enjoy
Richard Bos
> On May 12, 8:05=A0am, gaze...@shell.xmission.com (Kenny McCormack)
> wrote:
> > 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.
>
> 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.
What, and eliminate his entire raison d'�tre? If he did that, the
implosion would leave a greater void than the Tunguska event.
Richard
Kenny McCormack
Quite possibly so. Still, I doubt it would compare to the seismic
effects we'd see if Kiki actually let something go.
Barry Schwarz
stack_new can fail. Once you fix the undefined behavior there, either
that function needs to abort the program or you need to check for the
failure here. Checking in each of the operation functions seems
inefficient.
>
> 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 )
You always return the same value of s that you were provided. (What s
points to may change but that does not affect the value of s itself.)
Seems like a waste.
> {
> 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;
You now have a memory leak. p points to allocated memory and p will
disappear as soon as this function returns. You will never be able to
free the memory p points to.
> }
> 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 */
Since s->head is guranteed to equal p, this would be easier as
p->next = n;
> }
>
> 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");
At this point you know p is NULL. But you allow the code to fall
through ...
> }
>
> p->head = NULL;
... and here you dereference the null pointer!
>
> return p;
>
> }
>
arnuld
> ... SNIP...
> stack_new can fail. Once you fix the undefined behavior there, either
> that function needs to abort the program or you need to check for the
> failure here. Checking in each of the operation functions seems
> inefficient.
I check in each operation because those operations can be run
independent of of stack_new(), you just have to provide a pointer to
stack_list type and that can be done without using stack_new() (e.g.
like using a NULL pointer). It won't help in such a small program but
in bigger programs which have 16 source files and around 10 headers
where function calls are made at many places, I will never have any
idea when something will go NULL. I work in a compnay and that
Segfaults happen most of the time when whole team of 5 people sit
together to write code for one application. With my check in each
operation, I was ablw to know the reasons of Segfaults at many time,
the add/remove (push/pop) operations were gettign NULL arguments. So
these checks are not for this small program but for programs written
by teams in a corporate. I have just made a habit of it.
How is this new fixed code:
/* A Stack implementation of a singly linked list with 4 operations:
Pop, Push, Top and Print elements in the list.
*
* VERISON 0.3
*
*/
#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 my_stack* make_null( struct stack_list* );
struct my_stack* is_empty( 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);
printf("---------------------------\n");
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");
free(p);
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");
return NULL;
}
else if( NULL == s->head )
{
printf("There is no element on the stack\n");
}
return s->head;
}
/* Make a Stack empty */
struct my_stack* make_null( struct stack_list* s )
{
if( NULL == s )
{
printf("Can not make NULL when there is no Stack List\n");
return NULL;
}
else if( NULL == s->head )
{
printf("Stack is already Empty\n");
}
else
{
stack_free(s);
}
return s->head;
}
struct my_stack* is_empty( struct stack_list* s )
{
if( NULL == s )
{
printf("There is no Stack\n");
return NULL;
}
else if( NULL == s->head )
{
printf("Stack is Empty\n");
}
else
{
printf("Stack is not Empty\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");
exit( EXIT FAILURE ); /* There is no point in going beyond this
point */
}
p->head = NULL;
return p;
}
void stack_print( const struct stack_list* s )
{
struct my_stack* p = NULL;
if( NULL == s )
{
arnuld
version:
/* A Stack implementation of a singly linked list with 4 operations:
Pop, Push, Top and Print elements in the list.
*
* VERISON 0.4
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
enum { STACK_ARR_SIZE = 10 };
struct my_stack
{
char arrc[STACK_ARR_SIZE]; /* Thar array must not have more thab
(STACK_ARR_SIZE - 1) elements */
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 my_stack* make_null( struct stack_list* );
struct my_stack* is_empty( 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, "comppppppppppppppppp");
push(ms, "(dot)");
push(ms, "lang");
push(ms, "(dot)");
push(ms, "c");
stack_print(ms);
pop(ms);
p = top(ms);
stack_print_element(p);
printf("---------------------------\n");
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;
}
/* If use gave us more characters than what we want, then its his
problem */
if( strlen(c) < STACK_ARR_SIZE ) strcpy(p->arrc, c);
p->next = NULL;
if( NULL == s )
{
fprintf(stderr, "Stack not initialized ?\n");
free(p);
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");
return NULL;
}
else if( NULL == s->head )
{
printf("There is no element on the stack\n");
}
return s->head;
}
/* Make a Stack empty */
struct my_stack* make_null( struct stack_list* s )
{
if( NULL == s )
{
printf("Can not make NULL when there is no Stack List\n");
return NULL;
}
else if( NULL == s->head )
{
printf("Stack is already Empty\n");
}
else
{
stack_free(s);
}
return s->head;
}
struct my_stack* is_empty( struct stack_list* s )
{
if( NULL == s )
{
printf("There is no Stack\n");
return NULL;
}
else if( NULL == s->head )
{
printf("Stack is Empty\n");
}
else
{
printf("Stack is not Empty\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");
exit( EXIT_FAILURE ); /* There is no point in going beyond this
point */
}
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);
}
================== OUTPUT =================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra stack.c
[arnuld@dune programs]$ ./a.out
--------------------------
arrc = c
arrc = (dot)
arrc = lang
arrc = (dot)
arrc =
--------------------------
arrc = (dot)
---------------------------
arrc = (dot)
arrc = lang
arrc = (dot)
arrc =
--------------------------
[arnuld@dune programs]$
Barry Schwarz
> Array element of Stack remained to be fixed, so here is the fixed
> version:
snip
> 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;
I expect a user would like his calling function to know if this
function succeeded or not.
> }
>
> /* If use gave us more characters than what we want, then its his
> problem */
> if( strlen(c) < STACK_ARR_SIZE ) strcpy(p->arrc, c);
> p->next = NULL;
>
> if( NULL == s )
If you do this test at the top of the function, you can eliminate the
free since you will nhjot yet have called malloc.
> {
> fprintf(stderr, "Stack not initialized ?\n");
> free(p);
> 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;
>
> }
snip
> 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;
s-head = p->next; /*it just seems cleaner*/
> free(p);
> }
>
> return s;
>
> }
snip
Ben Bacarisse
> Array element of Stack remained to be fixed, so here is the fixed
> version:
<snip>
> struct my_stack
> {
> char arrc[STACK_ARR_SIZE]; /* Thar array must not have more thab
> (STACK_ARR_SIZE - 1) elements */
> struct my_stack* next;
> };
<snip>
In list insert function:
> /* If use gave us more characters than what we want, then its his
> problem */
> if( strlen(c) < STACK_ARR_SIZE ) strcpy(p->arrc, c);
This is an odd way to fix the problem. You leave lurking undefined
behaviour this way -- the user of this code can't tell if it worked or
not and examining the string they thought they stored in the array will
produce UB. It would be better to one of these:
(a) signal to the use that this failed;
(b) set the string to something they can test like p->arrc[0] = 0;
(c) copy no more characters than will fit rather than no writing
anything.
--
Ben.