Hi, I'm a second year student at a technical university. After skipping a few pairs of programming for health reasons, I was confronted with misunderstandings such as “Stack” and “Queue”. Through trial and error, a few days later, it finally dawned on me what it was and what it was eating 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 the second part, which will touch on such a thing as “Queue”

Theory

On Wikipedia, the definition of a stack is:

Stack (English stack - stack; stack is read) - an abstract data type, which is a list of elements organized on the principle of LIFO (English last in - first out, "last came - first out").

Therefore, the first thing I would like to emphasize is the presentation of the stack in the form of things from life. First I came to the interpretation in the form of a pile of books, where the top book is the top.

So, what does the stack consist of?
')
A 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 for the next element.
Complicated? Do not worry, let's understand.

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 pointer * next stores the address of the next cell. The * TOP pointer points to the top of the stack, that is, stores its address.

With the theory finished, let's move on to practice.

Practice

First we need to create a structure that will be our “cell”

struct comp { //   comp(  component) int Data; //- (  ,     int key; char Data; -    - ) comp *next;//  comp    }; 

Beginners may not understand why our pointer is of the comp type, or rather, the pointer of the comp structure type. I will explain that in order for the * next pointer to store the comp structure, it needs to designate the type of this structure. In other words, specify what the pointer will hold.

After we have set the "Cell", we proceed to the creation of functions.

Functions

The function of creating a "stack" / add an item to the "stack"

When adding an item, we have two situations:

• The stack is empty and you need to create it.
• The stack is already there and you just need to add a new element to it.

 void s_push(comp **top, int D) { //  void(  )              comp *q; //   q   comp.         q = new comp(); //     q->Data = D; //    Data  if (top == NULL) { //  ,     *top = q; //     } else //    { q->next = *top; //    ,  .      . *top = q; //,       } } 

We will analyze a little bit more in detail.
First, why the function takes ** top, that is, a pointer to a pointer, in order for you to be the most understandable, I will leave this issue for later. Secondly, let's talk more about q-> next = * top and what it means -> .

-> means that roughly speaking, we go into our structure and take out an element of this structure from there. In the q-> next = * top line, we get 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 are connecting, from the new element to the top of the stack. It's nothing complicated, everything is like with books. We put a new book exactly on the top of the stack, that is, we link from the new book to the top of the stack of books. After this, a new book automatically becomes a vertex, since the stack is not a stack of books, we need to indicate that the new element is a vertex, for this it is written: * top = q; .

The function of removing an item from the "stack" by data

This function will remove an item from the stack if the Data number of the cell (q-> Data) is equal to the number we denote.

There may be such options:

• The cell we need to remove is the top of the stack
• The cell that we need to delete is at the end, or between two cells

 void s_delete_key(comp **top, int N) {//    top      comp *q = *top; //   comp  ()     comp *prev = NULL;//    ,      while (q != NULL) {//  q  ,      ,        if (q->Data == N) {// Data   ,     if (q == *top) {//    ,   ,     -  *top = q->next;//     free(q);//  q->Data = NULL; //         ,           NULL ,   "  "   "-2738568384"  ,    . q->next = NULL; } else//         { prev->next = q->next;//       free(q);//  q->Data = NULL;//  q->next = NULL; } }//  Data    ,     prev = q; //     q = q->next;//  q    } } 

The q pointer in this case plays the same role as the pointer in the notebook, it runs around the entire stack, until it becomes NULL ( while (q! = NULL) ), in other words, until the stack ends.

For a better understanding of the removal of an element, let us draw analogies with the already familiar stack of books. If we need to remove the book from above, we remove it, and the book under it becomes the top. Here is the same thing, only at the beginning we must determine that the next element will become a vertex * top = q-> next; and only then remove the free (q) element ;

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 or on the table. As we already understood, the book we have is a cell, and the table turns out to be NULL, that is, there is no next element. It turns out the same way as with books, we denote that the previous cell will be associated with the subsequent prev-> next = q-> next; it is worth noting that prev-> next can be either a cell or zero if q-> next = NULL , that is, there is no cell (the book will lie on the table), then we clear the cell free (q) .

It is also worth noting that if you do not make this connection, the section of cells that lies after the deleted cell will become inaccessible, since the connection that connects one cell to another is lost, and this section is simply lost in memory.

Stack data display function

The simplest feature:

 void s_print(comp *top) { //     comp *q = top; // q   while (q) { // q   (while(q)  while(q != NULL)) printf_s("%i", q->Data);//      q = q->next;//     q   () } } 

Here I think everything is clear, I want to say only that q should be perceived as a slider, it runs through all the cells from the top, where we installed it at the beginning: * q = top; until the last item.

Main function

Well, we wrote down the main functions for working with the stack, we call it.
Let's see the code:

 void main() { comp *top = NULL; //      ,   ,    NULL //     1  5    s_push(&top, 1); s_push(&top, 2); s_push(&top, 3); s_push(&top, 4); s_push(&top, 5); //        54321 s_print(top);// s_delete_key(&top, 4); //  4,    5321 printf_s("\n");//    s_print(top);// system("pause");//   } 

Let's return to why we passed a pointer to the vertex pointer to the function. The fact is that if we entered only the pointer to the vertex in the function, then the “Stack” was created and changed only inside the function, in the main function the vertex would be as it was and would remain NULL. Passing a pointer to a pointer, we change the top of the top in the main function. It turns out if the function changes the stack, you need to pass the vertex to it with a pointer to a pointer, so we had in the function s_push, s_delete_key. In the s_print function, the “stack” should not be changed, so we simply pass a pointer to the vertex.
Instead of numbers 1,2,3,4,5, you can also use variables of type int.

Conclusion

Full program code:

 #include <stdio.h>; #include <iostream>; struct comp { //   comp int Data; //  (  ,     int key; char Data;      ) comp *next;//  comp    }; void s_push(comp **top, int D) { //  void(  )              comp *q; //   q,     .         q = new comp(); //     q->Data = D; // D  Data  if (top == NULL) { //  ,    *top = q; //     } else //    { q->next = *top; //    ,  .      . *top = q; //,       } } void s_delete_key(comp **top, int N) {//    top      comp *q = *top; //   comp  ()     comp *prev = NULL;//    ,      while (q != NULL) {//  q  ,    ,        if (q->Data == N) {// Data   ,     if (q == *top) {//    ,   ,     -  *top = q->next;//     free(q);//  q->Data = NULL; //         ,           NULL ,   "  "   "-2738568384"  ,    . q->next = NULL; } else//         { prev->next = q->next;//       free(q);//  q->Data = NULL;//  q->next = NULL; } }//  Data    ,     prev = q; //     q = q->next;//  q    } } void s_print(comp *top) { //     comp *q = top; // q   while (q) { // q   (while(q)  while(q != NULL)) printf_s("%i", q->Data);//      q = q->next;//     q   () } } void main() { comp *top = NULL; //      ,   ,    NULL //     1  5    s_push(&top, 1); s_push(&top, 2); s_push(&top, 3); s_push(&top, 4); s_push(&top, 5); //        54321 s_print(top);// s_delete_key(&top, 4); //  4,    5321 printf_s("\n");//    s_print(top);// system("pause");//   } 

In conclusion, I would like to thank you for taking the time to my article, I really hope that this material has helped some novice programmers to understand what Stack is, how to use it, and in the future they will not have any more problems. Write in the comments your opinion, as well as how to improve my articles in the future. Thanks for attention.