1. Introduction

As a common abstract data type, stack is very common in common use. It is a linear table with limited operation. Limit linear tables to insert and delete only at the end of the table. This end is called the top of the stack, and the other end is called the bottom of the stack. Inserting a new element into a stack is also called stack entry, stack entry or stack pressing. It puts the new element above the top element of the stack to make it a new top element; Deleting an element from a stack is also called out of stack or out of stack. It deletes the top element of the stack and makes its adjacent elements become new top elements.
This article leads you to simulate the implementation of a sequential stack. And encapsulate some common stack operations. I believe that students who have used the stack container in STL often call some functions packaged in the stack container (such as size (), empty (), etc.). Through this blog, we can also see the shadow of the source code of common stack API s. Of course, if you want to deeply analyze the source code of STL, I recommend you to read the book "STL source code analysis"!

2. Stack structure

Since stack is an abstract data type, let's first define its structure.

#define MAXSIZE 1024

struct SStack
{   
    //Take the array head as the end of the stack, because if it is used as the top of the stack, it will cost a lot of time to go back and forth
    void *data[MAXSIZE]; //array
    int size;
};

typedef void * sstack; 

Structure encapsulates data and stack size

The reason why a void * array is encapsulated in the structure of the stack is that we do not know what type of data to store with the stack, so we use a universal pointer array, which can point to any type of memory. The advantage of this is to make our code universal. (cpp generic programming yyds!)

3. Initialization stack

Well, after we have defined the structure of the stack, if we want to simulate a stack, of course we need to have a stack. So the next step is to initialize the stack.

//Initialization stack
sstack init_stack(){
    struct SStack * myStack = malloc(sizeof(struct SStack));
    if (myStack==NULL) //Judge null after applying for memory. This is a way to avoid the generation of wild pointers
    {
        return NULL;
    }
    memset(myStack->data,0,sizeof(void *)*MAXSIZE); //Assign an initial value of 0 to the array
    myStack->size=0; //Initial stack size
    return myStack;
}

OK, we have initialized a stack now. There is no data in its pointer array, and the size is 0.

4. Stack

After initializing the stack, we can insert data into the stack! Before inserting data, check whether the stack has been initialized. Next, we implement the stack operation.

//Push 
void push_stack(sstack stack,void *data ){
    if (stack==NULL) //Determine whether the stack is initialized successfully
    {
        return;
    }
    if (data==NULL)
    {
        return;
    }
    struct SStack *myStack=stack; //Convert the pointer of the stack into the pointer structure of the user

    //Judge stack full
    if (myStack->size==MAXSIZE)
    {
        return;
    }
    
    //Stacking is tail inserting array
    myStack->data[myStack->size]=data;
    myStack->size++; //Stack size + 1
}

The process is easy to understand, that is, don't forget the conversion of pointers.

5. Out of stack

The logic of the stack is very simple. We pass a stack. Determine whether the stack has been initialized and is not empty. Then let the top element out of the stack, and the stack length is - 1.

//Out of stack
void pop_stack(sstack stack){
    if (stack==NULL)
    {
        return;
    }
    struct SStack *myStack=stack;

    //Judge whether the stack is empty
    if (myStack->size==0)
    {
        return;
    }
    
    //Out of the stack is actually tail deletion
    myStack->data[myStack->size-1]=NULL;
    myStack->size--;
}

6. Return stack top element

//Return to top of stack
void * top_stack(sstack stack)
{
	if (stack == NULL)
	{
		return NULL;
	}

	struct SStack * mystack = stack;

	if (mystack->size == 0)
	{
		return NULL;
	}
	return mystack->data[mystack->size - 1];
}

7. Determine whether the stack is empty

//Determine whether the stack is empty
int isempty_stack(sstack stack){
    if (stack==NULL)
    {
        return -1; //Return - 1 for empty stack
    }
    struct SStack *myStack=stack;
    if (myStack->size==0)
    {
        return -1;
    }
    return 0;
}

8. Return stack size

//Return stack size
int size_stack(sstack stack){
    if (stack==NULL)
    {
        return -1;
    }
    struct SStack *myStack=stack;
    return myStack->size;
}

9. Destroy stack

Best of all, we need to destroy the stack to free up memory space.

//Destroy stack
void destroy_stack(sstack stack){
    if (stack==NULL)
    {
        return;
    }    
    free(stack);
    stack=NULL;
}

10. Testing

In order to test our code without losing generality, we use structure elements to operate on our stack.
First define a structure:

struct Person
{
	char name[64];
	int age;
};

The structure contains the name and age of the person.
Test:

void test01(){
    //Initialization stack
    sstack myStack=init_stack();
    //Create data
	struct Person p1 = {  "aaa", 10 };
	struct Person p2 = {  "bbb", 20 };
	struct Person p3 = {  "ccc", 30 };
	struct Person p4 = {  "ddd", 40 };
	struct Person p5 = {  "eee", 50 };
    //Push 
	push_stack(myStack, &p1);
	push_stack(myStack, &p2);
	push_stack(myStack, &p3);
	push_stack(myStack, &p4);
	push_stack(myStack, &p5);
    
    printf("The number of elements in the stack is:%d\n", size_stack(myStack));

    while (isempty_stack(myStack)==0) //When the stack is not empty, the elements are out of the stack in turn
    {
        struct Person *p=top_stack(myStack);
        printf("full name:%s，Age:%d\n",p->name,p->age);

        //Element out of stack
        pop_stack(myStack);
    }
    
    //Destroy stack
    destroy_stack(myStack);

}

Operation results: