Chain implementation of stack -- linear structure

I have learned before Linear storage Linear table operation , Between elements 1 Yes 1 The relationship between , Such as The order of linear tables 、 The chain Storage and presentation of , It is a manifestation of the linearity between data elements .

Except linear table , There are also data structures stored linearly Stacks and queues 、 strand 、 Arrays and generalized tables etc. .

Today, I will share with you a very important data structure among the data structures , Namely ------> Stack

How to understand “ Stack ” Well ？

Stack is widely used in our life , Such as the dishes we usually use for cooking , Generally, you need to put the plates one by one from bottom to top , And when you use it, you need to take it out one by one from top to bottom .
As we can see, the clip of the pistol , We need to press down the bullets one by one when loading the cartridge case , When the bullets are fired, they will bounce out one by one from the bottom to the top, and so on , Art comes from life , ha-ha , There are too many in life The application of the stack Example , You can understand .

Sum up Stack It's a feature of Last in, first out (LIFO).
The corresponding is queue Characteristics of fifo (FIFO).

We call the operation of adding elements from bottom to top ----> Stack pressing operation
We also call the reduction of elements from top to bottom to outside as ----> The stack,

because The stack can only be operated from the top of the stack , That is, adding and deleting can only be done from the top , We also call the stack Linear table with limited operation .

