Array implementation of Stack

[arnuld]

WANTED: To write an array implementation of Stack.
WHAT I GOT: It works fine.

I think program is still little too complex. Any ideas to improve ?



/* Array implementation of Stack - Aho, Hopcraft and Ullman, page 68-70
* section 2.3. We will add element at the bottom and we will grow the
* stack to top. top_index will keep track of index where element was
* added as latest. We will use top_index to push/pop elements.
*
* VERSION 0.0.
*
*/

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

enum {
SIZE_NAME = 10, SIZE_ARR = 3,
VAL_SUCC = 0, VAL_ERR = 1
};

struct elm
{
int num;
char name[SIZE_NAME+1];
};


struct elm_stack
{
int top_index;
struct elm* arr[SIZE_ARR];
};


int push(struct elm_stack* , struct elm* );
void pop(struct elm_stack* );
struct elm_stack* stack_init(void);
void print_stack(struct elm_stack* );
struct elm* get_element(const char* c, int n);


int main(void)
{
struct elm_stack* s = stack_init();

struct elm* e0 = get_element("comp", 2);
struct elm* e1 = get_element("lang", 1);
struct elm* e2 = get_element("c", 0);

int ret_elem = push(s, e0);
if(VAL_ERR == ret_elem)
{
printf("IN: %s @%d: Memory Full\n", __FILE__, __LINE__);
free(e0);
}

ret_elem = push(s, e1);
if(VAL_ERR == ret_elem)
{
printf("IN: %s @%d: Memory Full\n", __FILE__, __LINE__);
free(e1);
}

ret_elem = push(s, e2);
if(VAL_ERR == ret_elem)
{
printf("IN: %s @%d: Memory Full\n", __FILE__, __LINE__);
free(e2);
}

print_stack(s);


printf("-----------------------------------------\n\n");
pop(s);
print_stack(s);
printf("-----------------------------------------\n\n");

pop(s);
print_stack(s);
printf("-----------------------------------------\n\n");

pop(s);
print_stack(s);

return EXIT_SUCCESS;
}



int push(struct elm_stack* s, struct elm* e)
{
int ret;

if(NULL == s || NULL == e)
{
printf("IN:%s @%d Invalid Args!\n", __FILE__, __LINE__);
ret = VAL_ERR;
}
else if(s->top_index == 0)
{
ret = VAL_ERR;
}
else
{
--(s->top_index);
/* printf("s->top_index = %d\n", s->top_index); */
s->arr[s->top_index] = e;
/* printf("%s = %d\n", e->name, e->num); */
ret = VAL_SUCC;
}

return ret;
}


void pop(struct elm_stack* s)
{
if(NULL == s)
{
printf("IN:%s @%d: Invalid Args!\n", __FILE__, __LINE__);
}
else if(SIZE_ARR <= s->top_index)
{
printf("Nothing to pop()\n");
}
else
{
struct elm* e = s->arr[s->top_index];
free(e);
++(s->top_index);
}
}



struct elm_stack* stack_init(void)
{
int idx;
struct elm_stack* p = malloc(1 * sizeof *p);
if(NULL == p)
{
printf("IN: %s @%d: Out of Memory!\n", __FILE__, __LINE__);
}
else
{
p->top_index = SIZE_ARR;
for(idx = 0; idx < SIZE_ARR; ++idx) p->arr[idx] = NULL;
}

return p;
}


struct elm* get_element(const char* c, int n)
{
struct elm* p = malloc(1 * sizeof *p);

if(NULL == p)
{
printf("IN:%s @%d: Out of Memory!\n", __FILE__, __LINE__);
}
else if(SIZE_NAME < strlen(c))
{
printf("IN: %s @ %d: ", __FILE__, __LINE__);
printf("Name too big, Not adding element\n");
free(p);
p = NULL;
}
else
{
p->num = n;
strcpy(p->name,c);
}

return p;
}


