“This is the fifth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

A stack,

💦 Stack concept and structure

Stack: A special linear table that allows insertion and deletion of elements at a fixed end. The end where data is inserted and deleted is called the top of the stack and the other end is called the bottom of the stack. Data elements In the stack follow the Last In First Out (LIFO) principle; At the same time, for a stack, one order corresponds to multiple order out of the stackCopy the code

The stack has two classic operations

1️ stack: stack insertion operation is called loading/pressing/loading, with data on the top of the stack.

2️ discount stack: stack deletion operation is called making stack. Outgoing data is also at the top of the stack.

💦 stack implementation

We can implement the stack in either an array or a linked list and they’re pretty much as efficient as each other, but arrays are recommended

1. Initialization

The function prototype

function

void StackInit(ST* ps)
{
    assert(ps);
    / / initialization
    ps->a = NULL;
    ps->top = 0;
    ps->capacicy = 0;
}
Copy the code
2. Insert the

The function prototype

function

void StackPush(ST* ps, STDatatype x)
{
    assert(ps);
    // Check the space
    if (ps->top == ps->capacicy)
    {
        // The capacity of the first space is 4, and the capacity of the other Spaces is 2
	int newcapacity = ps->capacicy == 0 ? 4 : ps->capacicy * 2;
	Realloc has the same effect as malloc
	STDatatype* tmp = realloc(ps->a, sizeof(STDatatype) * newcapacity);
	/ / check realloc
	/ / realloc failure
	if (tmp == NULL)
	{
            printf("realloc fail\n");
            exit(- 1);
	}
	/ / realloc success
	ps->a = tmp;
	ps->capacicy = newcapacity;
    }
	// Insert data
	ps->a[ps->top] = x;
	ps->top++;
}
Copy the code
3. Empty

The function prototype

function

bool StackEmpty(ST* ps)
{
    assert(ps); 
    // equal to 0 is true, otherwise false
    return ps->top == 0;
}
Copy the code
4. Remove

The function prototype

function

void StackPop(ST* ps)
{
    assert(ps);
    // Delete to ensure that the target space is not emptyassert(! StackEmpty(ps));/ / delete
    --ps->top;
}
Copy the code
Length of 5.

The function prototype

function

int StackSize(ST* ps)
{
    assert(ps);
    // Top is the length
    return ps->top;
}
Copy the code
6. The stack

The function prototype

function

STDatatype StackTop(ST* ps)
{
    assert(ps);
    // To find the top of the stack, make sure that the space pointing to is not emptyassert(! StackEmpty(ps));// Top -1 is the top of the stack
    return ps->a[ps->top - 1];
}
Copy the code
7. To destroy

The function prototype

function

void StackDestory(ST* ps)
{
    assert(ps);
    // if a is true, it points to a dynamically opened space
    if (ps->a)
    {
	free(ps->a);
    }
    ps->a = NULL;
    ps->top = 0;
    ps->capacicy = 0;
}
Copy the code

💦 Full code

I need three files here

1️ Static. H, used for function declaration

2️ Static. C, used for the definition of function

3️ Test. C, used for Test function

🧿 Stack. H
#pragma once

/ / head
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

/ / structure
typedef int STDatatype;
typedef struct Stack
{
    STDatatype* a; // Point to dynamically opened space
    int top; / / stack
    int capacicy; / / capacity
}ST;

/ / function
// We write Print, but not stack, because if stack can Print, it does not match lifO
	/ / initialization
void StackInit(ST* ps);
	/ / insert
void StackPush(ST* ps, STDatatype x);
	/ / found empty
bool StackEmpty(ST* ps);
	/ / delete
void StackPop(ST* ps);
	/ / the length
int StackSize(ST* ps);
	/ / stack
STDatatype StackTop(ST* ps);
	/ / destroy
void StackDestory(ST* ps);
Copy the code
🧿 Stack. C
#include"Stack.h"

void StackInit(ST* ps)
{
    assert(ps);
    / / initialization
    ps->a = NULL;
    ps->top = 0;
    ps->capacicy = 0;
}
void StackPush(ST* ps, STDatatype x)
{
    assert(ps);
    // Check the space
    if (ps->top == ps->capacicy)
    {
	// The capacity of the first space is 4, and the capacity of the other Spaces is 2
	int newcapacity = ps->capacicy == 0 ? 4 : ps->capacicy * 2;
	Realloc has the same effect as malloc
	STDatatype* tmp = realloc(ps->a, sizeof(STDatatype) * newcapacity);
	/ / check realloc
            / / realloc failure
	if (tmp == NULL)
	{
            printf("realloc fail\n");
            exit(- 1);
	}
            / / realloc success
	ps->a = tmp;
	ps->capacicy = newcapacity;
    }
	// Insert data
	ps->a[ps->top] = x;
	ps->top++;
}
bool StackEmpty(ST* ps)
{
    assert(ps); 
    // equal to 0 is true, otherwise false
    return ps->top == 0;
}
void StackPop(ST* ps)
{
    assert(ps);
    // Delete to ensure that the target space is not emptyassert(! StackEmpty(ps));/ / delete
    --ps->top;
}
int StackSize(ST* ps)
{
    assert(ps);
    // Top is the length
    return ps->top;
}
STDatatype StackTop(ST* ps)
{
    assert(ps);
    // To find the top of the stack, make sure that the space pointing to is not emptyassert(! StackEmpty(ps));// Top -1 is the top of the stack
    return ps->a[ps->top - 1];
}
void StackDestory(ST* ps)
{
    assert(ps);
    // if a is true, it points to a dynamically opened space
    if (ps->a)
    {
        free(ps->a);
    }
    ps->a = NULL;
    ps->top = 0;
    ps->capacicy = 0;
}
Copy the code
🧿 Test. C
#include"Stack.h"

int main(a)
{
    ST st;
    / / initialization
    StackInit(&st);
    // Insert + delete
    StackPush(&st, 1);
    StackPush(&st, 2);
    StackPush(&st, 3);
    StackPush(&st, 4);
    StackPush(&st, 5);
    StackPop(&st);
    StackPop(&st);
    / / the length
    StackSize(&st);
    / / stack
    StackTop(&st);
    / / destroy
    StackDestory(&st);
    return 0;
}
Copy the code