CODEWITHSUNDEEP
c++stackcomputer-science
malhobayyeb
malhobayyeb

Reputation: 2883

What does LIFO really mean?

As mentioned in this tutorial: http://www.learncpp.com/cpp-tutorial/79-the-stack-and-the-heap/

In computer programming, a stack is a container that holds other variables (much like an array). However, whereas an array lets you access and modify elements in any order you wish, a stack is more limited. The operations that can be performed on a stack are identical to the ones above:

1) Look at the top item on the stack (usually done via a function called top()) 2) Take the top item off of the stack (done via a function called pop()) 3) Put a new item on top of the stack (done via a function called push())

But if I defined two variables in C++ I do not have to use them in the same order of definition:

Example:

int main() {
 int a;
 int b;

 b = 5;
 a = 6;
}

Is there a problem on this code? I can use them in any order I like!! I do not have to use the a first then the b.

Am I misunderstanding something? What is it?

Upvotes: 0

Views: 2387

Answers (7)

Puppy
Puppy

Reputation: 146970

You don't have to use them in the order defined. But they are destroyed - taken off the stack- in that order. LIFO does not refer to access, only putting things on or taking them off the stack.

You can trivially observe this by changing int for a type which prints in it's destructor.

Upvotes: 1

Imposter
Imposter

Reputation: 2686

Like any other data structure , stack is a data structure which follows LIFO(last in first out) principle.As mentioned in your question it does push and pop operation for inputting and retrieving data according to LIFO principle.

Every process consists of basically 4 portions of address space that are accessible to the process when it is running

Text - This portion contains the actual m/c instructions to be executed. On many Operating Systems this is set to read only, so that the process can't modify its instructions. This allows multiple instances of the program to share the single copy of the text.

Data - This portion contains the program's data part. It furthere divided into

1) Initialized Read Only Data - This contains the data elements that are initialized by the program and they are read only during the execution of the process.

2) Initialized Read Write Data - This contains the data elements that are initialized by the program and will be modified in the course of process execution.

3)Uninitalized Data - This contains the elements are not initialized by the program and are set 0 before the processes executes. These can also be modified and referred as BSS(Block Started Symbol). The adv of such elements are, system doesn't have to allocate space in the program file for this area, b'coz it is initialized to 0 by OS before the process begins to execute.

Stack - This portion is used for local variables, stack frames

Heap - This portion contains the dynamically allocated memory

int abc = 1;                            ---->   Initialized Read-Write Data
char *str;                              ---->   BSS
const int i = 10;                       ----->  Initialized Read-Only Data

main()
{
    int ii,a=1,b=2,c;                            ----->  Local Variables on 
Stack

    char *ptr;
    ptr = malloc(4);                     ------> Allocated Memory in Heap

     c= a+b;                             ------> Text

}

Data, store data Text, store code

There are 3 (main?) segments/sections of the file produced by a linker. text - program text (and apparently const char arrays. maybe other 'const' arrays, since those can not be changed anyway). I am not 100% sure about the array part, maybe someone will correct me.

data - initialized global data. see examples below. bss - uninitialized global data. Here are some examples

int x = 1;    /* goes into data */
int y;        /* goes into bss  */
const int z = 1;

this, we've seen go into 'text', since can't be changed anyway,but can be protected

const char array[] = {'a','b'....etc}


/* the rest goes into text */

int main(void)
   {
     return EXIT_SUCCESS;
   }

Block Started by Symbol

(BSS) The uninitialised data segment produced by Unix linkers. The other segments are the "text" segment which contains the program code and the "data" segment contains initialised data. Objects in the bss segment have only a name and a size but no value.

Upvotes: 1

Murali Krishna
Murali Krishna

Reputation: 311

Stack program:

Your example program is not an implementation of stack. Stack shall store elements like an array (or by some means) where elements can be pushed (stored) or poped (pulled out) in LIFO (last in first out) order. It's implementation is not as simple as declaring two variables. Standard C++ provides stack class so that you can use it without having to implement on your own.

Stack Memory:

Variables in a function are stored in stack memory (Somewhere in the RAM) in LIFO order. From your example, Variable a will be created and pushed to stack memory. Then, the variable b is pushed to stack memory. After the function completes it's execution, the variables are destroyed in LIFO fashion. So variable b is the first to get destroyed and finally variable a gets destroyed. You don't write the code for it. The compiler takes care to write assembly low level code for it.

Upvotes: 0

Karl Knechtel
Karl Knechtel

Reputation: 61597

Am I misunderstanding something? What is it?

The "stack" that you're putting 'a' and 'b' on is (WARNING HUGE SIMPLIFICATIONS AND CONCEPTUALIZATIONS AHEAD) not made out of variables; it is made out of stack frames. A stack frame consists of the parameters to a function and a space for its return value, and sometimes also the variables used within the function (except that these can also be held in registers, and sometimes parameters are also passed via the registers). "Pushing" onto this stack is accomplished by calling a function. "Popping" from this stack is accomplished by returning from a function. You indeed only have access to the "top" element; you can't just read the variables of the function that called the current function, unless they were explicitly passed in as parameters.

Upvotes: 1

Hot Licks
Hot Licks

Reputation: 47739

Yep, the "automatic storage" that holds a called method's local variables is allocated in a stack. But with the automatic storage stack you push and pop (variable sized) "stack frames" that contain all of the local variables for a method, not individual values.

This is conceptually similar to the kind of stack discussed in the article you quote, except that the items being pushed and popped are much larger.

In both cases the mechanism is "LIFO", since when you call a method you essentially return by "popping the stack" -- you always have to return from methods in the opposite order that you called them.

Upvotes: 4

seand
seand

Reputation: 5296

A stack is a standard data structure that's used all over the place. A thread's so called stack is in fact an implementation of this paradigm. There's a stack pointer (usually in a processor register) that points to a memory location. Data is 'pushed' onto this stack by moving the sp. We 'pop' by returning the value it points to and moving the sp the opposite direction.

As far as your a, b declared above it makes no difference. They're both allocated before they get used.

Upvotes: 0

Bill Lynch
Bill Lynch

Reputation: 81976

You are confusing two different kinds of stacks.

One stack, is where some of the memory for your application is allocated. This would be part of a discussion about the stack and heap and where your memory is allocated.

The other kind of stack is a data structure that conforms to a LIFO style of access. This could be implemented using a std::vector or other forms of data structures.

Upvotes: 8

Related Questions