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

The stack

The concept and structure of stack

Stack: A special linear table that allows only 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. The data elements In the stack adhere to LIFO (Last In First Out).

Push: The insertion of a stack is called push/push/push, and the data is pushed at the top of the stack


Unstack: The operation of deleting a stack is called making a stack. Outgoing data is also at the top of the stack


The realization of the stack

Stack implementation can generally use an array or linked list implementation, relatively speaking, the array structure is better. Because it’s cheaper to insert data at the end of an array.

image-20211030141911116


Stack node

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;       / / stack
	int capacity;  / / capacity
}ST;
Copy the code

The stack initialization function StackInit

image-20211030142711379 


// stack initialization function
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
Copy the code

The push function StackPush

image-20211030150058834 


// The push function
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)// Determine whether to expand the capacity
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a,newcapacity*sizeof(STDataType));
		if(! tmp) {printf("relloc fail\n");
			exit(- 1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	// Send the data back after expansion
	ps->a[ps->top] = x;
	ps->top++;
}
Copy the code

Write the stack destruction function in advance

The StackDestroy function StackDestroy

image-20211030150933462 


// the stack destruction function
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
Copy the code

Out of the stack function StackPop

image-20211030152048368 


// exit the stack function
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top>0);
	ps->top--;		
}
Copy the code

Check whether the stack is empty StackEmpty

image-20211030160445768 


// Check whether the stack is empty
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
Copy the code

Take the top element function StackTop

image-20211030161055009 


// take the top function of the stack
STDataType StackTop(ST* ps)
{ assert(ps); assert(! StackEmpty(ps));return ps->a[ps->top - 1];
}
Copy the code

StackSize function StackSize

image-20211030161322235 


// Stack size function
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
Copy the code

Traversal stack

image-20211030162836429 


while(! StackEmpty(&stack))
	{
		printf("%d ", StackTop(&stack));
		StackPop(&stack);
	}
Copy the code

code

Stack.h

#pragma once

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

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;       / / stack
	int capacity;  / / capacity
}ST;

// stack initialization function
extern void StackInit(ST* ps);
// the stack destruction function
extern void StackDestroy(ST* ps);
// The push function
extern void StackPush(ST* ps, STDataType x);
// exit the stack function
extern void StackPop(ST* ps);
// take the top function of the stack
extern STDataType StackTop(ST* ps);
// Stack size function
extern int StackSize(ST* ps);
// Check whether the stack is empty
extern bool StackEmpty(ST* ps);

Copy the code

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Stack.h"


// stack initialization function
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
// The push function
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)// Determine whether to expand the capacity
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a,newcapacity*sizeof(STDataType));
		if(! tmp) {printf("relloc fail\n");
			exit(- 1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	// Send the data back after expansion
	ps->a[ps->top] = x;
	ps->top++;
}
// the stack destruction function
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
// exit the stack function
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top>0);
	ps->top--;		
}
// take the top function of the stack
STDataType StackTop(ST* ps)
{ assert(ps); assert(! StackEmpty(ps));return ps->a[ps->top - 1];
}
// Stack size function
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
// Check whether the stack is empty
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
Copy the code

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Stack.h"

void Test1(a)
{
	ST stack = { 0 };
	StackInit(&stack);
	StackPush(&stack.1);
	StackPush(&stack.2);
	StackPush(&stack.3);
	StackPush(&stack.4);
	/ / traversal stack
	while(! StackEmpty(&stack))
	{
		printf("%d ", StackTop(&stack));
		StackPop(&stack);
	}
	printf("\n");
	StackDestroy(&stack);
}

int main(a)
{
	Test1();
	return 0;
}
Copy the code

practice

Case 1Valid parentheses

image-20211030163516039


image-20211030180114513


image-20211030192837065


image-20211030194404371 


typedef char STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;       / / stack
	int capacity;  / / capacity
}ST;


// stack initialization function
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
// the stack destruction function
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
// The push function
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)// Determine whether to expand the capacity
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a,newcapacity*sizeof(STDataType));
		if(! tmp) {printf("relloc fail\n");
			exit(- 1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	// Send the data back after expansion
	ps->a[ps->top] = x;
	ps->top++;
}
// Check whether the stack is empty
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

// take the top function of the stack
STDataType StackTop(ST* ps)
{ assert(ps); assert(! StackEmpty(ps));return ps->a[ps->top - 1];
}
// exit the stack function
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top>0);
	ps->top--;		
}
bool isValid(char * s){
    ST st = {0};
    StackInit(&st);
    while(*s)
    {
        // if it is an open parenthesis, it is pushed
        if(*s == '(' 
        || *s == '{' 
        || *s == '[')
        {
            / / into the stack
            StackPush(&st,*s);
            s++;
        }
        else
        {     
           if(StackEmpty(&st))     
           {
                StackDestroy(&st);
                return false;
           }
           / / out of the stack
           STDataType tmp = StackTop(&st);
           StackPop(&st);
           if(*s == '} '&& tmp ! ='{'
           || *s == '] '&& tmp ! ='['
           || *s == ') '&& tmp ! ='(')
           {
               StackDestroy(&st);
               return false;
           }           
           else{ s++; }}}// If the stack is not empty, there are open parentheses
    bool ret = StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}
Copy the code