because There is already a stack implementation in the textbook , Although it is pseudocode ( I'm not used to it , ha-ha ), Then I Realize the chain implementation of stack , For your reference .

Last self added Output all elements from top to bottom of the stack ( Adopt auxiliary stack ) Realization Of , If there are other friends who have other ideas , Welcome to comment and discuss ~

Definition of chain stack structure

Simple in stack element definitions and chained stack definitions

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

// Define the elements stored in the stack Student 
struct Student{
    	
	int id;				// Student id 
	int age;			// Student age  
	Student *next;		// Pointer to the next element  
};


// Define a data stack stored in a chain  
typedef struct Node{
    	
	Student *base;		// Define the pointer at the bottom of the stack , Used to point to elements at the bottom of the stack  
	Student *top;		// Define the top of stack pointer , Used to point to the top of the stack ,  They are initialized to NULL 
}*Stack;

All method declarations

int initStack(Stack &stack);						// Initialize the linked list stack  
int clearStack(Stack &stack);						// Clear all data in the stack  
int destroyStack(Stack &stack);						// Destroy the linked list data stack  
int stackEmpty(Stack &stack);						// Determine whether the linked list stack is NULL 
int stackLength(Stack &stack);						// Get stack length function  
int getStackTop(Stack &stack, Student &student);		// Get stack top element  
int pushStack(Stack &stack, Student student);			// Stack pressing operation , Push an element onto the stack  
int popStack(Stack &stack, Student &student);			// The stack, , Pop an element out of the stack , And with parameters student return  
void printStack(Stack &stack);						// Output all the elements in the stack from top to bottom  
void stackTraverse(Stack &stack);					// Output all the elements in the stack from the bottom of the stack to the top of the stack  

Initialize stack operation

Stack initialization operation

// data structure ---- Initialize chained data stack operation  
int initStack(Stack &stack)
{
    
	stack = (Node *)malloc(sizeof(Node));			// Use malloc Function dynamically opens up space for data stack  
	stack->base = NULL;					// The pointer at the bottom of the stack points to NULL 
	stack->top = NULL;					// The stack top pointer points to NULL 
	
	return OK;					// Returns the stack creation success message  
}

push Stack pressing operation

push Stack pressing operation , Push a data element onto the stack according to the parameters passed by the function

// data structure ----push Stack pressing operation , Push a data element onto the stack  
int pushStack(Stack &stack, Student student)
{
    
	Student *student1 = (Student *)malloc(sizeof(Student));		// Dynamically open up an element space  
	
	student1->id = student.id;				// information gathering , Get the... Of the elements to be stacked id 
	student1->age = student.age;			// Get the... Of the elements to be stacked age 
	
	if(stack->base == NULL)					// If the bottom of the stack is NULL when , It indicates that there is no element in the stack  
	{
    
		stack->base = student1;			// The bottom of the stack points to this element student1 
		stack->top = student1;			// The top of the stack points to this element student1 
	}
	else									// otherwise  
	{
    
		stack->top->next = student1; 		// Put the element student1 Pressure into the stack  
		stack->top = student1;				// The stack top pointer points to the new element student1 
	}
	
	stack->top->next = NULL;		// Set the address of the next element to be pressed as NULL( It is somewhat similar to the added elements of the chained linear table ) 
	
	return OK;
}

pop The stack,

The stack, , Pop up the top element of the stack , And save the pop-up information through function parameters for return

// data structure ---- The stack, , Pop up the top element of the stack  
int popStack(Stack &stack, Student &student)
{
    
	Student *p = stack->base, *q;		// Definition p The pointer temporarily points to the element at the bottom of the stack  
	
	if(stackEmpty(stack)) return ERROR;		// If the stack is empty, a failure message is returned  
	
	if(stack->top == stack->base)		// If top stack pointer and bottom stack pointer point to same element , Indicates that there is only one element in the stack  
	{
    
		student = *stack->top;			// Save the top element as a parameter and return  
		free(stack->top);			// Release the stack top element , Delete the stack  
		stack->base = NULL;				 
		stack->top = NULL;			// At the bottom of the stack 、 The top pointer points to again NULL, Represents that there are no elements yet  
		return OK;					// Return success message  
	}
	
	while(p->next != stack->top)		// If the elements in the stack  >= 2
	p = p->next;					//p The pointer moves up the loop from the bottom of the stack  , until p Point to the element below the top of the stack  
	
	q = stack->top;					//q Pointer to the top of the stack  
	student = *q;					// Assign the stack top element to the parameter student To be returned  
	stack->top = p;						// The pointer at the top of the stack moves down  
	stack->top->next = NULL;			// Set the address of the next element to be pressed as NULL
	
	free(q);						// Release the original stack top pointer  
	return OK;							// Return success message  
	
}

Print all elements from top to bottom

The auxiliary stack is used to output all elements from the top of the stack to the bottom of the stack

// data structure ---- Output all elements from the top to the bottom of the stack  
void printStack(Stack &stack)
{
    
	int i = 0;
	Stack new_stack; 
	initStack(new_stack);		// Define a new stack , And initialize  
	
	Student student;			// Define element variables student 
	printf(" The arrangement of data elements from the top of the stack to the bottom of the stack :\n");
	
	
	//stack Out of stack order ： A、B、C、D、E ---->  result ：stack The stack is empty  
	// meanwhile new_stack Stack order ： A、B、C、D、E ---->  result ：new_stack The original has been saved stack Stack  
	 
	while(!(stackEmpty(stack)))		// If the original stack is not NULL, Repeat the cycle  
	{
    
		popStack(stack, student);  				 // The stack,  
		printf("id = %d, age = %d.\n", student.id, student.age);	// Information output  
		pushStack(new_stack, student);			 // Stack pressing operation  
		i++;							//  Counter accumulation  
	}
	printf(" Shared data  %d  strip .\n\n", i);		   	// Number of output results  
	stack = new_stack;							// Make stack copy , The original stack has been restored ！ 
	return;						// return  
}

Print all elements from bottom to top

// data structure ---- Output all elements from the bottom of the stack to the top of the stack  
void stackTraverse(Stack &stack)
{
    
	int i = 0;
	Student *student = stack->base;					// Define a random variable pointer student Point to the element at the bottom of the stack  
	printf(" The arrangement of data elements from the bottom of the stack to the top of the stack :\n");
	while(student != NULL)							// Loop through the output  
	{
    
		printf("id = %d, age = %d.\n", student->id, student->age);
		student = student->next;				// The pointer moves up and down with the stack to output the next element  
		i++;								// Counter accumulation  
	}
	printf(" Shared data  %d  strip .\n\n", i);		// Output accumulated data  
	return;
}

Get stack top element

Get the top element of the chain stack

// data structure ---- Get stack top element  
int getStackTop(Stack &stack, Student &student)
{
    
	if(stack->top != NULL)					// If the stack top element is not NULL 
	{
    
		student = *stack->top;				// Pass the stack top element to the parameter variable  
		return OK;				// Return success message  
	}
	else return ERROR;			// Otherwise, a failure message will be returned  
}

Get the length of the chain stack

// data structure ---- Test stack length function  
int stackLength(Stack &stack)
{
    
	Student *student = stack->base;			// Define the random variable element to point to the element at the bottom of the stack  
	int i = 0;
	while(student != NULL)					// Loop traversal statistics  
	{
    
		student = student->next;			// Keep pointing to the upper elements of the stack  
		i++;					// Counter accumulation  
	}
	
	return i;					// Return length  
}

Destroy the stack 、 Empty stack 、 Determine stack empty operation

// data structure ---- Destroy chained data stack operation  
int destroyStack(Stack &stack)
{
    
	clearStack(stack);			// Clear all elements in the data stack  
	free(stack);				// Free the address space memory of the stack  
	stack = NULL;				// Set the stack pointer to NULL, That is to destroy 
	return OK;					// Return success message  
}


// data structure ---- Clean up the chained data stack  
int clearStack(Stack &stack)
{
    
	Student student;						// Define temporary element variables Student 
	while(stack->base != NULL)				// When the pointer at the bottom of the stack is not NULL when , Loop out of stack  
	popStack(stack,student);			// Element out of stack  
	
	if(stack->base == NULL) return OK;		// If the bottom of the stack is NULL, Return success message  
	else return ERROR;					// Otherwise, a failure message will be returned  
}



// data structure ---- Determine stack empty function  
int stackEmpty(Stack &stack)
{
    
	if(stack->base == NULL && stack->top == NULL)
		return TRUE;						// If the bottom pointer and the top pointer point to NULL, return true 
	else	
		return FALSE;						// Otherwise return to false 
}

No more test code for these methods , Friends can consult and communicate by themselves , Common progress , I am also studying advanced mathematics and other courses recently , It may be a little slow to update , ha-ha , Next time, prepare the chain Implementation of queues , come on. ~