04_ Stack

Stack

What is stack?

Why must it be the end of the sequence table , Header of linked list ：

The header of the linked list can be accessed directly , The time complexity is O（1）

It is essentially a linear table （ Access to linear tables with certain restrictions ）
principle ： Last in, first out , Later, you need to serve first
Stack 2 A design ：

• Sequence table design , Called sequential stack
• Chain design , It is called chain stack

1 Indefinite length sequential stack

Mode one ：

The stack can only be inserted and deleted at one end , The end where the insertion and deletion are performed is called To the top of the stack , The other end is called At the bottom of the stack （ The top of the stack is the end of the sequence table ）

top Yes 2 Layer meaning ：

• 1： Number of currently saved data ; As shown in the figure above, the number of valid data is 5 individual
• 2： The subscript of the next data to insert ; As shown in the figure above, the next data should be inserted into 5 Subscript no.

// Stack ： Last in, first out , Later, you need to serve first （ Access restricted linear table ）
// Stacks are divided into sequential stacks , Chain stack 
// This document is an indefinite length sequence stack , It can automatically expand capacity 
// The end of the stack that can only be inserted and deleted at one end is called the top of the stack , The other end is called the bottom of the stack 
// The top of the sequence stack is at the end , Because the time complexity of entering and leaving the stack is O（1)

//  Indefinite length sequential stack （ Access to linear tables with certain restrictions ）
typedef struct Stack
{
    
	int* base; // Point to dynamic memory 
	int stackSize; // Total stack size （ Total number of cells ）
	int top; // Top pointer of stack ; There is no need to design the pointer at the top of the stack of the sequence table as a pointer , Subscripts are more practical 
	       // The subscript that can store data at present 
}Stack,*PStack;


// initialization （ similar C++ Middle constructor ）
void InitStack(PStack ps);

// Full sentence 
bool IsFull(PStack ps);

// Stack expansion function , Capacity expansion 2 times 
void Inc(PStack ps);


// Put data into the stack （ Into the stack, ）
bool Push(PStack ps, int val);

// Get the value of the top of the stack element , But don't delete 
//int GetTop(PStack ps);// There's something wrong with the design 
bool GetTop(PStack ps,int* rtval);//rtval: Output parameters 
// int *rtval  usage ： Define a variable , Send the address in , Function internal dereference , The value of the parameter can be brought out 
//  Similar to  int a ;scanf_s("%d",&a);

// Get the value of the top of the stack element , And delete 
//int Pop(PStack ps);
bool Pop(PStack ps, int* rtval);

// Sentenced to empty 
bool IsEmpty(PStack ps);

// Get the number of stack valid data 
int GetLength(PStack ps);

// Clear all data 
void Clear(PStack ps);
// The destruction 
void Destory(PStack ps);

Mode two ：

data structure ：

Initialization function ：

Empty stack ：

Destroy function ：

Get the number of data in the stack ：

Stack capacity ：

Stack empty ：

Stack full :

Stack expansion ：

Push ：

Take the top element of the stack ：

Out of the stack ：

Merge the elements at the top of the stack and out of the stack ：

Non recursive implementation of fast scheduling ：

2 Chain stack

// Use the single linked list of the leading node to realize 
// To the top of the stack ： Push and pull , Stack top in header （ The time complexity of entering and leaving the stack is O（1））,
//  The top of the stack is not fixed at that end , Adjust according to the structural characteristics of the current linked list 


typedef struct LSNode
{
    
	int data;
	struct LSNode* next;
}LSNode,*PLStack;// The node of the chain stack , Because the top of the stack is at the first data node , So no need top The pointer 


// initialization 
void InitLStack(PLStack ps);

// Full sentence 
bool IsFull(PLStack ps);

// Stack expansion function , Capacity expansion 2 times 
void Inc(PLStack ps);


// Put data into the stack （ Into the stack, ）
bool Push(PLStack ps, int val);

// Get the value of the top of the stack element , But don't delete 
bool GetTop(PLStack ps, int* rtval);//rtval: Output parameters 


// Get the value of the top of the stack element , And delete 
bool Pop(PLStack ps, int* rtval);

// Sentenced to empty 
bool IsEmpty(PLStack ps);

// Get the number of stack valid data 
int GetLength(PLStack ps);

// Clear all data 
void Clear(PLStack ps);
// The destruction 
void Destory(PLStack ps);