• C

# stacks and quene

i don't understand how to write a program about stacks and quene, i know how they work, but i can't write it out in c program, pls help. also i don't understand how's the pointer in stacks and quene work, like the difference between (*top)-- and *top--
Asked:
###### Who is Participating?

Commented:
both, a stack and a queue are so-called linked lists. This means that one item stores a pointer to the next item. Thus, to traverse either structure, you need to look at every element and obtain pointers...I would love to give you an implementation but why since there are so many good ones out there. My first suggestion is to use C++ which provides both classes with convenient interfaces.

as for *top-- and (*top)--

The first one will decrease the pointer value by one, that is if you have a pointer to 0x00000128, *top-- will point to 0x00000127. (*top)-- will decrease the value stored at *top by one. So if the integer 4 is stored at 0x000000F3, then (*top)-- will be (4-1), -> 3.

hope this helps.
MaDdUCK
0

Author Commented:
Adjusted points to 100
0

Commented:
a linked list is a common way of implementing stacks and queues,
but not the only one
0

Author Commented:
element delete (int *top)
{
if (*top == -1)
return stack_empty();
return stack[(*top)--];
}
this is a function for deleting the toppest item in a stack, i would like to know why have to use (*top)-- if it wanna delete the top level
0

Commented:
linked list are definitely a good method for implementation though.

For some reason I don't get this function!
you are passing a pointer to an integer, then you query the value stored at the pointer. If it is -1 then you return the return value of return_empty() and if the pointer points to some other value (not -1) you take the integer stored at the pointer passed, subtract 1 from it and return the value.
Please get me on the right track here (lochau? ozo?).
0

Commented:
linked lists can indeed be a fine method for implementation.
it doesn't appear to be the method used be the above function though.
what I find very peculiar about that function the way responibility for knowing how the stack is stored seems to be divided between the caller and the callee
Why are you passing a pointer to top?
If the function knows where stack is, why doesn't it know where top is too?
I wouldn't expect you to have two tops for the same stack.
0

Author Commented:
This is a function i copied right out from my text book, the top  == -1 when the stack is empty, so if *top == -1, then return to another function stack_empty. but what i didn't get is the last line, the return stack[(*top)--] thing, i don't understand how this operation would erase the toppest item of the stack.  i hope this would help u guys out a bit

0

Commented:
the function does not seem to delete anything. Right now it returns the value stored at the address referred to by the pointer minus one, iff the stack is non-empty.
0

Commented:
what text book is this?
0

Commented:
it probably would have made more sense to have written the function as

element delete(){
if (top == -1) return stack_empty();
return stack[top--];
}

I see no sense in passing a pointer to top
perhaps the author just wanted to illustrate operations on (int *)
but here it just seems to confuse the issue.
0

Commented:
I'd agree .. it seems odd to pass the top of stack as a pointer, but NOT pass the stack[] array.

A more generic way to write this would be

element delete(element stack[], int* top){
if ((*top) == -1) return stack_empty();
return stack[(*top)--];
}

That way, the one 'delete' function can work with whatever stacks you are using (rather than use a global 'stack' variable - yuck!).

0

Commented:
or perhaps

element delete( struct stack *s ){
if( s->top == -1 ){ return stack_empty(s); }
return s->array[s->top--];
}
0

Commented:
lochau, basicly what is happening is the stack is stored in an array.  In the book you are using, it appears the array is called stack.  When you say:

return stack[(*top)--];

it returns the item at position *top, then decreases what top points to by 1. Heres an example of what is happening.

