preface:

In the last article, the blogger talked about sequential stack. Today, the blogger talked about chained stack. Chained stack is a data storage structure that can be realized by single linked list. The advantage of using chained stack is that it can overcome the low utilization of sequential stack space realized by array, However, additional pointer space needs to be allocated for each stack element to store the pointer field. What people say is: there is a stack top pointer pointing to a single linked list. The single linked list stores data, and the stack top pointer takes and puts data.

Once a day, happy mood

(the picture was taken by the blogger at home. In fact, there is a very interesting video that can't be uploaded. I have the opportunity to show it to netizens.)

1. Understand logic and know what chain stack is.

In fact, the chain stack is very similar to the single linked list. Entering the stack can be understood as the head insertion method of the single linked list. Leaving the stack can be understood as the single linked list output of the leading node, but its head node is our stack top, which is used for input and output. The chain stack is a little better than the sequential stack. It is more flexible than the sequential stack. It does not want to limit the size of the sequential stack. The chain stack does not need to limit the size. It is very flexible. Put a logic diagram:

(this figure shows the comparison between chain stack and sequential stack. The logic of chain stack is to use malloc to generate new nodes and then connect with next.)

2. After understanding the logic of chain stack, we should know the code

typedef struct node
{       
	int data;         //Data domain     
	struct node * next;     //Pointer field
}LinkStack; //Is the definition stack very similar to the linked list? You guessed right
 p=(LinkStack *)malloc(sizeof(LinkStack));//Allocate space
 LinkStack *top //Stack top pointer
 p->data=x;         //Set the value of the new node
 p->next=top;       //Insert new element into stack
 p=top;  //Point to the top of the deleted stack
  *e =p->data;//Returns the value of our stack 
   top=top->next; //Modify stack top pointer
  free(p);//Release nodes that have been out of the stack 

The above is the core code of the whole chain stack. As long as we understand these codes, we will learn half, the other half is logic, the program is code + algorithm, and the algorithm is our logical thinking.

3. The chain stack judges that the stack is empty and obtains the top of the stack

int StackEmpty(LinkStack *top)// Judge whether the chain stack is empty 
{
       return (top?0:1) ;//Stack empty return 1
}
int GetTop(LinkStack *top)//Gets the value of the top of the stack 
{
    if(!top)//Judge whether the stack top is empty 
    {
    printf("/n The linked list is empty!");
    return 0;       
     }
    return top->data;//Returns the value at the top of the stack 
}

Our formal parameters are stack top pointers. If our stack is empty, it will return 1, if there is a stack top, it will return 0, and our method to obtain the value of the stack top is to directly use the top value

3. Simple operation of chain stack

In fact, it's easy to enter the stack. As long as you have seen the blogger's linked list before, the blogger has written out the simple logical steps. You can look at the picture and understand it. It's a little abstract and time is limited to understand it.

LinkStack *Push(LinkStack *top,int x)//Push 
{
 
    LinkStack *p;
    p=(LinkStack *)malloc(sizeof(LinkStack));//Allocate space
    p->data=x;         //Set the value of the new node
    p->next=top;       //Insert new element into stack
    top=p;             //Set the new element to the top of the stack
    return top;
}

Bloggers use the main function to use the loop to stack one by one. Of course, you can also change it. For example, pass the array and use the loop to stack in the implementation function. In fact, it's almost the same

4. Simple out of stack operation of chain stack

The output of the stack is very similar to the output of the head node of the single linked list. Really, as long as we know the linked list, the stack is really not difficult

LinkStack *Pop(LinkStack *top,int *e)//Out of stack
{
    LinkStack *p;
    if(!top)
    {
    printf("/n The chain stack is empty!");
    return NULL;
    }  //Determine whether it is an empty stack n
       p=top;  //Point to the top of the deleted stack
       *e =p->data;//Returns the value of our stack 
       top=top->next; //Modify stack top pointer
       free(p);//Release nodes that have been out of the stack 
       return top;
 
}

5. Overall demonstration effect and overall code of chain stack

#include <stdio.h>
#include <malloc.h>
typedef struct node
{       
	int data;         //Data domain     
	struct node * next;     //Pointer field
}LinkStack;   
int StackEmpty(LinkStack *top)// Judge whether the chain stack is empty 
{
       return (top?0:1) ;//Stack empty return 1
}
int GetTop(LinkStack *top)//Gets the value of the top of the stack 
{
    if(!top)//Judge whether the stack top is empty 
    {
    printf("/n The linked list is empty!");
    return 0;       
     }
    return top->data;//Returns the value at the top of the stack 
}

LinkStack *Push(LinkStack *top,int x)//Push 
{
 
    LinkStack *p;
    p=(LinkStack *)malloc(sizeof(LinkStack));//Allocate space
    p->data=x;         //Set the value of the new node
    p->next=top;       //Insert new element into stack
    top=p;             //Set the new element to the top of the stack
    return top;
 
}

LinkStack *Pop(LinkStack *top,int *e)//Out of stack
{
    LinkStack *p;
    if(!top)
    {
    printf("/n The chain stack is empty!");
    return NULL;
    }  //Determine whether it is an empty stack n
       p=top;  //Point to the top of the deleted stack
       *e =p->data;//Returns the value of our stack 
       top=top->next; //Modify stack top pointer
       free(p);//Release nodes that have been out of the stack 
       return top;
 
}
int main(){
    LinkStack *L;
    int n, num, m;
    int i;
    if(StackEmpty(L))//Determine whether the stack is empty 
    {
    printf("Stack is empty\n");
	}
	else{
	printf("Initialization completed, with stack top\n");	
	}
    printf("Please enter the number of stack elements:\n");
    scanf("%d", &n);
    printf("Please enter the to stack%d Elements:\n", n);
    for(i = 0; i < n; i++){
        scanf("%d", &num);
     	L=Push(L,num);
    }  
    printf("Stack top value:%d \n",GetTop(L));
    printf("Please enter the number of elements to stack (no more than)%d Item (s):\n", n);
    scanf("%d", &n);
    printf("Stack in turn%d Elements:\n", n);
    for(i = 0; i < n; i++){
        L=Pop(L, &m);
    	printf("%3d",m);
    }
	return 0;
}

Summary:

Basically, the blogger has finished talking about the stack. In fact, the stack needs to be associated with the knowledge learned before before it can be learned very clearly. In the blogger's own words, the sequential stack is an array with subscripts. The subscripts go all the way back, and the output goes forward. The subscript is the top of the stack, and the chain stack is a single linked list of pointers to the leading nodes, Entering the stack is equivalent to a single linked list. The linked list is established by using the header insertion method. When the chain stack comes out of the stack, the single linked list is generated by using the header node, which is equivalent to the top of our stack. That's it. The next article is our queue. Remember to pay attention to the children's shoes you want to see. It's not easy to create. I hope you can praise, comment and collect them. Thank you. Don't spray if you don't like it.