A simple question about stack.........

[AmberJain]

Hello,

I am presently studying Data structures in C. And so I have a simple question about stack. The book which I got my hands on says about stack:

Note that the most frequently accessible element in the stack is the top most element, whereas the least accessible element is the bottom of the stack.

For me this quote (from the book) is a bit confusing. I think that every element on the stack must be potentially (and equally) available for reference/modification by the executing code. But the quote says that top most element is most accessible element.
And so I need your help.....


Should I first read some book on 'data structures' or 'data strucrtures in C'?
Also, can you please post the name of some "good" book for data structures in C? :)


Thanks in advance........
AmbrNewlearner

[boxfish]

You can only access the top element of a stack. The other ones are buried completely until you pop some items off the top of the stack. Info about stacks.

[JosAH]

In theory that's true: you can only push one element on the stack at the time and
you can only pop the top stack element (if there is one).

In practice however a stack is often implemented by an array or list or vector or
whatever. That underlying class often exposes its additional methods through
the stack class so you can fiddle diddle with other stack elements at will.
Do that at your own risk though ...

kind regards,

Jos

[Banfa]

When using a high(ish) level language like C (or C++) the stack entries are made in stack frames, every time a function call is made a stack frame is placed on the stack.

A stack frame contains all the data required by the processor to return form the function (various stack pointers and the return address) as well as space for all the stack (automatic) variables declared in the function.

As such you can only access the top-most entry in the stack but that is the top-most stack frame so you can access all the variables in the function because they are contained in a single stack entry. You can not access the variables from the function that call the current function or functions further up the call tree because that is in a higher entry on the stack.


I thought you may not be clear on what "an entry" on the stack was, for a high level language it is not a single variable.

[donbock]

1. An introductory-level text probably ignores the existence of stack frames as described by Banfa in #4.

2. In a canonical stack, only two locations will ever be accessed at any given time: POP reads from the top location of the stack; PUSH writes to the location just above the top location of the stack. But the top of the stack moves around.

3. A memory region has to be allocated to hold the stack. The need to keep the stack balanced means that the stack depth may grow on occassion, but it always shrinks back down again. The top of the stack will more often be near the bottom of the memory region than the top (where bottom refers to where the base of the stack is, which is not necessarily the lowest address).

I don't know if your book is referring to the logical top of the stack (as in #2 above), or the physical bottom of the stack memory region (as in #3 above).

[drhowarddrfine]

Am I missing something? I agree with the OP that every element on the stack is accessible at any time and no one element is any more difficult to get to than any other. If you examine the assembly of any C compiler you'll see this happening all the time with the ebp register used as the base pointer.

In addition, how is the compiler determining ahead of time which would be the most/least used datum? This doesn't make sense.

[boxfish]

I don't know anything about stacks. I was just faking it. I'm planning on taking a data structures and algorithms class next semester. But the functions on a stack class should only let you do anything to the top item, and a stack could be implemented as a linked list.

[AmberJain]

Hello,

@JosAH- Do you mean to say then that all the elements of stack are available for modification (although I may have to proceed at my own risk :)

@Banfa- If I interpret you correctly then you mean to say that we can access all the elements of a single stack entry.

Am I missing something? I agree with the OP that every element on the stack is accessible at any time and no one element is any more difficult to get to than any other. If you examine the assembly of any C compiler you'll see this happening all the time with the ebp register used as the base pointer.

In addition, how is the compiler determining ahead of time which would be the most/least used datum? This doesn't make sense.

Oh yes....this is what I meant to ask. Well, after going through replies of JosAH and Banfa I think I understand something but I am still confused.


Thanks......
AmbrNewlearner

[FishVal]

Hello,
I am presently studying Data structures in C. And so I have a simple question about stack. The book which I got my hands on says about stack:

It is more like a definition of Stack as data structure organized on LIFO principle - intrinsic property necessary and sufficient to define data structure as Stack.

For me this quote (from the book) is a bit confusing. I think that every element on the stack must be potentially (and equally) available for reference/modification by the executing code. But the quote says that top most element is most accessible element.
And so I need your help.....

And now you are talking about Stack as special memory segment addressed by ESS register. It has a special use as place for temporary storing of values (Asm: push/pop etc.) and return adresses for function calls (Asm: call) and return addresses with Flag register for interrupts.
High-level launguages use it to store automatic variables and pass arguments on function calls, thus, certainly providing free addressing within a certain stack frame assigned for a particular function. This certainly could not be considered as stack data structure, more like reserving flat memory space within a stack like organized larger memory space.

Regards,
Fish

[JosAH]

@JosAH- Do you mean to say then that all the elements of stack are available for modification (although I may have to proceed at my own risk :)

Theoretically a stack is no more than this:

class Stack {
public:
   virtual bool isEmpty();
   virtual E pop();
   virtual void push(E);
}

In practice however a class implementing this interface implements many more
methods: a 'list' of some sort might impement a 'virtual E getElement(int i)'
method that allows you to access other elements then the stack top element.
It all depends on the implementation for what you can do on top of the bare bones
Stack interface.

kind regards,

Jos

[Banfa]

I agree with the OP that every element on the stack is accessible at any time and no one element is any more difficult to get to than any other. If you examine the assembly of any C compiler you'll see this happening all the time with the ebp register used as the base pointer.

Not all processors have an ebp register (or equivalent), however that point aside,

You are correct that actually all of the process stack is available for reading and writing at any time during program execution, that is for instance how a symbolic debugger can give you the call stack, by reading the entire stack and using symbol tables to convert program counters to function names.

However in the normal course of writing a program the only part of the stack currently available to you are the variables defined in the current stack frame. To access any other part requires some decidedly platform specific pointer arithmetic and in the normal course of things would hardly be considered best practice.

That is of course assuming that you are using a software stack and not a hardware stack, sometimes with hardware stacks (as found on some micro-controllers) you actually do only have access to the top most entry.

It is jolly hard to generalise about something so platform dependent, for instance on many embedded applications I have worked on since the stack and the heap are in ram and you know the top and bottom address of ram (and in fact the start and end of the stack and heap segments) you can write or read to either of those segments without using what might be termed the proper channels (i.e. variables on the stack or allocations using malloc). That isn't to say that it is a good idea in general but you could do it.

[AmberJain]

Hello,

Thanks to all......I get it now.

AmbrNewlearner

[AmberJain]

Hello,

Which book would you refer me to read for data structures (specifically "Data structures in C")? I had recently completed with my C programming. I have no basic knowledge about Data structures and so what would you recommend for a "Data structure newbie"?

Thanks in advance........ ..
AmbrNewlearner

[JosAH]

Check out a couple of books by Robert Sedgewick; he has some data structures
and algorithms books in C/C++/Java; they're a nice read.

kind regards,

Jos

[AmberJain]

Check out a couple of books by Robert Sedgewick; he has some data structures
and algorithms books in C/C++/Java; they're a nice read.

kind regards,

Jos

Hello,

Ok, I will buy this book.

Thank you.......
AmbrNewlearner