preface

This paper is based on C language.
The following is the main content of this article, and the following cases can be used for reference

1, Concept and structure of stack

Stack: a special linear table that allows insertion and deletion of elements only at a fixed end. One end for data insertion and deletion is called the top of the stack, and the other end is called the bottom of the stack. The data elements in the stack follow the principle of Last In First Out LIFO (Last In First Out).

Stack entry: the stack insertion operation is called stack entry / stack pressing / stack entry, and the input data is at the top of the stack.
Stack out: stack deletion is called stack out. The output data is also at the top of the stack.

2, C language - basic operation and implementation of stack

The basic operations of the stack mainly include the following: initialization, entering the stack, exiting the stack, obtaining the top element of the stack, obtaining the number of effective elements in the stack, empty judgment, and destroying the stack

1. Create stack

Stack is similar to linear table. There are also two storage representation methods: fixed length static stack and chain stack supporting dynamic growth. The operation of chain stack is a special case of linear table operation, which is easy to implement. The static stack, that is, the sequential storage structure of the stack, uses a group of storage units with continuous addresses to store the data elements from the bottom of the stack to the top of the stack in turn. At the same time, the pointer top is attached to indicate the position of the top element in the sequential stack, and top = 0 represents the empty stack. Therefore, in the non empty stack, top represents the next position of the top element. Because it is not practical in practice, the following implementations are dynamic growth stacks

Additional static stack:

#define N 10
typedef struct Stack
{
 STDataType arr[N];
 int top; // Stack top
}Stack;

Stack supporting dynamic growth:

// Stack supporting dynamic growth
typedef int STDataType;   //It is convenient to modify different stack data types
typedef struct Stack
{
	STDataType* a;
	int top;		// Stack top
	int capacity;  // capacity 
}Stack;

2. Stack initialization

Here, top = 0 indicates an empty stack, which is convenient to judge whether the stack is full in the later stage. In a non empty stack, top represents the next position of the top element of the stack.

The code is as follows:

// Initialization stack 
void StackInint(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

3. Stack

Judge whether the stack is full. If it is full, use the realloc() function to open up additional space. If you forget this function, remember to review it!

The code is as follows:

void StackPush(Stack* ps, STDataType data)
{
	if (ps->top == ps->capacity)  //Determine whether capacity expansion is required
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = data;
	ps->top++；
}

4. Out of the stack

Here, you must judge whether the stack is empty. If it is empty, top = -1 will result in illegal access to memory when entering the stack.

The code is as follows:

void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StachEmpty(ps));  //Judgment is not empty
	ps->top--;
}

5. Get stack top element

Here, judge whether the stack is empty. If it is empty, it means that the stack is empty and there is no data.

The code is as follows:

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StachEmpty(ps));
	return ps->a[ps->top - 1];
}

6. Get the number of valid elements in the stack

The code is as follows:

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

7. Check whether the stack is empty

If NULL, it returns a non-zero result; otherwise, it returns 0

The code is as follows:

bool StachEmpty(Stack* ps)
{
	assert(ps);
	if (ps->top == 0)
		return true;
	return false;
}

8. Destruction stack

Release the space created by realloc(), set a to NULL, and keep good habits

The code is as follows:

void StackDestroy(Stack* ps)
{
	assert(ps);
	if (ps->a)
		free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

3, Classic use of stack

1. Problem description

Attach link: Bracket matching problem
The title is described as follows:

2. Problem solving methods

Solution: this problem can be solved by using the data structure of stack.
We iterate over the given string s. When we encounter a left parenthesis, we expect a right parenthesis of the same type to close it in subsequent iterations. Therefore, it can be seen from the example that when the left bracket is encountered, the stack operation is performed, and when the right bracket is encountered, the stack operation is performed to match it. If it does not match, false is returned When the string is traversed and the stack is empty, true is returned
Complexity analysis:
Time complexity: O(N) traverses the string once.
Space complexity: O(N) if the input is [[[[[[], the size of the stack will be the length of the input string.

3. Code implementation

Since the stack has been created above, the code can be used directly (yes, ctrl + c and ctrl + v are the "basic cultivation" of a "qualified programmer")

bool isValid(char * s){
//Implementation of stack
typedef struct Stack
{
	char* a;
	int top;
	int capacity;
}Stack;
void StackInint(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
bool StackEmpty(Stack* ps)
{
	assert(ps);
	if (ps->top == 0)
		return true;
	return false;
}
void StackDestroy(Stack* ps)
{
	assert(ps);
	if (ps->a)
		free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void StackPush(Stack* ps, char data)
{
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		char* tmp = (char*)realloc(ps->a, sizeof(char) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}
			ps->a = tmp;
			ps->capacity = newcapacity;
	}
	ps->a[ps->top] = data;
	ps->top++;
}

char StackTop(Stack* ps)
{
	assert(ps);
    if(ps->top)
	return ps->a[ps->top - 1];
    return 'a';
}

void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	//free(ps->a + ps->top - 1);
	ps->top--;
}

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

Stack ST;
StackInint(&ST);
//Match parentheses
while(*s)
{
	//It is an open parenthesis and is put on the stack
    if((*s == '(')||(*s == '[')||(*s == '{'))
    StackPush(&ST, *s);
    else
    {	
    	//The right parenthesis matches the top element of the stack. If the matching is successful, it will be out of the stack. Otherwise, it will return false
        if((*s==')'&&StackTop(&ST)!='(')
        ||(*s==']'&&StackTop(&ST)!='[')||
        (*s=='}'&&StackTop(&ST)!='{'))
        return false;
        StackPop(&ST);
    }
    s++;
}
if(StackEmpty(&ST)!=0)
	return true;
return false;
}

Attach the operation diagram:

The above is the content brought by using c language this time. If it helps you, please like it and support it