Today I plan to stack up this 'dormant for a while' blog with some wisdom bytes stacked up in my tiny brain about (yes, you guessed it right) Stack.
So here we go ........
Stack
A stack is an abstract data structure based on the principle of Last in First out (LIFO).
It has two basic operations: push and pop.
Push adds a given data item to the top of the stack leaving previous items below.
Pop removes and returns the current top data item of the stack.
A stack is an abstract data structure based on the principle of Last in First out (LIFO).
It has two basic operations: push and pop.
Push adds a given data item to the top of the stack leaving previous items below.
Pop removes and returns the current top data item of the stack.
Stack oriented program flow
Stack is a ubiquitous data structure in the world of programming. It is used for a variety of purposes including reversing a string, implementing search techniques and most importantly for deciding program flow and run time memory management by almost all the modern programming languages. Let us now explore how programming languages use stack for dictating program flow.
A computer program is nothing but a set of instructions to the CPU which when executed in a particular sequence performs some useful task. The bigger the task the longer will be the list of instructions to be executed by the CPU. What do you do when you have to evaluate a big expression: {(x+y)-z} * r .You divide the expression into parts and evaluate each part one at a time like this:
Add X+Y first and then subtract Z from the sum and then multiply the result with r.
So you divided the problem into manageable parts and worked on each part separately.
Similarly to write a program for a very complex task you should first divide the task into simpler tasks and then write the code for each simple task. The piece of code for each simple task here is called a function. Each function after performing its designated task delivers the results through a return value. These functions work together to accomplish the actual task for which the program was written.
Now the question is how these functions work together. Here is the answer:
Every program has a function called main function at which the program execution starts. As you know each function has a designated task which it has to accomplish and deliver the results via its return value. The designated task of main function in any program is to accomplish the actual goal of the program in this case to evaluate the expression {(x+y)-z} * r and return the result of expression. Now we have divided the task into subtasks:
Task 1: add x, y
Task 2: Subtract z from sum of x and y .For that it should first know the sum. The Sum has been calculated in task 1 .So it should request task 1 to give it the sum.
Task 3: Multiply the result of task 2 with r. So taks 3 should somehow get the result of task 2.
Form above it is clear that if you want to divide your program into functions there should be a means for functions to communicate.
A function requesting another function to do a subtask on its behalf is called calling a function.
When a function calls another function to perform a subtask it also provides the data on which subtask need to be performed in the form of parameters or arguments. The called function in turn delivers the results in the form of its return value.
So now we know that functions in a program communicate by calling function passing the parameters or arguments to the called function. Now there should be a place in memory for called function to keep the arguments passed before it work on it.
Further a function code consists of other statements interlaced with function calls.So once the called function is done with its subtask the program flow should come back to the calling function and proceed from the statement next to function call.For that it should know the address of next instruction in memory.
For all this every program creates a stack called call stack for itself near the high addresses of Process Address Space. As and when functions are called their argument values, return addresses and local variables(except static variables) are pushed on to the stack and retained there as long as the function is running. All this information pushed onto stack is called a stack frame.Once the function completes its subtask its stack frame is popped out from stack and control is returned to the return address retrieved from the stack frame.
A computer program is nothing but a set of instructions to the CPU which when executed in a particular sequence performs some useful task. The bigger the task the longer will be the list of instructions to be executed by the CPU. What do you do when you have to evaluate a big expression: {(x+y)-z} * r .You divide the expression into parts and evaluate each part one at a time like this:
Add X+Y first and then subtract Z from the sum and then multiply the result with r.
So you divided the problem into manageable parts and worked on each part separately.
Similarly to write a program for a very complex task you should first divide the task into simpler tasks and then write the code for each simple task. The piece of code for each simple task here is called a function. Each function after performing its designated task delivers the results through a return value. These functions work together to accomplish the actual task for which the program was written.
Now the question is how these functions work together. Here is the answer:
Every program has a function called main function at which the program execution starts. As you know each function has a designated task which it has to accomplish and deliver the results via its return value. The designated task of main function in any program is to accomplish the actual goal of the program in this case to evaluate the expression {(x+y)-z} * r and return the result of expression. Now we have divided the task into subtasks:
Task 1: add x, y
Task 2: Subtract z from sum of x and y .For that it should first know the sum. The Sum has been calculated in task 1 .So it should request task 1 to give it the sum.
Task 3: Multiply the result of task 2 with r. So taks 3 should somehow get the result of task 2.
Form above it is clear that if you want to divide your program into functions there should be a means for functions to communicate.
A function requesting another function to do a subtask on its behalf is called calling a function.
When a function calls another function to perform a subtask it also provides the data on which subtask need to be performed in the form of parameters or arguments. The called function in turn delivers the results in the form of its return value.
So now we know that functions in a program communicate by calling function passing the parameters or arguments to the called function. Now there should be a place in memory for called function to keep the arguments passed before it work on it.
Further a function code consists of other statements interlaced with function calls.So once the called function is done with its subtask the program flow should come back to the calling function and proceed from the statement next to function call.For that it should know the address of next instruction in memory.
For all this every program creates a stack called call stack for itself near the high addresses of Process Address Space. As and when functions are called their argument values, return addresses and local variables(except static variables) are pushed on to the stack and retained there as long as the function is running. All this information pushed onto stack is called a stack frame.Once the function completes its subtask its stack frame is popped out from stack and control is returned to the return address retrieved from the stack frame.
No comments:
Post a Comment