C language implementation of chain stack (without leading node)

C Language implementation chain stack ( No leading node )

Preface

Follow up on the previous article C Language implementation sequence stack After implementing the sequence stack , This time, let's implement the chain stack . Because the characteristic of stack is to operate only at one end , So I think it will be easier to implement without leading nodes , And do not waste the space of the head node .

Implemented function

• Initialization stack
• Push
• Out of the stack
• Get stack top element

Screenshot of main interface

Definition of stack

Each node needs to have a data field and a pointer field . I defined a global variable length To view the number of elements in the stack .

typedef int ElemType;// Alias the data type , This deposit is int type , If you want to save it as another type, you only need to modify here once  
int length = 0;// Define a global variable to represent the number of elements actually stored in the stack 

//------- Structure definition part ------ //
typedef struct mystack{
    
	ElemType data; // Data fields  
	struct mystack *next;// Pointer to the top element of the stack  
}MyStack;
//------- Structure definition part ------ //

Initialization of stack

Due to the way of not leading nodes , During initialization, you only need to set the pointer of the header node to null .

// Initialization of stack ( No leading node ) 
bool InitStack(MyStack *S)
{
    
	S = NULL;// First set the head pointer to null  
	return true;
} 

Push

Elements need to be distinguished when they are put on the stack Two cases ：

​ ① The stack is empty before entering the stack , That is to put the first element on the stack , At this point, you only need to apply for a new node to save the stacked elements , Then point the head pointer to the new node (S->next = p), And let the pointer of this node point to NULL(p->next = NULL).

​ ② There are already elements in the stack when entering the stack , At this time, the new application node also needs to save the newly stacked elements , And you need to point the pointer of the new node to the node pointed to by the original header pointer (p->next = S->next), Then let the header pointer point to the new node (S->next = p).

// Push  
bool Push(MyStack *S,ElemType e)
{
    
	length++;// The number of elements in the stack +1 
	//1. Apply for a memory space to save the new node  
	MyStack *p = (MyStack *)malloc(sizeof(MyStack));
	//2. Put the value into the data field of the node  
	p->data = e;
	
	// Do special processing for the first element on the stack 
	if(length==1)
	{
    
		S->next = p;
		p->next = NULL;
	}
	else
	{
    
		p->next = S->next;
		S->next = p;
	}
	return true;
} 

Out of the stack

You need to judge whether the stack is empty when you exit the stack . Just point the header pointer to the next element at the top of the stack .

// Out of the stack 
bool Pop(MyStack *S)
{
    
	if(S->next==NULL)
		return false;
	
	MyStack *q = S->next;
	S->next = q->next;

	length--;// The number of elements in the stack -1
	return true; 
}

Get stack top element

To get the top element of the stack, you also need to determine whether the stack is empty . If it's not empty , Then the element pointed to by the header pointer is the stack top element .

// Get the current stack top element 
bool GetTop(MyStack *S,int *x)
{
    
	if(S->next==NULL)// If the stack is empty  
		return false;
	else	
		*x = (S->next)->data;
	
	return true;
} 

Get stack length

Get the stack length and print the result directly here , Of course, you can also use a value to return .

// Get stack length  
bool GetLen(MyStack *S)
{
    
	printf(" The number of elements in the current stack is :%d\n",length);
    return true;
} 

All the code

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h> // according to C99 standard ,C Language use bool Type needs to add this header file 


typedef int ElemType;// Alias the data type , This deposit is int type , If you want to save it as another type, you only need to modify here once  
int length = 0;// Define a global variable to represent the number of elements actually stored in the stack 

//------- Structure definition part ------ //
typedef struct mystack{
    
	ElemType data; // Data fields  
	struct mystack *next;// Pointer to the top element of the stack  
}MyStack;
//------- Structure definition part ------ //
 