void print_stack(struct elm_stack* s)
{
if(NULL == s)
{
printf("IN:%s @%d: Invalid Args!\n", __FILE__, __LINE__);
}
else
{
int idx = SIZE_ARR - 1;
struct elm* e;
/*printf("idx %d, top_index = %d\n", idx, s->top_index); */
for(; (idx >= 0) && (idx >= s->top_index); --idx)
{
/*printf("idx %d, top_index = %d\n", idx, s->top_index);*/
e = s->arr[idx];
printf("%s = %d\n", e->name, e->num);
}
}
}

=================== OUTPUT ========================
[arnuld@dune C]$ gcc -ansi -pedantic -Wall -Wextra lifo-array.c
[arnuld@dune C]$ ./a.out
comp = 2
lang = 1
c = 0
-----------------------------------------

comp = 2
lang = 1

 

[Malcolm McLean]

WANTED:  To write an array implementation of Stack.
WHAT I GOT:  It works fine.

I think program is still little too complex. Any ideas to improve ?

..
Stacks are inherently simple. You have a chunk of memory, and a stack
top pointer or index. You push by adding an intem and incrementing
stack top, you pop by reading the top item and decrementing stack top.
Stacks are used in lots of places. The tricky part is deciding on the
interface for your particular stack.

For instance stacks are often used for global states. You have a
drawing package. You don't want every subroutine to have to query
every colour, linestyle, and font, store the state, and put them back.
So you might provide pushdrawingstate and popdrawing state. Probably
you want to store the stack as globals.
However on other occasions globals make it impossible to achieve what
you want, because you can only have one instance of each global stack
per program.

Then you've got to consider what happens if the caller pushes too many
items, or tries to pop an item that isn't there. If the user controls
the stack operations directly, then of course you've got to assume
that overflows and underflows will happen. If you are caller yourself,
it might be OK to be careful never to push more than 256 levels of
nested parentheses. Or maybe ypu want the stack to expand to fill all
available memory. This might open the program up to a denial of
service attack. The strategy of always passing errors up is a bad one,
as is the strategy of always crashing out - you have to decide what
the right interface is for your particular situation.

This is why software engineering is hard. Many projects fail because
of an accumulation of poor decisions, each small in themselves,
eventually makes further development impossible.

 

[Mark Bluemel]

WANTED: To write an array implementation of Stack.
Really?

void pop(struct elm_stack* );

Why would pop() not return a value?

 

[Rui Maciel]

Why would pop() not return a value?

Why should pop return a value?


Rui Maciel

 

[Willem]

Rui Maciel wrote:
) Mark Bluemel wrote:
)
)> On 06/16/2011 11:00 AM, arnuld wrote:
)>> WANTED: To write an array implementation of Stack.
)>
)> Really?
)>
)>> void pop(struct elm_stack* );
)>
)> Why would pop() not return a value?
)
) Why should pop return a value?

For the same reason as push() takes two arguments.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Chris M. Thomasson]

Why should pop return a value?

Because you can use the return value of the function itself as a predicate
for a condition? Perhaps a better name would be `try_pop()'; humm...

 

[Ian Collins]

Because you can use the return value of the function itself as a predicate
for a condition? Perhaps a better name would be `try_pop()'; humm...

Or simply use top() to read and pop() to pop.

 

[Chris M. Thomasson]

Or simply use top() to read and pop() to pop.

That does create a "gap" between `top()' and `pop()'; no problem for
single-threaded access...

 

[Chris M. Thomasson]

That does create a "gap" between `top()' and `pop()'; no problem for
single-threaded access...

WRT multi-threaded access it seems like the combined success to a call to
`top()' and a call to `pop()' would be analogous to a committed
transactional memory operation. Or simply lock the whole damn thing!

;^)

 

[Rui Maciel]

