Directory
What is a stack?
How the stack is implemented
Implementation of the stack
initialization
Empty
size
stack
pop out
Get the top element of the stack
destroy stack
test
Summarize
OJ works – bracket matching issue
copy of the stack
Code
What is a stack?
A stack is a data structure characterized by First In Last Out. Simply speaking, the function of data structure is the way of organizing data. The so-called first-in-last-out here refers to the characteristics of data entering and exiting in the stack.
Playing with the stack, you first understand a few concepts:
Top of the stack: The top of the stack is the only “opening” of the stack. Push and pop operations can only be performed at the top of the stack.
Push: Put the element from the top of the stack into the stack.
Pop: Remove the top element from the stack.
With a picture, better understand:
Stack implementation
There are two ways to implement a stack:
Array Implementation
The method of array implementation is to use an array to simulate the stack. We need a top to mark the position of the stack top element (or the next position of the stack top element), through In this way, the function of the stack is realized.
Linked list implementation
When implementing a linked list (take a single linked list as an example), you need to pay attention. You can use the head of the linked list as the top of the stack, because the head insertion of the single linked list is convenient, and the tail insertion needs to find the previous one at the end, which is inconvenient to traverse.
Of course, you can take the method of adding a variable, use a ptail pointer to point to the tail, and use the tail as the top of the stack, which is also completely possible, as shown in the figure below.
In short, both implementation methods are possible, but the implementation process needs to pay attention to the requirements of various functions of the stack.
Implementation of the stack
I chose to use an array to implement the stack.
The interface corresponding to the stack is as follows (implemented in C language)
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
// Renaming the int type, in order to modify the elements of the stack in the future
typedef int STDataType;
//Use a structure to put the relevant parameters of the stack together
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
} ST;
void STInit(ST *pst);//initialization
void STPush(ST* pst, STDataType x);//Push into the stack
void STPop(ST* pst);// pop the stack
STDataType STTop(ST* pst);//Get the top element of the stack
bool STEmpty(ST* pst);//judging whether the stack is empty
int STSize(ST* pst);//Get the number of elements in the stack
void STDestory(ST *pst);//Destroy the stack
Our implementation method is that creating a structure is equivalent to creating a stack, and we simulate the function of the stack by modifying the elements in the structure.
Then, we analyze the interface.
Initialization
void STInit(ST* pst) {
pst->a = NULL;
pst->top = 0;//The next top element of the stack
pst->capacity = 0;
}
Initialization is very simple, give an initial value to the relevant parameters of our stack.
Here I will focus on why top is 0.
As mentioned earlier, top can identify the subscript of the top element of the stack, or identify the subscript of the next position of the top element of the stack, so the difference between the two is the literal meaning , so why here, there is no element in the stack, so it is necessary to give zero?
In fact, you can think of it this way, The stack is empty is a special state, no matter which identification method you choose, you must uniquely identify the special state of the empty stack.
Suppose, we top identifies the next position of the top element of the stack, then give zero, if an element is entered in the stack, top + + becomes 1, is it just the next position of the top element of the stack?
Assuming that our top means the top element of the stack, then when you say it is empty, is it appropriate to give 0? Obviously inappropriate, you have to give -1, so that after you insert the element top + +, top points to the top element of the stack.
So, pay attention to this detail, here I choose to identify the next position of the top element of the stack.
capacity shows the capacity of the array.
Judging empty
Empty judgment is to check whether there are elements in the stack, and return a bool value.
bool STEmpty(ST* pst) {
assert(pst);
return pst->top == 0;
}
As mentioned earlier, when we mark top, the element at the next position on the top of the stack, The stack is empty means top is 0, then return here
The result of the expression pst->top == 0.
If top is zero, the expression evaluates to true and the stack is empty.
If top is not zero, the result of the expression is false and the stack is not empty.
(The assert used here is used to check whether the value of the parameter does not meet the requirements (generally it is not empty).
For example, pst cannot be empty here, because the stack must exist, if pst is NULL or false (in C language, NULL, false and 0 are equivalent).
If it is empty, the program will die directly and report the error of this line. The assertions used below are all of this function. )
As shown in the picture below:
size
Count how many elements are in the stack.
int STSize(ST* pst) {
assert(pst);
return pst->top;
}
Our stack is implemented with an array, and top points to the element next to the top element of the stack.
For example, there are five elements in the stack, the subscripts range from 0 to 4, and the value of top is 5, which is exactly the number of elements in the stack. It is okay if the stack is empty, and 0 is returned.
Push
The push operation is to push an element into the stack from the top of the stack.
void STPush(ST* pst, STDataType x) {
//Determine whether to increase the capacity
if (pst->top == pst->capacity) {
int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));
if (tmp == NULL) {
perror("realloc fail");
return;
}
pst->a = tmp;
pst->capacity = newCapacity;
}
//adding data
pst->a[pst->top] = x;
pst->top++;
}
Since our stack is simulated by an array, we need to judge whether it needs to be increased when inserting data.
The capacity parameter needs to be used here, so what is the need to increase the capacity? What should I pay attention to?
Suppose our capacity is 6, that is, there are at most 6 elements in the stack. Assuming our stack is full, should the subscript of the last element be 5, then should the value of top be 6 at this time? Numerically equal to capacity.
as the picture shows:
This state is the state when the stack is full, and data needs to be inserted, so the capacity needs to be increased.
For an array of arrays, realloc is used to increase the capacity, and the capacity is generally doubled. Note that there is a devilish detail here. After initialization, our capacity is 0. At this time, you should open up a space. At this time, the function of realloc is the same as malloc.
So this code appeared:
int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
Determine whether the capacity is zero, and if it is zero, assign a value of 4, and then the stack will open up space for four elements. If it is not zero, it will double the original capacity, and then expand normally.
After that, put the data into the stack normally, and don’t forget to make top ++.
Out of stack
The operation of popping the stack is simpler, just manipulate top.
void STPop(ST* pst) {
//Empty cannot be deleted
assert(pst);
assert(!STEmpty(pst));
pst->top--;
}
The premise of popping the stack is that the stack must have elements, so let’s judge whether it is empty first. If it is empty here, the return value of STEmpty is true. After using ! to negate, the value is flase, and an error will be reported.
Then, if it is not empty, delete it here, and we will let top decrease.
Note that the deletion here does not really remove the data from the array, but logically, we put top–, this element does not belong to our stack.
But this data still occupies memory in the memory, and this memory still belongs to our array. The next time you insert data, you can directly overwrite it.
as the picture shows:
Get the top element of the stack
Only returns the top element of the stack, and does not modify the elements in the station.
STDataType STTop(ST* pst) {
assert(pst);
assert(!STEmpty(pst));
return pst->a[pst->top - 1];
}
Similarly, the stack must exist and not be empty to get the top element of the stack.
top records the subscript of the next position of the top element of the stack, then top-1 is the subscript of the top element of the stack, directly access the elements of the array through this subscript, and return.
Destroy stack
The memory is freed, and the variable is empty.
void STDestory(ST* pst) {
assert(pst);
free(pst->a);
pst->a = NULL;
pst->capacity = pst->top = 0;
}
This is very simple, malloc opens, free releases, the pointer is empty, and the variable is set to zero.
test
Next, we will test whether our stack can be used normally through simple code.
void test01()
{
//Create a stack, that is, create a structure
ST st;
//initialization
STInit( &st);
//Into the stack 10 20 30 40
STPush( &st, 10);
STPush( &st, 20);
STPush( &st, 30);
STPush( &st, 40);
//Get the number of stack elements
int sz = STSize( &st);
printf("The number of elements in the stack is:>%d\
", sz);//4
//Get the top element of the stack
int tmp = STTop( &st);
printf("The top element of the stack is:>%d\
", tmp);//40
//Elements are popped out of the stack in this way, and the order should be 40 30 20 10 to satisfy first-in-last-out
printf("Pop:>");
while (!STEmpty( &st))
{
tmp = STTop( &st);
printf("%d ", tmp);
STPop( & st);
}
//Destroy the stack
STDestory( &st);
}
int main()
{
test01();
return 0;
}
The result is as follows:
From the test results, the implementation of our stack is successful! ! !
Summary
The implementation of the stack should pay attention to the following points:
- The characteristic of the stack is first in last out
- Arrays and linked lists can be used to implement stacks
- Stack functions include push, pop, top, size, empty, destroy
Did you think it was over here? Just kidding, look at my title, let’s use the stack we wrote to do a question! !
OJ works – bracket matching problem
Here is the link to the topic:
20. Valid Parentheses – Leetcode
Title description:
Topic overview:
That is, there is a string consisting only of brackets like ‘( )[ ] { }’, let us judge whether the brackets in the string it gives match.
The so-called matching refers to the same parentheses, one left and one right are called matching. The use case given in the title is very simple. I will write one for everyone, and you can see if it matches.
“( [ { } ] )” (the space in the middle is to separate characters), do you think the brackets in this string match?
The answer is: matches.
In the string, although the left bracket and the parenthesis are not adjacent to each other, they are logically matched.
You can think about it this way, from the middle, the two curly braces match, and then remove them, leaving “( [ ] )” , and then the square brackets in the middle are also matched , remove it, and the parentheses are also matched in the same way.
Based on these understandings, we give the following ideas:
We use a stack to put the characters in the character into the stack.
If a left parenthesis is encountered, it is pushed onto the stack.
If a closing parenthesis is encountered, the element on the top of the stack is obtained to match the closing parenthesis.
Matches
- The case of single-pair matching is easy to say, just continue to judge the next character.
- There are several situations where there is a mismatch:
- When a right parenthesis is encountered and does not match the top element of the stack, false is returned directly.
- When the string is empty, there are still elements in the station (it must be the left bracket, because only the left bracket is pushed into the stack), directly return false
Then it is very clear to return true. When the string is empty and there are no elements in the stack, it will return true.
Copy of stack
Copy the stack we wrote and copy it into the OJ topic.
//Interface type OJ does not need to include the header file, delete it //#pragma once //#include//#include //#include //#include //typedef int STDataType; //Because characters are to be placed in the station, it is changed to char here typedef char STDataType; typedef struct Stack { STDataType* a; int top; int capacity; } ST; //Actually, the function declaration can not be written here, and it is not bad to write. void STInit(ST *pst); void STPush(ST* pst, STDataType x); void STPop(ST* pst); STDataType STTop(ST* pst); bool STEmpty(ST* pst); int STSize(ST* pst); void STDestory(ST *pst); //Header file deleted //#define _CRT_SECURE_NO_WARNINGS 1 //#include "stack.h" void STInit(ST* pst) { pst->a = NULL; pst->top = 0;//The next top element of the stack pst->capacity = 0; } void STPush(ST* pst, STDataType x) { //Determine whether to increase the capacity if (pst->top == pst->capacity) { int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newCapacity; } pst->a[pst->top] = x; pst->top++; } void STPop(ST* pst) { //Empty cannot be deleted assert(pst); assert(!STEmpty(pst)); pst->top--; } STDataType STTop(ST* pst) { assert(pst); assert(!STEmpty(pst)); return pst->a[pst->top - 1]; } bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; } int STSize(ST* pst) { assert(pst); return pst->top; } void STDestory(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->capacity = pst->top = 0; }
Code implementation
bool isValid(char * s){
ST st;//Create a stack
STInit( & amp;st);//Initialize the stack
while(*s!='\0'){//discrimination process
char tmp= *s;//Take out a character for judgment
if(tmp=='('||tmp=='['||tmp=='{'){//The left bracket is pushed onto the stack
STPush( &st,tmp);
s++;
}
else{//Right parenthesis, remove the top element of the stack, and compare (the premise is that there is data in the stack, so it must be judged as empty here)
//The stack is empty, it must not match, return false
if(STEmpty( &st)){
STDestory( & amp;st);//It is best to destroy the stack before returning, and the following steps are also
return false;
}
else{//The stack is not empty, take out the top element of the stack, match
STDataType top= STTop( &st);
if(top=='(' & &tmp==')'||
top=='[' & &tmp==']'||
top=='{' & &tmp=='}')
{
STPop( & amp;st);//Match, pop out the top element of the stack, and let s ++ find the next character
s++;
}
else{//does not match, return false directly
STDestory( &st);
return false;
}
}
}
}
bool ret=STEmpty( & amp;st);//true indicates that the stack is empty and also indicates that the brackets are matched
//false indicates that the stack is not empty and also indicates that the brackets do not match
STDestory( &st);
//The stack is not empty, does not match, the stack is empty, matches
return ret;
}
code analysis,
First create a stack and initialize it.
Next get a character from the string.
If it is a left parenthesis, push it onto the stack.
If it is a closing bracket, it means to match.
But first of all, it is necessary to judge whether the stack is empty. If it is empty, it means that it does not match (there is no element in the stack that matches it).
If it is not empty, take out the top element of the stack and judge whether it matches. If it matches, continue to the next match. If it does not match, return false.
Finally, if the while exits, we have to check whether the stack is empty, if it is empty, it returns true, if it is not empty, it returns false.
The overall logic of the code is like this, let’s take a look at the results.
Our code can be passed, which means that there is no problem with the realization of the stack and the way of solving the problem! ! !
The above is my understanding and analysis of the implementation of the stack. If the article is helpful to you, please give the blogger a little attention and like it,
The blog will continue to be updated in the future, and the next time will be the implementation of the queue and related exercises! !
! ! See you next time! !
If you need the source code, you can go to the blogger’s warehouse to pick it up~~
test_5_19 Qiqi loves to knock on code/test_c – Code Cloud – Open Source China (gitee.com)
