What is stack?

Stack: a linear table that allows insertion or deletion operations only at one end (limited to the end of the table).
Therefore, for the stack, there is a distinction between the top and bottom of the stack. The details are as follows:

Therefore, when using stack storage, there is a law of first in and last out.
When we store the elements into the stack in turn, when the first stored element is taken out (out of the stack), we need to wait until all the elements pressed on it are taken out.

Stack status

A stack has four different states

• Empty stack
• Full stack
• Stack entry (stack entry, stack pressing push)
• Out of stack (pop)

This corresponds to the operation API s of the most basic stacks.

ADT design

For stack programming, we mainly write these operations on the stack

Stack method name	operation
initStack(*S)	Initialize the stack and create an empty stack
destoryStack(*S)	If stack S exists, destroy the stack
is_Full(S)	Is the stack full
clearStack(*S)	Empty the elements in the stack
getTop(S,*e)	If stack S is not empty, use e to obtain the top element of stack
push(*S,e)	If stack S exists, push element e into stack
pop(*S,*e)	Delete the top element of stack S and return the deleted value with e
stackLength(S)	Get the length of the stack

C language implements two types of stack

Sequential stack

Sequential stack uses continuous memory space (array) to store the elements in the stack and realize the functional characteristics of the stack.
Advantages of using sequential stack:

• Simple structure, continuous storage address and easy operation

Disadvantages:

• Fixed memory space and poor scalability
• And it needs to occupy the whole block of memory

code implementation

# include<stdio.h>
# include<stdlib.h>

# define MaxSize 50 		//  Defines the depth of the stack
typedef int ElemType;	// Defines the type of the stack element

// Structure structure of structure stack
typedef struct {
	ElemType data[MaxSize];		// Construct stack memory structure for storage
	int top;	// Define stack top pointer
} SeqStack;

// Initialization stack
SeqStack* initStack(SeqStack* s){
	// The structure of the stack has been constructed using the structure above
	// Here we need to open up the memory for the defined stack structure
	s = (SeqStack*)malloc(sizeof(SeqStack));
	// Set the stack top pointer to the bottom of the stack
	// Here is stored according to the array, so the beginning of the stack starts from 0
	// So the initialization here should be set to - 1
	s->top = -1;
	return s;
}

// Determine whether the stack is empty
int is_Full(s){
	if(s->top == MaxSize-1){
		return 0;	
	}
	return -1;
}

// Push 
void push(SeqStack* s, Elemtype e){
	if(is_Empty){
		printf("Stack is Full\n");
	}else{
		s->top ++;
		s->data[s->top] = e;
	}	
}

// Out of stack
void pop(SeqStack* s){
	int fetchElem;
	//If there are no elements in the stack
	if(s->top == -1){
		printf("Stack is Empty\n");
	}else{
		fetchElem = s->data[s->top];
		s->top --;
		printf("%d\n",fetchElem);
	}
}

// Get stack top element
// Here is to view the top elements of the stack, not out of the stack
void getTop(SeqStack s, Elemtyep e){
	// If the stack is empty
	if(s->top == -1){
		printf("Stack is Empty\n");
	}else{
		e = s->data[s->top];
		printf("%d\n", e);
	}
}

// Gets the length of the stack
void stackLength(SeqStack s){
	int length;
	length = s->top + 1;
	printf("%d\n", length);
} 

Discontinuous stack

Discontinuous stack refers to the structure of the stack, which does not depend on the fixed continuous memory space, but uses pointers to connect the scattered stack storage elements to realize the function of the stack.
Advantages of discontinuous stack:

• The stored elements are scattered, the size is not limited, and the depth can be widened arbitrarily
• You don't need to use the whole block of memory

Disadvantages:

• Pointer connection is used between elements, and the operation is complex

code implementation

# include<stdio.h>
# include<stdlib.h>

typedef int ElemType;

// Define a single stack node
typedef struct Node {
	// Define a data field for storing stack elements
	int data;
	// Define the pointer field to point to the next stack element
	struct Node* next;
} LinkStack;

// Initialization stack
void initStack(LinkStack* s){
	// Open up the memory space of one node at a time
	s = (LinkStack*)malloc(sizeof(LinkStack));
	// Clear pointer
	s->Next = NULL;
}

// Judge whether it is empty
int is_Empty(LinkStack* s){
	return(s->next == NULL)
}

// Destroy stack
void destroyStack(LinkStack* s){
	Node *h = s;
	// First traverse to the last stack storage space of the stack
	// Then release it, and then traverse from the beginning to the last person's stack storage space
	while(s != NULL){
		s = s->next;
		free(p);
		p = s;
	} 
}

// Push 
void push(LinkStack* s, ElemType e){
	LinkStack* p;
	p = (LinkStack*)malloc(sizeof(LinkStack));
	p->data = e;
	// Point the pointer of the stack to be pressed to the first stack element
	p->next = s->next;
	// Then make the first stack element the element to be inserted
	s->next = p;
}

// Out of stack
void pop(LinkStack* s){
	// Determine whether the stack is empty
	if(s->next == NULL){
		printf("Stack is Empty\n");
	}else{
		// Temporary storage of the first stack to be deleted
		LinkStack* temp = s->next;
		// Make the first stack the next stack of the original first stack
		s->next = temp->next;
		// Release the storage space of the original first stack
		free(temp);
	}
}