{            //Start of program, top=-1, stack = '?,?,?,?,?'
add(7,&top)  //top = 0, stack = '7,?,?,?,?'
add(2,&top)  //top = 1, stack = '7,2,?,?,?'
erase(&top)  //returns 2, then makes top = 0, stack = '7,?,?,?,?'
add(3,&top)  //top = 1, stack = '7,3,?,?,?'
.

in this case stack is an array of 5 char's.  I used the '?' to show that we don't care what those values are, we only care about the first top+1 items.  I hope this makes it clearer, and if you need me to explain something I can.

Mithander

0

Commented:
There are two usual ways of implementing stacks.

One is via a linked list.  In this case each item in the stack has a pointer to the item below it.  Each item needs to be created and destroyed (eg. malloc/free) - either your calling functions or the stack functions need to manage the items (just be consistent).  You also need to keep a separate top-of-stack pointer which you ensure always points to the top item on the stack (not surprisingly).  When this pointer is NULL, then the stack is empty.  To add a new item, you make create an item and make it point to the current top-of-stack item, and then set the top-of-stack pointer to the new item.  To remove an item from the stack, you simply make the top-of-stack pointer point to the item just below the current top item (making sure that you free up the old top item).

The second common way of implementing a stack is using an array.  You keep a count of how many items are in the stack.  When this count is zero, then the stack is empty.  Stack items are simply array elements.  The first element is the bottom of the stack.  To add an item, simply increase the count and use the next (unused) array element as your top of stack item.  To remove an item, simply decrease the count.

The advantage of a linked list is that the stack size is virtually (sic) unlimited ... you can use as much stack space as you have available memory for creating items.  Also the storage required for the stack varies proportionally with the number of items ... and empty stack takes (almost) no room.  The disadvantage is that items need to be bigger (to accomodate the linked list pointer).  Also allocating and freeing storage for the items takes time (so a linked list stack is slower - and you need to be careful to allocate and free items to avoid memory leaks etc)

The advantage of an array stack is speed .. it is very efficient (just inc/dec a counter).  Also individual items don't take up extra room (no pointers required).  And there is no need to allocate and free storage for items.  However, the disadvantage is that the stack always takes up the same amount of storage whether it is empty or full.  And the size (or depth) of the stack is limited by the size of the array.

Of course, you can combine these ideas (eg. have an array based stack that allocates more storage for iteself as the stack grows - usually in chunks rather than an item at a time; or use an array to keep unused stack items for a linked list so that storage allocation and freeing is quicker).

Queues are link stacks, but you add to one end and remove from the other.

Again, you can implement a queue with a linked list.  However, you usually need a pointer to each end of the list, and each items needs a pointer to the item beofer and after it in the queue.  This is called a doubly linked list.

You can also use an array for implementing a queue.  In this case, you need to keep track of the index of each end of the queue ... and when incrementing these indices, you need to wrap back around to zero when you reach the end of the array.  You can imagine the array as being a circle and the queue as being a snake that crawls around the circle as items are added and removed.

The issues in using either a linked list or array are the same for queues as they are for stacks.

In your example code the stack is implemented as an array of elements called 'stack'.  There is also an index referencing the topmost item in the stack (ie. the last element used in the array).  You deletion routine get a _pointer_ to this index (called top) and simply subtracts one from it to remove an item.  This code assumes that a value of -1 means the stack is empty.  A value of 0 means that stack[0] is the top of the stack, 1 means stack[1] is the top etc.

I hope this clears things up for you.

0

Commented:
Also, regarding *top-- and (*top)-- ....

if top is an int* (ie a pointer to an int) then

"*top" means the value of the itn the top is pointing to.  For example is you have an array of 5 ints and top points to (ie hold the address of) the 3rd item, then "*top" is the value of that 3rd item in the array.

"top--" means decrement the pointer so that it points to the int stored just before.  For example is you have an array of 5 ints and top points to (ie hold the address of) the 3rd item, then after doing "top--" top will now point to the 2nd item.

"(*top)--" means to decrement the value that top is pointing to.  The "*" is done first because of the "()", then the "--" applies to the value pointer to.

"*top--" means decrement the value of top first (the "--" is done first) (ie. make it point to the int before) and then return the value (the "*" is done last).  It is the same as "*(top--)".

Roger

0

Commented:
re:  *top-- and  (*top)--

(*top)-- decrements whatever top points at. ( as Roger mentioned ).

*top-- should be flagged by the compiler - probably L value required.

Matt
0

Commented:
(top--) can be an L value, but *(top--) will return the value of *top first, then decrement top
*(--top) will decrement top first then dereference
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

## Already a member? Login.

All Courses

From novice to tech pro — start learning today.