This is the first day of my participation in the Gwen Challenge in November. Check out the details: the last Gwen Challenge in 2021
Preface:
Last time we looked at a linked list inside a linear list, and today we’re going to look at a stack, which, in the official term, is a data structure, a special linear list that can only be inserted and deleted at one end. It stores data on a LIFO (LIFO) or LIFO (LIFO) basis, in which the first data is pushed to the bottom of the stack and the last data is pushed to the top of the stack. The stack has the function of memory, and the operation of inserting and deleting the stack does not need to change the bottom pointer of the stack.
Once a day, no limits to happiness, hahaha
1. What is stack and understand logic
So let’s learn the logic of the stack, and logic is a very important thing in programming, as long as we know the logic, and then we know the language, basically we can use two diagrams to get you to understand the logic of the stack.
Figure 1 is a logical diagram, it’s abstract, it’s easy to understand, remember last in, first out, or first in, last out, if you find these two sentences, they are inversely related to queues, so let’s use life to remember this logic, figure 2.
This figure is the combination of life a logic diagram, a dead end one by one, finally only is last in first out, advanced to go out in the end, you can start the imagination to think of it, and logic, such as those in the life can facilitate our memory, bloggers who want to have, handguns, we used to use old flashlight batteries, As well as our childhood to play the press, just a few children, one by one to press the bottom of the child, we imagine that picture, can enhance our stack of logic. 😂 😂 😂 😂
2. Know the code. Know our tools
2.1 Build stack we need to understand the code, sum up
The flow chart looks like this:
We need to know some code and what it means
Typepedef struct{DataType data[MAXSIZE]; #define DataType data[MAXSIZE]; int top; }SeqStack;}SeqStack;}SeqStack; (SeqStack*)malloc(sizeof(SeqStack)); We used this in linked lists, dividing up memory. Int Push_SeqStack(SeqStack* s, DataType x); Int Pop_SeqStack(SeqStack* s, DataType* x){// Pop_SeqStack(SeqStack* s, DataType* x){// Pop_SeqStack(SeqStack* s, DataType* x)Copy the code2.2 Initializing the sequential stack
Initialize the stack sequence is to stack, memory space, and then save the value in the array, talking people is: (a structure pointer to a structure, and this structure has an array and a plastic variable, is an array subscript, then every time deposit value the plastic variable since, the stack is plastic variable the decrement)
typedef struct{ DataType data[MAXSIZE]; int top; }SeqStack; SeqStack* Init_SeqStack(){// Stack initializes SeqStack* s; s = (SeqStack*)malloc(sizeof(SeqStack)); // Allocate memory space if(! Printf (" not enough space \n"); return NULL; }else{ s->top = -1; // return s; Empty_SeqStack(SeqStack* s){if(s->top == -1) {return 1; else return 0; }Copy the code2.3 Loading and unloading operations
Int Push_SeqStack(SeqStack* s, DataType x){int Push_SeqStack(SeqStack* s, DataType x){if(s->top == maxsize-1) The reason why we subtract one is because we start the stack at 0 and we end the stack at -1 return 0; Else {s->top++; S ->data[s->top] = x; // push our value to the stack return 1; Int Pop_SeqStack(SeqStack* s, DataType* x){Pop_SeqStack(SeqStack* s, DataType* x){ If (Empty_SeqStack(s)) return 0; Else {*x = s->data[s->top]; // set the top of the stack to s->top--; // Return 1; }// store the top element in *x, return}Copy the code2.4 Effect demonstration, and the overall code
So the sequential stack looks like this, and I’m going to put the whole code down here, so you can run it
#include <stdio.h> #include <malloc.h> #define DataType int #define MAXSIZE 10 typedef struct{ DataType data[MAXSIZE]; int top; }SeqStack; SeqStack* Init_SeqStack(){// Stack initializes SeqStack* s; s = (SeqStack*)malloc(sizeof(SeqStack)); if(! S){printf(" insufficient space \n"); return NULL; }else{ s->top = -1; return s; }} int Empty_SeqStack(SeqStack* s){if(s->top == -1) return 1; else return 0; } int Push_SeqStack(SeqStack* s, DataType x){return 0; Else {s->top++; s->data[s->top] = x; return 1; If (Empty_SeqStack(s)) return 0; if(Empty_SeqStack(s)) return 0; Else {*x = s->data[s->top]; s->top--; return 1; } int Print_SeqStack(SeqStack* s){int I; Printf (" element in current stack :\n"); for(i = s->top; i >= 0; i--) printf("%3d", s->data[i]); printf("\n"); return 0; } int main(){ SeqStack* L; Int n, num, m; int i; L = Init_SeqStack(); // Initialize stack printf(" initialize done \n"); Printf (" empty stack: %d\n", Empty_SeqStack(L)); Printf (" Please enter the number of elements (not more than %d) : \n",MAXSIZE); // MAXSIZE scanf("%d", &n); Printf (" Please enter %d elements to be pushed: \n", n); for(i = 0; i < n; i++){ scanf("%d", &num); Push_SeqStack(L, num); Push_SeqStack(L, num); } Print_SeqStack(L); Printf (" Please enter the number of elements to be removed from the stack (no more than %d) : \n", n); scanf("%d", &n); Printf (" stack %d elements: \n", n); for(i = 0; i < n; i++){ Pop_SeqStack(L, &m); Printf ("%3d", m); printf("%3d", m); M} printf("\n"); return 0; }Copy the codeConclusion:
The sequential stack is relatively simple, we can simply understand it as a one-dimensional array with subscripts, and the subscripts can not be arbitrarily jumped to the last position, the subscripts will increase, the stack will decrease, stack is a good data structure, it is also used in a lot of algorithms. For example, the classic Hannott tower problem can be solved by stack, which is also used more in recursion. This is generally the understanding of bloggers. If there is any mistake, I hope you can timely advise.
Data structure, linear linked list (inside volume)
