Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Array implementation of Stack (http://www.velocityreviews.com/forums/t750024-array-implementation-of-stack.html)

arnuld 06-16-2011 10:00 AM

Array implementation of Stack
 
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
-----------------------------------------

comp = 2
-----------------------------------------

[arnuld@dune C]$



--
www.lispmachine.wordpress.com
find my email-ID @above blog

Malcolm McLean 06-16-2011 01:55 PM

Re: Array implementation of Stack
 
On Jun 16, 1:00*pm, arnuld <sunr...@invalid.address> wrote:
> 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.
--
Read my book MiniBasic - how to write a script interpreter
http://www.lulu.com/bgy1mm




Mark Bluemel 06-16-2011 02:05 PM

Re: Array implementation of Stack
 
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?

Rui Maciel 06-16-2011 07:12 PM

Re: Array implementation of Stack
 
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?


Rui Maciel

Willem 06-16-2011 07:35 PM

Re: Array implementation of Stack
 
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 06-16-2011 08:35 PM

Re: Array implementation of Stack
 
"Rui Maciel" <rui.maciel@gmail.com> wrote in message
news:4dfa55b3$0$23522$a729d347@news.telepac.pt...
> 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?


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 06-16-2011 08:50 PM

Re: Array implementation of Stack
 
On 06/17/11 08:35 AM, Chris M. Thomasson wrote:
> "Rui Maciel"<rui.maciel@gmail.com> wrote in message
> news:4dfa55b3$0$23522$a729d347@news.telepac.pt...
>> 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?

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

--
Ian Collins

Chris M. Thomasson 06-16-2011 09:15 PM

Re: Array implementation of Stack
 
"Ian Collins" <ian-news@hotmail.com> wrote in message
news:95v8ljFd2pU12@mid.individual.net...
> On 06/17/11 08:35 AM, Chris M. Thomasson wrote:
>> "Rui Maciel"<rui.maciel@gmail.com> wrote in message
>> news:4dfa55b3$0$23522$a729d347@news.telepac.pt...
>>> 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?

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


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



Chris M. Thomasson 06-16-2011 09:19 PM

Re: Array implementation of Stack
 


"Chris M. Thomasson" <cristom@charter.net> wrote in message
news:unuKp.7810$_I7.7793@newsfe08.iad...
> "Ian Collins" <ian-news@hotmail.com> wrote in message
> news:95v8ljFd2pU12@mid.individual.net...
>> On 06/17/11 08:35 AM, Chris M. Thomasson wrote:
>>> "Rui Maciel"<rui.maciel@gmail.com> wrote in message
>>> news:4dfa55b3$0$23522$a729d347@news.telepac.pt...
>>>> 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?
>>>
>>> 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.

>
> 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 06-16-2011 09:43 PM

Re: Array implementation of Stack
 
Chris M. Thomasson wrote:

> 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


All times are GMT. The time now is 06:02 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.