Because you can use the return value of the function itself as a predicate
for a condition? Perhaps a better name would be `try_pop()'; humm...

You have top for that, which, from that code, you can get with:

stack->arr[stack->top_index]

In this case, if you write your pop() to return the value then at worse you
perform a set of instructions which more often than not you don't even need
and at best end up needlessly using more code to perform a task that you
already get with a simple, single LoC.


Rui Maciel

 

[Rui Maciel]

) Why should pop return a value?

For the same reason as push() takes two arguments.

And what reason is that?


Rui Maciel

 

[Rui Maciel]

That does create a "gap" between `top()' and `pop()'; no problem for
single-threaded access...

And what leads you to believe that writing pop() so that it returns a value
will make the code immune to concurrency issues, or at least more vulnerable
than the version which doesn't return a value?


Rui Maciel

 

[Keith Thompson]

And what reason is that?

Convenience.

 

[Chris M. Thomasson]

And what leads you to believe that writing pop() so that it returns a
value
will make the code immune to concurrency issues, or at least more
vulnerable
than the version which doesn't return a value?

NO IMMUNITY!


I simply prefer the conditional `try_pop()' function because it can be so
easily used by the inherent pattern contained within the almighty
"eventcount" algorithm:

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/6cf4655c4e0b7c95

;^)

 

[Willem]

Rui Maciel wrote:
) Willem wrote:
)
)> ) Why should pop return a value?
)>
)> For the same reason as push() takes two arguments.
)>
)
) And what reason is that?

I don't know. Ask the person who proposed the API upthread.

If you insist that pop() shouldn't return a value, then push()
should not take a value either, just a stack. Otherwise it
is plainly inconsistent.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Keith Thompson]

Rui Maciel wrote:
) Willem wrote:
)
)> ) Why should pop return a value?
)>
)> For the same reason as push() takes two arguments.
)>
)
) And what reason is that?

I don't know. Ask the person who proposed the API upthread.

If you insist that pop() shouldn't return a value, then push()
should not take a value either, just a stack. Otherwise it
is plainly inconsistent.

pop() not returning a value makes some sense if you think that
shrinking the stack and retrieving the top element should be
separate operations.

push() without an argument would have to push an indeterminate or
default value onto the stack.

 

[Willem]

Keith Thompson wrote:
) pop() not returning a value makes some sense if you think that
) shrinking the stack and retrieving the top element should be
) separate operations.

push() not taking a value makes some sense if you think that
expanding the stack and setting the top element should be
separate operations.

) push() without an argument would have to push an indeterminate or
) default value onto the stack.

pop() without a return value would have to discard the value it
takes from the stack.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Mark Storkamp]

pop() not returning a value makes some sense if you think that
shrinking the stack and retrieving the top element should be
separate operations.

push() without an argument would have to push an indeterminate or
default value onto the stack.

Maybe the names are just poorly chosen. I always think of pop()
returning the top value and shrinking the stack. I would use drop() to
just shrink the stack. A push() without arguments could just duplicate
the top of the stack, but then you'd be better off calling that dup().

 

[Keith Thompson]

Keith Thompson wrote:
) pop() not returning a value makes some sense if you think that
) shrinking the stack and retrieving the top element should be
) separate operations.

push() not taking a value makes some sense if you think that
expanding the stack and setting the top element should be
separate operations.

*And* if you don't mind the new top of the stack having a meaningless
value. The two cases are not equivalent.

) default value onto the stack.

pop() without a return value would have to discard the value it
takes from the stack.

Of course. Sometimes that's what you want to do.

I'm not arguing that pop() *shouldn't* have a return value, just
that it's not entirely insane for it not to.

 

[Joe Pfeiffer]

Keith Thompson wrote:
) pop() not returning a value makes some sense if you think that
) shrinking the stack and retrieving the top element should be
) separate operations.

push() not taking a value makes some sense if you think that
expanding the stack and setting the top element should be
separate operations.

This would be an extraordinarily idiosyncratic usage.

) push() without an argument would have to push an indeterminate or
) default value onto the stack.

pop() without a return value would have to discard the value it
takes from the stack.

pop() without a return value wouldn't actually have to take a value from
the stack; it just moves the pointer.