What's a stack?

This is a discussion on What's a stack? within the C Programming forums, part of the General Programming Boards category; Ok . . . I'm learning to program in C. I've been reading books/articles which have mentioned the "stack" or ...

  1. #1
    Registered User
    Join Date
    Jul 2008
    Posts
    15

    What's a stack?

    Ok . . . I'm learning to program in C. I've been reading books/articles which have mentioned the "stack" or "call stack". However, I have no idea what a stack is. . . . wikipedia is too complicated... http://en.wikipedia.org/wiki/Call_stack .

    Help?

    Thanks!

  2. #2
    Super Moderator
    Join Date
    Sep 2001
    Posts
    4,913
    The stack is memory that the system allocates for a program when it runs. The call stack is memory that is used to keep track of what code is running and what routines have been called.

    To put this in context, there's another thing called a heap. I remember their uses this way: a stack is an organized pile, a heap is unorganized. The stack is where your variables get declared, it's where your functions (or calls) are handled, etc... The heap is memory you have to manage yourself - the system doesn't organize it for you.

    So simply put - the stack is simply memory that's given to you and somewhat run by the system. As a beginner in programming- you probably won't have to worry about what it means, but remembers this when you start having to work with memory, etc...

  3. #3
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    For example, when you dynamically allocate memory (e.x. malloc() ) you allocate memory from the heap. Local variables in functions are allocated in the stack

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You can think of a stack like a stack of plates. Each plate represents some sort of data element, from this category list:
    1. The return address back to where the function was called.
    2. The argument passed to a function.
    3. A local variable within a function.

    When you return from a function, all local variable plates and the plate with the return address is taken off the the stack. The return address plate is used to find the calling function so that execution can continue there. The calling function will remove the plates added to give the arguments to the function.

    If we have the following code:
    Code:
    int main()
    {
       func1(7, 8);
       return 0;
    }
    
    void func1(int x, int y)
    {
        int d = 9;
        func2(y);
    }
    
    void func2(int a)
    {
        int b = 11;
        ... do some stuff ... 
    }
    Inside func2, the stack will have:
    b (with the value 11)
    return address in func1.
    a (with the value 8)
    d (with the value 9)
    return address to main
    x (with the value 7)
    y (with the value 8)
    return address to C startup code.

    When the return back from func2 to func1, the stuff down to a is removed, and inside func1, the argument a will be removed, and eventually, we return back to main and the
    x, y arguments are cleared off the stack, and finally main will return to where it came from.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    pursuant to what matsp wrote and "beginnerness": the structure of memory and the way it is literally used have given form to the language itself (and probably the language has influenced the construction of physical memory). So a lot of concepts get explained in relation to memory and the way it's managed. Two big central issues for me in learning and understanding have been:

    1) allocation
    2) reference and pointing

    I think learning to use strtok is good here, because it helps to illustrate how a (possibly large) chunk of memory can be manipulated with pointers (the address the pointer points to is literally somewhere inside this contiguous chunk) AND the consequence (since the pointer is literally nothing, if you play with it you're really playing with a piece of the larger structure). Which is why we are warned:

    "if a part of a program does not have as its purpose the modification of a certain data structure, then it is error-prone to modify the data structure temporarily."

    Which I think means if you didn't want to change something permanently, you're better playing with a copy. That may be part of why we get a "stack" seperate from a "heap".
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    A stack is NECESSARY (at least for languages that wishes to support many levels of function calls [aka levels of nesting] and arbitrary number/type of parameters). In nearly all processors except the really tiny embedded processors, the stack is part of the processor architecture, and there is support to handle function calls in the instruction set, so a function call and the return from the function call translates directly into processor instructions, just like "+" becomes an add instruction, and "-"becomes a subtract instruction.

    The heap, on the other hand, is not directly supported as such by the processor - it is just a lump of memory that an application can be asking for a chunk of.

    The stack is also "automatically cleaning up", so when you go back from a function, the stack content is cleaned up (the compiler takes care of doing that), whilst the heap, the code needs to say "don't use this memory any more" in some way (usually by calling "free()" in C, and "delete" in C++).

    And one thing to remember: Since data on the stack "disappears", it is invalid to pass back a reference to a stack variable to a calling function. Typically, this appears when someone writes code to return a local string variable.

    Some languages have ONLY stack, such as the languages Forth and PostScript.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. stack and pointer problem
    By ramaadhitia in forum C Programming
    Replies: 2
    Last Post: 09-12-2006, 12:41 AM
  2. infix evaluation using stack
    By lewissi in forum C++ Programming
    Replies: 0
    Last Post: 11-03-2005, 02:56 AM
  3. Question about a stack using array of pointers
    By Ricochet in forum C++ Programming
    Replies: 6
    Last Post: 11-17-2003, 10:12 PM
  4. error trying to compile stack program
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-03-2003, 06:27 PM
  5. Stack Program Here
    By Troll_King in forum C Programming
    Replies: 7
    Last Post: 10-15-2001, 06:36 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21