Solved

stacks and quene

Posted on 1998-10-22
17
383 Views
Last Modified: 2007-10-18
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--
0
Comment
Question by:lochau
  • 5
  • 4
  • 3
  • +3
17 Comments
 

Author Comment

by:lochau
ID: 1253752
Adjusted points to 100
0
 
LVL 8

Accepted Solution

by:
MaDdUCK earned 100 total points
ID: 1253753
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
 
LVL 84

Expert Comment

by:ozo
ID: 1253754
a linked list is a common way of implementing stacks and queues,
but not the only one
0
 

Author Comment

by:lochau
ID: 1253755
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
 
LVL 8

Expert Comment

by:MaDdUCK
ID: 1253756
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
 
LVL 84

Expert Comment

by:ozo
ID: 1253757
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 Comment

by:lochau
ID: 1253758
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
 
LVL 8

Expert Comment

by:MaDdUCK
ID: 1253759
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
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
LVL 8

Expert Comment

by:MaDdUCK
ID: 1253760
what text book is this?
0
 
LVL 84

Expert Comment

by:ozo
ID: 1253761
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
 
LVL 10

Expert Comment

by:RONSLOW
ID: 1253762
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
 
LVL 84

Expert Comment

by:ozo
ID: 1253763
or perhaps

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

Expert Comment

by:Mithander
ID: 1253764
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
 
LVL 10

Expert Comment

by:RONSLOW
ID: 1253765
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
 
LVL 10

Expert Comment

by:RONSLOW
ID: 1253766
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
 
LVL 1

Expert Comment

by:MatthewL
ID: 1253767
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
 
LVL 84

Expert Comment

by:ozo
ID: 1253768
(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

Featured Post

Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

Join & Write a Comment

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.

757 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now