What is a stack? Example: calculator in reverse Polish notation
A stack is a programming phenomenon and a natural solution. Stack immediately came into the computer business and became so “native”, as if it was where it all began.
Without a stack, the processor does not work, there is no recursion, and it is impossible to organize efficient function calls. Any algorithm can do without a queue, list, collection, array, or system of organized objects, but nothing works without memory and a stack, including all of the above.
At the dawn of the beginning: processor, memory and stack
Ideal memory provides addressing directly to the value - these are the machine and language levels of a high degree. In the first case, the processor sequentially iterates through memory addresses and executes instructions. In the second case, the programmer manipulates arrays. Both episodes contain:
- address = value;
- index = value.
The address can be absolute and relative, the index can be digital and associative. The address and index may contain another address than a value, but these are the details of indirect addressing. Without memory, a processor cannot work, and without a stack of commands and data, it is like a boat without oars.
A stack of plates is a traditional story about the essence of a stack: the concept of stack and translation in the common consciousness. You cannot take a plate from below, you can only take it from above, and then all the plates will be intact.
Whatever comes last on the stack goes first. The perfect solution. In essence, stack, as a translation of one action into another, transforms the idea of an algorithm as a sequence of operations.
The essence and concept of a stack
Processor and memory - main structural elements computer. The processor executes instructions, manipulates memory addresses, and retrieves and modifies values at these addresses. In a programming language, all this is transformed into variables and their values. The essence of the stack and the concept of last in first out (LIFO) remains unchanged.
The acronym LIFO is no longer used as often as it used to be. Probably because lists have been transformed into objects, and first in first out (FIFO) queues are used as needed. The dynamics of data types has lost its relevance in the context of describing variables, but has acquired its significance at the time of execution of expressions: the type of a data is determined at the moment of its use, and until that moment you can describe anything and any way you want.
So, stack - what is it? Now you know that this is an inappropriate question. After all, without a stack there is no modern programming. Any function call means passing parameters and a return address. A function can call another function - this is again passing parameters and a return address. Setting up a mechanism for calling values without a stack is extra work, although an achievable solution is certainly possible.
Many people ask: “Stack - what is it?” In the context of a function call, it consists of three actions:
- saving the return address;
- saving all transferred variables or addresses to them;
- function call.
Once the called function has completed its mission, it will simply return control to the return address. A function can call any number of other functions, since the limit is only the size of the stack.
Stack properties
A stack is not an abstract data type, but a real mechanism. At the processor level, it is an “engine” that refines and complements the work of the main processor cycle. Like bit arithmetic, the stack captures simple and obvious rules of operation. It's reliable and safe.
The characteristic properties of a stack are its size and the length of its elements. At the processor level, everything is determined by the bit capacity, memory addressing and the physics of access to it. Interesting feature and tradition: the stack grows downwards, that is, towards decreasing memory addresses, and program and data memory - upwards. This is common, but not required. The meaning here is important - he came last and left first. This surprisingly simple rule allows you to build interesting algorithms that work primarily in languages high level. Now you won't ask, what is a stack?
Impeccable work hardware has been the norm for a very long time, but at the forefront information technologies The idea of a stack is gaining new and promising applications.
Essentially, it doesn't matter what the stack is at the processor level. It is a natural part of computer architecture. But in programming, the stack depends on the specific application and the ability of the programmer.
Arrays, collections, lists, queues... Stack!
People often ask the question: "Stack - what is it?" “Programming” and “systematization” are interesting concepts: they are not synonyms, but they are so closely related. Programming has gone such a long way very quickly that the peaks reached seem ideal. Most likely this is not the case. But obviously something else.
The idea of a stack has become familiar not only at the level of various programming languages, but also at the level of their designs and capabilities for creating data types. Any array has push and pop, and the concepts of “the first and last elements of the array” have become traditional. Previously there were just array elements, but today there are:
- array elements;
- first element of the array;
- the last element of the array.
The operation of placing an element in an array moves the pointer, and retrieving an element from the beginning of the array or from its end makes a difference. Essentially this is the same stack, but applied to other data types.
It is especially noteworthy that popular programming languages do not have a stack construct. But they provide his idea to the developer in full.
Hello, I'm a second year student technical university. After missing a few programming classes due to health reasons, I was faced with a lack of understanding of topics such as Stack and Queue. Through trial and error, after a few days, it finally dawned on me what it was and what it was eaten with. So that your understanding does not take so much time, in this article I will talk about what a “Stack” is, how and with what examples I understood what it is. If you like it, I will write a second part, which will touch upon such a concept as “Queue”
Theory
On Wikipedia the definition of a stack is:
Stack (English stack - stack; read stack) is an abstract data type, which is a list of elements organized according to the LIFO principle (English last in - first out, “last in - first out”).
A fairly complete definition, but perhaps a little difficult to understand for beginners.
Therefore, the first thing I would like to focus on is representing the stack in the form of things from life. The first interpretation that came to my mind was in the form of a stack of books, where the top book is the top.
In fact, a stack can be represented as a stack of any objects, be it a stack of sheets, notebooks, shirts, etc., but I think the example with books will be the most optimal.
So, what does a stack consist of?
The stack consists of cells (in the example, these are books), which are represented as a structure containing some data and a pointer to the type of this structure to the next element.
Difficult? No problem, let's figure it out.
This picture schematically shows the stack. The block of the form “Data/*next” is our cell. *next, as we see, points to the next element, in other words, the *next pointer stores the address of the next cell. The *TOP pointer points to the top of the stack, that is, it stores its address.
We're done with theory, let's move on to practice.
Practice
First we need to create a structure that will be our “cell”
C++ code
struct comp ( //Structure called comp (from the word component) int Data; //Some data (can be any, for example you can write int key; char Data; you can also add some other data) comp *next;//Comp type pointer to the next element);
Beginners may not understand why our pointer is of type comp, or more precisely, a pointer of the comp structure type. Let me explain, in order for the *next pointer to store the comp structure, it needs to indicate the type of this structure. In other words, indicate what the pointer will store.
Once we have the “Cell” set, let’s move on to creating functions.
Functions
Function of creating a “Stack”/adding an element to the “Stack”
When adding an element, we will have two situations:
- The stack is empty and needs to be created
- The stack already exists and you just need to add it to it new element
C++ code
void s_push(comp **top, int D) ( //function of type void (does not return anything) which takes a pointer to the top of the stack and a variable that will be written to cell comp *q; //Create a new pointer q of the structure type comp. By in essence, this is our new element q = new comp(); //allocate memory for the new element q->Data = D; //Write the required number in the Data element if (top == NULL) ( //If there is no vertex, that is, the stack is empty *top = q; //the top of the stack will be a new element) else //if the stack is not empty ( q->next = *top; //We draw a connection from the new element to the top. That is, we put the book on the top of the stack . *top = q; //Denote that the top is now a new element ) )
Let's look at it in a little more detail.
First, why the function accepts **top, that is, a pointer to a pointer, in order to make it more clear to you, I will leave consideration of this issue for later. Secondly, let's talk in more detail about q->next = *top and about what it means ->
.
-> means that, roughly speaking, we go into our structure and take out an element of this structure from there. In line q->next = *top We take a pointer to the next element *next from our cell and replace it with a pointer that points to the top of the stack *top. In other words, we make a connection from the new element to the top of the stack. There is nothing complicated here, everything is like with books. We place the new book exactly on the top of the stack, that is, we draw a connection from the new book to the top of the stack of books. After that A new book automatically becomes the top, since the stack is not a stack of books, we need to indicate that the new element is the top, for this we write: *top = q;.
Function for removing an element from the “Stack” based on data
This function will remove an element from the stack if the number of Data of the cell (q->Data) is equal to the number that we ourselves will designate.
There may be the following options:
- The cell we need to remove is the top of the stack
- The cell we need to delete is at the end, or between two cells
C++ code
void s_delete_key(comp **top, int N) (//a function that takes the top top and the number to be deleted comp *q = *top; //create a comp type pointer and equate (put) it to the top of the stack comp *prev = NULL;//we create a pointer to the previous element, from the beginning it will be empty while (q != NULL) (//while the pointer q is not empty, we will execute the code in a loop, if it is still an empty loop ends if (q-> Data == N) (//if the Data of the element is equal to the number that we need to remove if (q == *top) (//if such a pointer is equal to the top, then there is an element that we need to remove - the top *top = q- >next;//move the vertex to the next element free(q);//clear the cell q->Data = NULL; //Next, to avoid errors, we reset the variables in the remote cell, since in some compilers the remote cell has non-NULL variables values, but literally “Memory reading is impossible” or numbers “-2738568384” or others, depending on the compiler q->next = NULL ) else//if the element is the last one or is between two other elements ( prev->next = q ->next;//Draw a connection from the previous element to the next free(q);//clear the cell q->Data = NULL;//zero the variables q->next = NULL;
) ) // if the element's Data is NOT equal to the number we need to remove prev = q; //remember the current cell as the previous one q = q->next;//move the pointer q to the next element ) ) Pointer q in in this case plays the same role as a pointer in a notepad, it runs around the entire stack until it becomes NULL( while(q != NULL)
To better understand the removal of an element, let’s draw an analogy with the already familiar stack of books. If we need to remove a book from above, we remove it, and the book below it becomes the top one. It’s the same here, only at the beginning we must determine that the next element will become the top *top = q->next; and only then delete the element free(q);
If the book to be removed is between two books or between a book and a table, the previous book will fall on the next one or on the table. As we already understood, our book is a cell, and the table turns out to be NULL, that is next element No. It turns out the same way as with books, we designate that the previous cell will be connected to the next one prev->next = q->next;, it is worth noting that prev->next can be equal to either a cell or zero, if q->next = NULL, that is, there is no cell (the book will lie on the table), after that we clear the cell free(q).
It is also worth noting that if you do not this connection, the section of cells that lies after the deleted cell will become inaccessible, since the very connection that connects one cell to another will be lost and this section will simply be lost in memory
Stack display function
The simplest function:
C++ code
void s_print(comp *top) ( //accepts a pointer to the top of the stack comp *q = top; //set q to the top while (q) ( //as long as q is not empty (while(q) is equivalent to while(q != NULL )) printf_s("%i", q->Data);//display the data of the stack cell q = q->next;//after displaying it, move q to the next element (cell) ) )
Here I think everything is clear, I just want to say that q should be perceived as a slider, it runs across all cells from the top where we set it at the beginning: *q = top;, to the last element.
Main function
Okay, we have written down the main functions for working with the stack and call them.
Let's look at the code:
C++ code
void main() ( comp *top = NULL; //at the beginning of the program we do not have a queue, therefore there is no vertex, we give it NULL value//Next we start adding numbers from 1 to 5 to our stack s_push(&top, 1);
Let's return to why we passed a pointer to the vertex pointer to the function. The fact is that if we introduced only a pointer to the vertex into the function, then the “Stack” would be created and changed only inside the function; in the main function the vertex would be and remain NULL. By passing a pointer to a pointer, we change the *top vertex in the main function. It turns out that if a function changes the stack, you need to pass a vertex to it with a pointer to a pointer, as we did in the s_push, s_delete_key function. In the s_print function, the “Stack” should not change, so we simply pass a pointer to the top.
Instead of the numbers 1,2,3,4,5, you can also use int type variables.
Conclusion
Full program code:
C++ code
#include
Execution result
Since elements are constantly being added to the top of the stack, elements will be displayed in reverse order.
In conclusion, I would like to thank you for the time you spent on my article, I really hope that this material helped some novice programmers understand what the “Stack” is, how to use it, and in the future they will no longer have problems. Write your opinion in the comments, as well as how I can improve my articles in the future. Thank you for your attention.
Tags: Add tags
Tags: Stack, stack in C, implementation of a stack, stack on an array, dynamically growing stack, stack on a singly connected system
Stack
S tek is probably the most simple structure data that we will study and which we will constantly use. A stack is a data structure in which the elements support the LIFO (“Last in – first out”) principle: last in, first out. Or first in, last out.
A stack allows you to store elements and usually supports two basic operations:
- PUSH– puts an element on the top of the stack
- POP– removes an element from the top of the stack, moving the top to the next element
Also common is the PEEK operation, which gets an element at the top of the stack but does not remove it from there.
The stack is one of basic structures data and is used not only in programming, but also in circuit design, and simply in production, for the implementation technological processes etc.; The stack is used as an auxiliary data structure in many algorithms and other more complex structures.
Let, for example, we have a stack of numbers. Let's run a few commands. Initially the stack is empty. The top of the stack is a pointer to the first element, it does not point anywhere. In the case of C, it can be equal to NULL.
The stack now consists of one element, the number 3. The top of the stack points to the number 3.
The stack consists of two elements, 5 and 3, with the top of the stack pointing to 5.
The stack consists of three elements, the top of the stack points to 7.
It will return the value 7, leaving 5 and 3 on the stack. The top will point to the next element – 5.
Returns 5, leaving only one element on the stack, 3, to which the top of the stack will point.
Returns 3, the stack will be empty.
A stack is often compared to a stack of plates. To get next plate, you need to remove the previous ones. The top of the stack is the top of a stack of plates.
When we work with the stack, two main and common errors are possible:
- 1. Stack Underflow: Trying to pop an element from an empty stack
- 2. Stack Overflow: Trying to put a new element on a stack that can't grow anymore (for example, there's not enough RAM)
Software implementation
Let's look at three simple implementations stack:
Fixed size stack built on an array
A distinctive feature is the ease of implementation and maximum speed execution. Such a stack can be used when its maximum size is known in advance or is known to be small.
First, we determine the maximum size of the array and the type of data that will be stored in it:
#define STACK_MAX_SIZE 20 typedef int T;
Now the structure itself
Typedef struct Stack_tag ( T data; size_t size; ) Stack_t;
Here the variable size is the number of elements, and at the same time a pointer to the top of the stack. The top will point to the next element of the array, which will contain the value.
We put a new element on the stack.
Void push(Stack_t *stack, const T value) ( stack->data = value; stack->size++; )
The only problem is that you can go beyond the array. Therefore, you should always check that there are no Stack overflow errors:
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 void push(Stack_t *stack, const T value) ( if (stack->size >= STACK_MAX_SIZE) ( exit(STACK_OVERFLOW); ) stack->data = value; stack->size++ ; )
Similarly, let's define a Pop operation that returns an element from the top and moves on to the next one
T pop(Stack_t *stack) ( if (stack->size == 0) ( exit(STACK_UNDERFLOW); ) stack->size--; return stack->data; )
AND peek function, returning the current element from the top
T peek(const Stack_t *stack) ( if (stack->size<= 0) { exit(STACK_UNDERFLOW); } return stack->data; )
Another important note– we don’t have a stack creation function, so we need to manually reset the size value
Helper functions for printing stack elements
Void printStackValue(const T value) ( printf("%d", value); ) void printStack(const Stack_t *stack, void (*printStackValue)(const T)) ( int i; int len = stack->size - 1 ; printf("stack %d > ", stack->size);< len; i++) { printStackValue(stack->data[i]);
printf(" | ");
) if (stack->size != 0) ( printStackValue(stack->data[i]); ) printf("\n"); )
Note that in the print function we use int rather than size_t because len can become negative. The function prints the stack size first and then its contents, separating the elements with |
Examination
Stack_t stack; stack.size = 0; push(&stack, 3); printStack(&stack, printStackValue); push(&stack, 5); printStack(&stack, printStackValue); push(&stack, 7); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); _getch();
Let's also consider situations where there are usage errors. Underflow< 100; i++) { push(&stack, i); } _getch(); }
Void main() ( Stack_t stack; stack.size = 0; push(&stack, 3); pop(&stack); pop(&stack); _getch(); )
Void main() ( Stack_t stack; size_t i; stack.size = 0; for (i = 0; i Dynamically growing stack on an array A dynamically growing stack is used when the number of elements can be significant and is not known at the time of solving the problem.
Maximum size
The stack can be limited by a certain number or by the size of RAM.
The stack will consist of a pointer to the data, the size of the array (maximum), and the number of elements in the array. This number will also indicate the top.
Typedef struct Stack_tag ( T *data; size_t size; size_t top; ) Stack_t;
First, you will need some initial array size, let it be 10
#define INIT_SIZE 10
The algorithm works like this: we check whether the value of top has exceeded the value of size. If the value is exceeded, then we increase the size of the array. There are several options here for how to increase the array. You can add a number, you can multiply by some value. Which option is better depends on the specifics of the task. In our case, we will multiply the size by the number MULTIPLIER
First, functions for creating and deleting a stack and a few errors
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 Stack_t* createStack() ( Stack_t *out = NULL; out = malloc(sizeof(Stack_t)); if (out == NULL) ( exit(OUT_OF_MEMORY); ) out->size = INIT_SIZE; out->data = malloc(out->size * sizeof(T)); if (out->data == NULL) ( free(out); exit(OUT_OF_MEMORY); ) out- >top = 0; return out; ) void deleteStack(Stack_t **stack) ( free((*stack)->data); free(*stack); *stack = NULL; )
Everything is extremely simple and clear, there are no tricks. We create a stack with an initial length and reset the values.
Now let's write auxiliary function size changes.
Void resize(Stack_t *stack) ( stack->size *= MULTIPLIER; stack->data = realloc(stack->data, stack->size * sizeof(T)); if (stack->data == NULL) ( exit(STACK_OVERFLOW);
Here, note that if it was not possible to allocate enough memory, it will exit with STACK_OVERFLOW.
The push function checks whether we have gone beyond the bounds of the array. If yes, then increase its size
Void push(Stack_t *stack, T value) ( if (stack->top >= stack->size) ( resize(stack); ) stack->data = value; stack->top++; )
The pop and peek functions are similar to those used for a fixed-size array
T pop(Stack_t *stack) ( if (stack->top == 0) ( exit(STACK_UNDERFLOW); ) stack->top--; return stack->data; ) T peek(const Stack_t *stack) ( if ( stack->top<= 0) { exit(STACK_UNDERFLOW); } return stack->data; )
Let's check
Void main() ( int i; Stack_t *s = createStack(); for (i = 0; i< 300; i++) { push(s, i); } for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); } deleteStack(&s); _getch(); }
Let's write another function, implode, which reduces the array to the size equal to the number elements in the array. It can be used when it is already known that no more elements will be inserted, and memory can be partially freed.
Void implode(Stack_t *stack) ( stack->size = stack->top; stack->data = realloc(stack->data, stack->size * sizeof(T)); )
We can use in our case
For (i = 0; i< 300; i++) { push(s, i); } implode(s); for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); }
This single-threaded implementation of the stack uses few memory accesses, is quite simple and general-purpose, runs quickly and can be implemented, if necessary, in a few minutes. It is always used henceforth unless otherwise noted.
It has a drawback related to the method of increasing memory consumption. When multiplying by a factor of 2 (in our case), few memory accesses are required, but each subsequent increase can lead to an error, especially if the amount of memory in the system is small. If you use a more gentle method of allocating memory (for example, adding 10 each time), then the number of accesses will increase and the speed will drop. Today, there are usually no problems with memory size, and memory managers and garbage collectors (which are not in C) work quickly, so aggressive changes prevail (for example, the implementation of the entire standard library of the Java language).
Implementation of a stack on a singly linked list
What is a singly linked list? Briefly: a singly linked list consists of nodes, each of which contains useful information and a link to the next node. The last node refers to NULL.
No maximum and minimum sizes we will not have (although in general case May be). Each new element is created anew. First, let's define the node structure
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 typedef int T; typedef struct Node_tag ( T value; struct Node_tag *next; ) Node_t;
The function of inserting the first element is simple: create a new node. The next pointer is thrown to old node. Next, we transfer the pointer to the top of the stack to the newly created node. The top of the stack now points to the new node.
Void push(Node_t **head, T value) ( Node_t *tmp = malloc(sizeof(Node_t)); if (tmp == NULL) ( exit(STACK_OVERFLOW); ) tmp->next = *head; tmp->value = value; *head = tmp;
The pop function takes the first element (the one pointed to by the vertex), throws the pointer to the next element, and returns the first one. There are two options here - you can return a node or a value. If we return a value, we will have to delete the node inside the function
Node_t* pop1(Node_t **head) ( Node_t *out; if ((*head) == NULL) ( exit(STACK_UNDERFLOW); ) out = *head; *head = (*head)->next; return out; )
T pop2(Node_t **head) ( Node_t *out; T value; if (*head == NULL) ( exit(STACK_UNDERFLOW); ) out = *head; *head = (*head)->next; value = out ->value; free(out);
Now, instead of checking for the length of the array, a check for equality of the top of the stack to NULL is used everywhere.
Simple peek function
T peek(const Node_t* head) ( if (head == NULL) ( exit(STACK_UNDERFLOW); ) return head->value; )
Iteration is quite interesting. We just move from one node to another until we reach the end
Void printStack(const Node_t* head) ( printf("stack >"); while (head) ( printf("%d ", head->value); head = head->next; ) )
And one more problem - now you can’t just look at the stack size. You need to go from start to finish and count all the elements. For example, like this
Size_t getSize(const Node_t *head) ( size_t size = 0; while (head) ( size++; head = head->next; ) return size; )
Of course, you can store the size separately, you can wrap the stack with all the data in another structure, etc. Let's consider all this when studying the lists in more detail.
When mastering programming, sooner or later the question arises: " What is a stack?".
I think the most obvious way to explain this is an assembly language program (don't be alarmed) that simply adds data to the stack.
Stack is a data structure inherent in all programmable technology. Most often, the principle of operation of the stack is compared to a stack of plates: to take the second one from the top, you need to remove the top one. The stack is often called a magazine - by analogy with a magazine in a firearm (shooting will begin with the last loaded cartridge).
Why is all this needed?
You can hardly write a program that doesn't use functions (subroutines). When a function is called, the address is copied onto the stack to return after the execution of the given subroutine ends. At the end of its execution, the address is returned from the stack to the program counter and the program continues to be executed from the point after the function.
It is also necessary to place the registers that are used in this subroutine on the stack (in high-level languages, the compiler does this).
All of the above is typical for the so-called hardware stack. I hope you realize that this data structure (LIFO - last in, first out) is useful not only when working at a low level. Often there is a need to store data in this order (for example, a well-known algorithm for parsing arithmetic expressions is based on working with a stack), then programmers implement a software stack.
How it works?
Let's let's look at working with the stack using the example of MSP430 family controllers. I chose them only because I happened to have an environment installed to work with them.
In the MSP430, the stack is based on a pre-decremental design. Those. Before you write data to the stack, it decrements the address of the top of the stack (the top platter). There are also post-decremental/post-incremental (subtraction/adding of the top of the stack occurs after writing data) and pre-incremental (before writing, the address of the top is increased).
If the stack increases its address when writing data, it is said to be a stack growing upward; if it decreases, it is said to be growing downwards.
The SP register is responsible for storing the address of the top of the stack.
As you can see, the default vertex address is 0x0A00.
Consider this program:
PUSH #0123h ; Putting 0123h on the top of the stack (TOS); copy data from memory MOV.W &0x0A00, R5 MOV.W &0x09FE, R6 ; write two more numbers PUSH #9250h PUSH #0000h ; pop data from the stack POP R8 POP R9 POP R10
What does this program do?
With the PUSH command we push data 0123h onto the stack. It would seem that with this command we would write 0123h into memory at address 0x0A00, but we remember that our stack is pre-decremental. Therefore, first the address is decreased by 2 (0x0A00 - 2 = 0x09FE) and data is written to the cell with the resulting address.
This is what the memory originally looked like:
After executing the PUSH command (changes are highlighted in red):
So the data has been recorded.
Let's check if this is true by executing two transfer commands (mov). First, we will receive data from cell 0x0A00 and write it to register R5, and then write data from cell 0x09FE to register R6.
After this, the registers will contain the following data:
When executing POP commands, the top of the stack will be incremented by 2 with each command, and the data in registers R8-10 will be 0x0000, 0x9250 and 0x0123, respectively.
As more data is added, the memory (which still contains the data popped from the stack) will be filled with new values.
You can illustrate working with a stack like this (from left to right):
Initially, the stack address was 0x0A00, 0000 was stored in it. When PUSH was executed, the cell below (with address 0x09FE) became the top of the stack and data was written to it. With each next command the top is lower in memory.
When executing the POP command, the picture is reversed.
I look forward to your questions in the comments.
The memory used by programs consists of several parts − segments:
code segment(or "text segment") where the compiled program is located. The code segment is usually read-only;
bss segment(or "uninitialized data segment"), where global and zero-initialized values are stored;
data segment(or "initialized data segment"), where initialized global and static variables are stored;
Toteaching(heap), from where dynamic variables are allocated;
call stack, where local variables and other information related to functions are stored.
In this tutorial we'll only look at the heap and stack, since that's where all the fun happens.
Heap
Heap segment(or simply " a bunch") keeps track of memory used for dynamic allocation. We've already talked a little about the heap in .
In C++, when using the new operator to select dynamic memory, this memory is allocated in the heap segment of the application itself.
int *ptr = new int; // ptr allocates 4 bytes from the heap int *array = new int; // array allocates 40 bytes from the heap
The address of the allocated memory is passed back by the new operator and can then be stored in . About the storage and allocation mechanism free memory We have nothing to worry about now. However, it is worth knowing that sequential memory requests do not always result in the allocation of sequential memory addresses!
int *ptr1 = new int; int *ptr2 = new int; // ptr1 and ptr2 may not have consecutive addresses
When a dynamically allocated variable is deleted, the memory is returned back to the heap and can then be reassigned (based on subsequent requests). Remember that deleting a pointer does not delete the variable, it simply causes the memory at that address to be returned back to the operating system.
The heap has its advantages and disadvantages:
Memory allocation on the heap is comparatively slow.
The allocated memory remains allocated until it is freed (beware of memory leaks) or until the application terminates (at which point the OS must reclaim the memory).
Dynamically allocated memory is accessed only through a pointer. Dereferencing a pointer is slower than accessing a variable directly.
Since the heap is a large reservoir of memory, it is used to allocate large , or classes.
Call stack
Call stack(or simply " stack") has a much more interesting role. The call stack tracks all active functions (those that have been called but not yet completed) from the beginning of the program to the current point of execution, and handles the allocation of all function parameters and local variables.
The call stack is implemented as a Stack data structure. So before we talk about how a call stack works, we need to understand what a “Stack” is as a data structure.
Stack Data Structure
Data structure is a mechanism in programming for organizing data so it can be used efficiently. You've already seen several types of data structures, such as arrays and structs. They provide mechanisms for efficiently storing and accessing data. There are many more additional data structures that are commonly used in programming, some of which are implemented in the C++ standard library, and Stack is one of them.
Consider a stack of plates on a table. Since each plate is heavy and they are stacked (on top of each other), you can only do one of the following three things:
Look at the surface of the top plate.
Take the top plate from the stack (thus revealing the next one, which is below - if there is one at all).
Place a new plate on top of the stack (hiding the topmost plate underneath, if there was one).
In computer programming, a stack is a container-like data structure that contains several variables (similar to an array). However, while an array allows you to access and change elements in any order (called " random access"), then the stack is more limited. The operations that can be performed on the stack correspond to the three listed above. On the stack you can:
Look at the top element in the stack (use the function top() or peek() ).
Pull out the top element of the stack (use the function pop() ).
Add a new element to the top of the stack (use the function push() ).
Stack is a structure like LIFO(Last In, First Out - last to come, first to leave). The last element pushed to the top of the stack will be the first one to come off the stack. If you place a new plate on top of a stack of other plates, it will be the first one you pick up. As elements are pushed onto the stack, the stack grows; as elements are removed from the stack, the stack shrinks.
For example, consider short sequence showing how adding and removing on the stack works:
Stack: empty
Push 1
Stack: 1
Push 2
Stack: 1 2
Push 3
Stack: 1 2 3
Push 4
Stack: 1 2 3 4
Pop
Stack: 1 2 3
Pop
Stack: 1 2
Pop
Stack: 1
A stack of plates is a pretty good analogy for how a stack works, but there is a better analogy. For example, consider several mailboxes that are located on top of each other. Each mailbox can only contain one item, and all mailboxes are initially empty. Additionally, each mailbox is nailed to the bottom of the mailbox, so the number of mailboxes cannot be changed. If we can't change the number of mailboxes, then how do we get stack-like behavior?
First, we use a sticker to indicate where the lowest empty mailbox is. At the beginning, this will be the first mailbox that is on the floor. When we add an item to our mailbox stack, we will place that item in the mailbox that the sticker will be on (i.e. the very first empty mailbox on the floor), and then move the sticker one mailbox higher. When we pop an element from the stack, we move the sticker one letterbox down and remove the element from mailbox. Everything below the marker is on the stack. Everything that is in the box with a sticker and above is not in the stack.
Call stack segment
The call stack segment contains memory used for the call stack. When the application starts, the main() function is pushed onto the call stack operating system. Then the program begins its execution.
When a program encounters a function call, the function is pushed onto the call stack. When a function completes execution, it is removed from the call stack. This way, by looking at the functions added to the stack, we can see all the functions that were called up to the current point of execution.
Our mailbox analogy is really how the call stack works. The call stack has a fixed number of memory addresses (fixed size). Mailboxes are memory addresses, and the "items" we add and pop on the stack are called frames(or more " personnel") stack. The stack frame keeps track of all the data associated with a single function call. "Sticker" is a register ( small part memory in the CPU), which is stack pointer. The stack pointer keeps track of where the top of the call stack is located.
The only difference between the actual call stack and our hypothetical mailbox stack is that when we pop an element from the call stack, we don't have to clear memory (i.e. pop the entire contents of the mailbox). We can simply leave this memory for the next element, which will overwrite it. Since the stack pointer will be below this memory address, then, as we already know, this memory location will not be on the stack.
Call stack in practice
Let's take a closer look at how the call stack works. Below is sequence of steps performed when calling a function:
The program encounters a function call.
A stack frame is created and placed on the stack, it consists of:
The address of the instruction that is located behind the function call (the so-called " return address"). This is how the processor remembers where to return after executing a function.
Function arguments.
Memory for local variables.
Saved copies of all registers modified by the function, which will need to be restored after the function completes its execution.
The processor moves to the start point of the function.
The instructions inside the function begin to execute.
After the functions are completed, they are executed next steps :
Registers are restored from the call stack.
The stack frame is popped from the stack. The memory of all local variables and arguments is freed.
The return value is processed.
The CPU resumes executing the code (based on the return address).
Return values can be processed different ways, depending on the computer architecture. Some architectures consider the return value to be part of the stack frame. Others use processor registers.
Knowing all the details of how the call stack works is not that important. However, understanding that functions are added to the stack when called and removed from the stack when called gives the basics needed to understand recursion, as well as some other concepts that are useful in .
Example call stack
Consider the following code snippet:
The call stack of this program looks like this:
boo() (including parameter b)
main()
Stack Overflow
The stack has a limited size and therefore can only hold a limited amount of information. IN Windows size The default stack size is 1 MB. On some other Unix systems this size can reach 8 MB. If a program tries to push too much information onto the stack, it will result in a stack overflow. Stack Overflow(stack overflow) occurs when a memory request occurs when all the stack memory has already been allocated - in this case, all allocation requests will begin to flow (overflow) to other memory sections.
A stack overflow is the result of adding too many variables to the stack and/or creating too many large quantity nested function calls (for example, where function A calls function B, which in turn calls function C, which calls function D, etc., etc.). Stack overflow usually causes a program to crash.
For example:
int main() ( int stack; return 0; )
int main() int stack [ 100000000 ] ; return 0 ; |
This program is trying to add a huge array to the call stack. Since the stack size is not enough to process such an array, its addition goes to other parts of memory that the program cannot use. Therefore, we get a failure.
Here's another program that will cause a stack overflow, but for a different reason:
void boo() ( boo(); ) int main() ( boo(); return 0; )
