Stack -- one of two common linear structures of linear structure

Origin of stack

In the previous article, we introduced the characteristics of two linear storage structures , And practice the actual combat between two different storage structures to achieve the same function , And realized the similarities and differences between them , Finally, we get an inspiration , In a linear storage structure , Whether its storage form is continuous or discontinuous , They are all connected in a certain way from beginning to end , In this way, it may be that the storage units are close to each other , It may also be a pointer between storage units , They all show it in a linear way , This well simulates the physical structure of memory , And formal this special structure , Raises questions about the relationship between storage units The order Thinking . Through different production , array , The order produced by the combination , This paper summarizes two special storage structures which follow different array operation order on the basis of linear structure , One of them is the stack to be introduced today

Definition and example of stack

Definition of stack ：
Internet ： Stack （Stack） yes n Elements a1,a2,…an, Finite sequence of components , Write it down as S =(a1,a2,…,an), And you can only insert and delete elements at one end ,n=0 It is called empty stack .
This is the answer I found on the Internet , I don't think it's very easy to understand and he generalizes concepts beyond the essence of stack
Summarize yourself ： One can achieve “ First in, then out ” Storage structure of
Of course, I have other understandings about stack , But now is not the time to come clean

give an example
Stacks are like boxes , Badminton bucket . You can't take out the things below without taking out the things above , The first thing you put in is automatically at the bottom

Stack classification

Stack can be classified into static stack and dynamic stack , Static and dynamic, if you read my previous blog, you should understand it very well
To put it bluntly, it is the way of memory allocation, right .

Stack algorithm

There are two main types , One is stack pressing ( No, ma'am ), One is out of the stack .
Pressing stack ： Similar to the fragrant badminton bucket
Out of the stack ： It's like taking something out of a badminton bucket

actual combat ----- Stack （ It's time to pull your ass with a knife ）

Actual target ： Show the structure of dynamic stack , The process of getting out and into the stack , The process of traversing the stack

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct Node
{
    
	int data;
	struct Node* pNext;
}*pnode,node;
typedef struct stack // Stack   This is where we define the storage unit of the stack we need 
{
    
	pnode ptop;
	pnode pbottom;
}stack,*pstack;
// Function declaration 
void initstack(pstack ps);
void pushstack(pstack ps, int val);
void traverse(pstack ps);
bool pop(pstack ps, int* pval);
bool empty(pstack ps);// Determine whether it is null 
void clear(pstack ps);
int main(void)
{
    
	int val;
	stack s;// Equivalent to struct stack 
	initstack(&s);// Aim to create an empty stack 
	pushstack(&s,1);// Pressing stack 
	pushstack(&s,2);
	pushstack(&s, 99);
	pushstack(&s, 7);
	pushstack(&s, 6);
	pushstack(&s, 2);
	traverse(&s);// Traverse 

	
	if (pop(&s, &val))
	{
    
		printf(" Stack out successfully , The element out of the stack is %d\n", val);
	}
	else
	{
    
		printf(" Stack out failed ");
	}
	traverse(&s);// Traverse 

	clear(&s);
	traverse(&s);// Traverse 
	return 0;
}
void initstack(pstack ps)
{
    
	ps->ptop=(pnode)malloc(sizeof(Node));
	if (NULL == ps->ptop)
	{
    
		printf(" Dynamic memory allocation failed ");
		exit(-1);
	}
	else
	{
    
		ps->pbottom = ps->ptop;
		ps->ptop->pNext = NULL;// Equivalent to ps->pbotom->pNext = NULL  This node is the head node , therefore pNext be free 
	}
	return;
}
void pushstack(pstack ps, int val)
{
    
	pnode pnew = (pnode)malloc(sizeof(node));
	pnew->data = val;
	pnew->pNext = ps->ptop;//ps->ptop
	ps->ptop = pnew;
	return;
}
void traverse(pstack ps)
{
    
	pnode p=ps->ptop;
	while (ps->ptop!=ps->pbottom)
	{
    
		printf("%d ",ps->ptop->data);
		ps->ptop = ps->ptop->pNext;
	}
	ps->ptop = p;
	return;
}
// hold ps Point to the stack to stack once , And store the elements out of the stack into pval In the variable pointed to by the formal parameter ,
														// If the stack fails, return false Successfully put the stack back true
bool empty(pstack ps)
{
    
	if (ps->ptop == ps->pbottom)
		return true;
	else
		return false;
}
bool pop(pstack ps, int *pval)
{
    
	if (empty(ps))//ps What it stores is s The address of 
	{
    
		return false;
	}
	else
	{
    
		pnode f = ps->ptop;
		*pval = ps->ptop->data;
		ps->ptop = ps->ptop->pNext;
		free(f);
		f = NULL;
		return true;
	}
}
//clear Empty 
void clear(pstack ps)
{
    
	if (empty(ps))
		return;
	else
	{
    
		pnode p = ps->ptop;
		pnode q = NULL;
		while (p!=ps->pbottom)
		{
    
			q = p->pNext;
			free(p);
			p = q;
		}
		p = NULL;
		q = NULL;
		ps->ptop = ps->pbottom;
	}

}

Summary of stack

See the actual demonstration of the whole stack , No man found , Stack is actually a linked list with some functions cut off . Why do you want to cut some functions to form a stack ？ This is actually the reason for better operation of logarithm sentences , The linked list will have some disadvantages in this province , Too developed is not a good thing . Everything has two sides , Let's talk about this later .