Array implementation of Stack


A

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 ========================
[[email protected] C]$ gcc -ansi -pedantic -Wall -Wextra lifo-array.c
[[email protected] C]$ ./a.out
comp = 2
lang = 1
c = 0
-----------------------------------------

comp = 2
lang = 1
 
Ad

Advertisements

M

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

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
 
C

Chris M. Thomasson

Rui Maciel said:
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...
 
Ad

Advertisements

I

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

Chris M. Thomasson

Ian Collins said:
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...
 
C

Chris M. Thomasson

Chris M. Thomasson said:
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!

;^)
 
R

Rui Maciel

Chris said:
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
 
Ad

Advertisements

R

Rui Maciel

Chris said:
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
 
C

Chris M. Thomasson

Rui Maciel said:
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

;^)
 
W

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
 
K

Keith Thompson

Willem said:
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.
 
Ad

Advertisements

W

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
 
M

Mark Storkamp

Keith Thompson said:
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().
 
K

Keith Thompson

Willem said:
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.
 
Ad

Advertisements

J

Joe Pfeiffer

Willem said:
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.
 

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

Queue - can not delete last element 6
compressing charatcers 35
wcstombs() problem 16
Stack using doubly linked list 1
Stack using Array 16
selection-sort in C 22
perror()4 says SUCCESS 10
Pointer Problem 9

Top