//------- Function declaration part ------ //
void MainMenu();
bool InitStack(MyStack *S);// Initialization of stack  
bool Push(MyStack *S,ElemType e);// Put the element e Push to stack  
bool Pop(MyStack *S);// Out of the stack 
bool GetTop(MyStack *S,int *x);// Get the current stack top element  
bool GetLen(MyStack *S);// Get stack length , And print directly on the screen  
//------- Function declaration part ------ //
int main()
{
    
	int ch;// Select the operation instruction  
	int element;// Stack elements  
	int x;// Get the elements of the stack  
	MyStack S;
	InitStack(&S);// Initialize a stack  
	
	while(1)
	{
    
		MainMenu(); 
		printf(" Please enter the action you want to perform :");
		scanf("%d",&ch);
		
		switch(ch)
		{
    
			case 0:		printf(" Thank you for using , Exited ！");	exit(0);	break;
			case 1:		printf(" Please enter the element you want to stack :\n");
						scanf("%d",&element); 
						if(Push(&S,element))
							printf(" Stack successfully ！\n");
						else
							printf(" Failed to stack ！ The stack is full ！\n");
						break;
			case 2:		
						if(Pop(&S))
							printf(" Stack out successfully ！\n");
						else
							printf(" Stack out failed ！ Stack empty ！\n");
						break;		
			case 3:		
						if(GetTop(&S,&x))
							printf(" Get the top of stack successfully ！ The current stack top element is :%d\n",x);
						else
							printf(" Failed to get top of stack ！ Stack empty ！\n");
						break; 
			case 4:		GetLen(&S);  break;
			default:	printf(" The operation instruction you entered is incorrect ！ Please re-enter ！");
		}
	}
	return 0;
}

// The main menu , Show  
void MainMenu()
{
    
	printf("\n\n\n");
	printf("\t ************* The implementation of chain stack ************\n\n"); 
	printf("\t ------- 0. sign out  \n\n");
	printf("\t ------- 1. Put data on the stack \n\n");
	printf("\t ------- 2. Perform an out of stack operation \n\n");
	printf("\t ------- 3. Get the current stack top element \n\n");
	printf("\t ------- 4. Number of elements in the output stack \n\n");
	printf("\t *************************************\n");
}

// Initialization of stack ( No leading node ) 
bool InitStack(MyStack *S)
{
    
	S = NULL;// First set the head pointer to null  
	return true;
} 

// Push  
bool Push(MyStack *S,ElemType e)
{
    
	length++;// The number of elements in the stack +1 
	//1. Apply for a memory space to save the new node  
	MyStack *p = (MyStack *)malloc(sizeof(MyStack));
	//2. Put the value into the data field of the node  
	p->data = e;
	
	// Do special processing for the first element on the stack 
	if(length==1)
	{
    
		S->next = p;
		p->next = NULL;
	}
	else
	{
    
		p->next = S->next;
		S->next = p;
	}
	
	return true;
} 

// Out of the stack 
bool Pop(MyStack *S)
{
    
	if(S->next==NULL)
		return false;
	
	MyStack *q = S->next;
	S->next = q->next;

	length--;// The number of elements in the stack -1
	return true; 
} 

// Get the current stack top element 
bool GetTop(MyStack *S,int *x)
{
    
	if(S->next==NULL)// If the stack is empty  
		return false;
	else	
		*x = (S->next)->data;
	
	return true;
} 

// Get stack length  
bool GetLen(MyStack *S)
{
    
	printf(" The number of elements in the current stack is :%d\n",length);
	return true; 
} 

System function test

--------------------------------------------------- to update 2021 year 10 month 18 Japan -------------------------------------------------
Reminded by bloggers , The initialization method of the non leading node is changed to S == NULL. This is a more rigorous way of writing . It turned out to be S->next == NULL. The reason why there is no error report , It's because I'm in main Function to create a S When the object , There are next Of , So there is no problem setting the subsequent pointer to null , But in order to be consistent with the teaching method , Be rigorous , It was decided to amend to S== NULL.