C language to achieve the chain stack

Chain stack diagrams

Chain stack is the chain storage structure of stack. Chain stack can be realized by the head plug method of single linked list.

Single-linked lists, stacks, queues, trees, binary trees, and so on are easy to understand.

General operation of chain stack

/ * * * * * * * * * * * * * * * * * * * * * chain stack the normal operation of * * * * * * * * * * * * * * * * * * * * * * * * * * * * /

LinkStack 	 InitLinkStack(a);			// Initializes the stack
int   	 	 StackEmpty(a);				// Check that the stack is empty
int   	 	 StackLength(a);				// Stack length (number of stack elements)
int    		 Push(a);					// push the stack
ElemType 	 Pop(a);						// exit the stack
void 	 	 DestroyStack(a);			// Destroy the stack

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
Copy the code

Define the stack structure

#include "stdio.h"
#include "malloc.h"


#define TRUE  1
#define FALSE 0

typedef int ElemType;		// The stack stores the data type of the element


/* * Defines the stack structure */
typedef struct Node{
	ElemType data;			// stack node data field
	struct Node *next;		// stack node pointer field
}*LinkStack, Node;
Copy the code

Initializes the stack

// Initializes the stack (the stack of the leading node)
LinkStack InitLinkStack(a){
	LinkStack s = (LinkStack)malloc(sizeof(struct Node));
	s -> next = NULL;
	return s;
}
Copy the code

Chain stack found empty

/* * Check if the stack is empty * s stack */
int StackEmpty(LinkStack s){
	if(s == NULL) {return FALSE;
	}
	return s -> next == NULL;
}
Copy the code

Because of the chain storage structure, there is no stack full.

Calculates the length of the stack

/* * Find the length of the stack (number of elements in the stack) * s stack */
int StackLength(LinkStack s){
	LinkStack p;
	int len = 0;
	if(StackEmpty(s)){
		return FALSE;
	}
	p = s -> next;	// The stack of the leading node should be moved first
	while(p ! =NULL){
		len ++;
		p = p -> next;
	}
	return len;
}
Copy the code

Push chain

/* * push stack push stack * s chain stack * data push data */
int Push(LinkStack s, ElemType data){
	// Assign a stack node
	Node *new_node = (Node *)malloc(sizeof(struct Node));
	if (new_node == NULL) return FALSE;		// Node allocation failed
	
	// Use headers just like single-linked lists
	new_node -> data = data;
	new_node -> next = s -> next;
	s -> next = new_node;
	return TRUE;
}
Copy the code

Out of stack (Pop)

/* * out of the stack stack * s chain stack */
ElemType Pop(LinkStack s){
	LinkStack top;
	ElemType data;
	/ / the stack is empty
	if(StackEmpty(s)){
		return FALSE;
	}
	top = s -> next;	// Access the top of the stack
	data = top -> data;	// Fetch the top element of the stack
	s -> next = top -> next;
	free(top);			// Free space at the top of the stack
	return data;
}
Copy the code

Chain stack operation test

// Program main entry
int main(int argc, char const *argv[])
{
	LinkStack s = InitLinkStack();
	printf("StackEmpty():%d\n", StackEmpty(s));
	printf("StackLength():%d\n\n", StackLength(s));

	// Push the element
	ElemType datas[] = {1.3.5.7.9};

	// Dynamically count the number of elements to be pushed
	int len = sizeof(datas) / sizeof(datas[0]);	

	// The for loop is pushed in sequence
	printf("Push():");
	for(int i = 0; i < len; i++){
		printf("%d\t", datas[i]);
		Push(s, datas[i]);
	}
	printf("\nStackEmpty():%d\n", StackEmpty(s));
	printf("StackLength():%d\n\n", StackLength(s));

	// exit the stack
	printf("Pop(): ");
	while(! StackEmpty(s)){printf("%d\t", Pop(s));
	}
	printf("\nStackEmpty():%d\n", StackEmpty(s));
	printf("StackLength():%d\n\n", StackLength(s));
	return 0;
}
Copy the code

The results are as follows:

StackEmpty():1
StackLength():0

Push():1        3       5       7       9
StackEmpty():0
StackLength():5

Pop(): 9        7       5       3       1
StackEmpty():1
StackLength():0
Copy the code

The source code

The source code has been uploaded to GitHub data-structure-of-C, welcome to visit.

✍ code word is not easy, the long journey always feeling, praise again go line, also hope you heroes support ❤️