How is a stack created and handled?

Question

Because anything from C++ and beyond have nice constructs that handles a "stack" like behavior(vectors, lists, array lists, etc), I want to keep the question in terms of C.

So, I am learning about compilers, stacks, inscript and postscript, parsers, lexers, and everything else that involves putting a compiler together as I will be required to later on in the my course for this semester. I want to make sure that my understanding of stacks is solid.

I believe I have the general idea on how one is put together. Basically you have an array following LIFO model. When you add an element, it is "pushed" in on the end of the array and "popped" off when removed. No issue there. My concern comes whith some the implementation detail. How are things like number of elements tracked? How large should a stack be initialized to? Should I use a structure to hold those details together? Are variables global?

My professor has already handed us some source code in relation to our assignment, I am just looking for some supplemental details for my own understanding (generally I have to put something together myself before getting an understanding of someone else's code). In most of my programming experience, the stack was some magical place that was beyond my control, but would explode if my recursive functions got too deep (SO anyone?).

Thanks in advance.

EDIT:

Ok, one thing I think I need to clarify is that I am not making a "true" stack, but will be required to take a an infix epxression and convert it to postfix. I am looking at the stack data structure so anything architecure related may not apply in this since. I was given the impression a stack was the way to handle this, likewise with rule reduction described in BNF notation.

Answer 1

What kind of stack are you talking about, here?

Most CPU architectures have a notion of a stack, which is how the CPU tracks function calls, basically. C is typically compiled to use the same stack for this purpose, and also often to use it for argument-passing.

Such "architectural" stacks don't require much, typically there's a register in the CPU that points to the top of the stack. It's the job of the operating system to make sure that every time a process starts, that process has a valid stack pointer. This is done by allocating the memory and initializing the register to the proper address. Modern "large" OS:es with virtual memory and so on often support growing the stack dynamically on demand.

The number of elements in the stack is not explicitly tracked in such cases, you can compute the number of bytes used by inspecting the current stack pointer and comparing to the process' (assumed known) "stack start", but that doesn't tell you about the internal structure of those bytes. This is normal for such low-level constructs.

---

If, as nos hints in a comment, you're really talking about a stack data structure, then there is no standard implementation for such a thing in C. It's possible to imagine many possible API:s, for instance:

typedef struct _Stack Stack;

Stack * stack_new(size_t element_size, size_t initial_depth, int allow_growth);
int     stack_push(Stack *stack, const void *element);
int     stack_pop(Stack *stack, void *element);
void    stack_peek(const Stack *stack, void *element);
size_t  stack_depth(const Stack *stack);
void    stack_clear(Stack *stack);

The above API leaves the initial depth and whether or not the stack should grow once you try to go beyond the limit up to the user. This is sensible for a general-purpose API, in my opinion.

Answer 2

It seems like you may be looking for info on the call stack. In that case, this post may help you out a lot.

http://altdevblogaday.com/2011/12/24/c-c-low-level-curriculum-part-4-more-stack/

This and the one previous to it (linked in the post) talk about how the stack works at the assembly level. Which is necessary as even C hides this away from you when you create functions.

This is probably most relevant from the perspective of compilers, but is probably the most important implementation of a stack.

Answer 3

How large should a stack be initialized to?

I think belongs individually to your use case.

How are things like number of elements tracked?

Your can store the information in an extra variable or count the elements each time.