1. Valid brackets
This topic comes from leetcode valid parentheses
1.1 Title Description
Tips
1.1.1 interface function
bool isValid(char * s){
}
1.2 general framework
Although the array can also solve the problem, it is not very good. Some problems will appear later. We try to use the stack to solve the problem
Directly using c must be written by ourselves, because there is no library, so if we want to use c language to realize this problem, we need to write a stack by ourselves
1.2.1 ideas
The title says that there are only left or right parentheses for input, so we don't care about other input possibilities
Using the first in and last out feature of the stack, we can put all the left parenthesis types (with ({[) into the stack, and then the right parenthesis will start matching. If the matching fails, it will be false directly. If it succeeds, we will remove the top one of the stack through StackPop, and then judge whether the next one matches until the last one returns true or false
1.2.2 specific steps
First, you have to implement the stack in c language
statement
#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef char STDataType ;
struct Stack
{
STDataType* a;
int capacity; //Capacity, easy to increase capacity
int top; //Stack top
};
typedef struct Stack Stack;
void StackInit(Stack *pst);
void StackDestroy(Stack* pst);
void StackPush(Stack* pst,STDataType x);
//The nature determines the data access at the top of the stack
STDataType StackTop(Stack* pst);
void StackPop(Stack* pst);
bool StackEmpty(Stack* pst);
int StzckSize(Stack* pst);
function
void StackInit(Stack* pst)
{
assert(pst);
pst->a = NULL;
pst->top = 0;
pst->capacity = 0;
}
void StackDestroy(Stack* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->capacity = pst->top = 0;
}
void StackPush(Stack* pst,STDataType x)
{
assert(pst);
if (pst->top == pst->capacity)
{
int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;//Capacity doubled
STDataType* tmp = realloc(pst->a, sizeof(STDataType) * newCapacity);
if (tmp == NULL)
{
printf("realloc fail");
exit(-1);
}
pst->a = tmp;
pst->capacity =newCapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
STDataType StackTop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));
return pst->a[pst->top - 1];//From high subscript to low subscript
}
void StackPop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));
pst->top--;
}
bool StackEmpty(Stack* pst)
{
assert(pst);
return pst->top == 0;//Boolean to judge
}
int StzckSize(Stack* pst)
{
assert(pst);
return pst->top;//It happens to be size
}
Then build isValid(char * s)
matters needing attention:
-
In the loop, a branch should judge whether it is a left bracket or a right bracket. The left bracket enters the stack and the right bracket judges
-
Don't forget to move the s pointer forward after a branch
-
Finally, if it is empty, it indicates that it matches. If it is not empty, it indicates that it does not match. Because the last remaining one is added, it will directly return true. In fact, it should be false, so there should be a judgment in the end, which can be judged by StackEmpty
bool isValid(char * s){
Stack st;
StackInit(&st);
while(*s)
{
//Left bracket stack
//The right bracket matches the nearest one
if(*s =='['
||*s=='{'
||*s=='(')
{
StackPush(&st,*s);
++s;
}
else
{
if(StackEmpty(&st))//The description has no leading brackets
{
StackDestroy(&st);
return false;
}
char top=StackTop(&st);
if((top=='['&&*s!=']')
||(top=='('&&*s!=')')
||(top=='{'&&*s!='}'))
{
StackDestroy(&st);
return false;
}
else
{
//Matching
StackPop(&st);
++s;
}
}
}
bool ret=StackEmpty(&st);
StackDestroy(&st);
return ret;
}
1.3 overall realization
#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef char STDataType;
struct Stack
{
STDataType* a;
int capacity; //Capacity, easy to increase capacity
int top; //Stack top
};
typedef struct Stack Stack;
void StackInit(Stack *pst);
void StackDestroy(Stack* pst);
void StackPush(Stack* pst,STDataType x);
//The nature determines the data access at the top of the stack
STDataType StackTop(Stack* pst);
void StackPop(Stack* pst);
bool StackEmpty(Stack* pst);
void StackInit(Stack* pst)
{
assert(pst);
pst->a = NULL;
pst->top = 0;
pst->capacity = 0;
}
void StackDestroy(Stack* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->capacity = pst->top = 0;
}
void StackPush(Stack* pst,STDataType x)
{
assert(pst);
if (pst->top == pst->capacity)
{
int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;//Capacity doubled
STDataType* tmp = realloc(pst->a, sizeof(STDataType) * newCapacity);
if (tmp == NULL)
{
printf("realloc fail");
exit(-1);
}
pst->a = tmp;
pst->capacity =newCapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
STDataType StackTop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));
return pst->a[pst->top - 1];//From high subscript to low subscript
}
void StackPop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));
pst->top--;
}
bool StackEmpty(Stack* pst)
{
assert(pst);
return pst->top == 0;//Boolean to judge
}
bool isValid(char * s){
Stack st;
StackInit(&st);
while(*s)
{
//Left bracket stack
//The right bracket matches the nearest one
if(*s =='['
||*s=='{'
||*s=='(')
{
StackPush(&st,*s);
++s;
}
else
{
if(StackEmpty(&st))//The description has no leading brackets
{
StackDestroy(&st);
return false;
}
char top=StackTop(&st);
if((top=='['&&*s!=']')
||(top=='('&&*s!=')')
||(top=='{'&&*s!='}'))
{
StackDestroy(&st);
return false;
}
else
{
//Matching
StackPop(&st);
++s;
}
}
}
bool ret=StackEmpty(&st);
StackDestroy(&st);
return ret;
}
Summary:
This topic will be much simpler if you use c + +, because you can directly call the interface, but the c language has to implement a stack by itself, which will be more troublesome
2. Design cycle queue
This topic comes from leetcode 622. Designing circular queues
This topic may be a little deeper and more difficult
2.1 Title Description
Tips
2.1.1 interface function
typedef struct {
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
}
int myCircularQueueFront(MyCircularQueue* obj) {
}
int myCircularQueueRear(MyCircularQueue* obj) {
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
}
void myCircularQueueFree(MyCircularQueue* obj) {
}
/**
* Your MyCircularQueue struct will be instantiated and called as such:
* MyCircularQueue* obj = myCircularQueueCreate(k);
* bool param_1 = myCircularQueueEnQueue(obj, value);
* bool param_2 = myCircularQueueDeQueue(obj);
* int param_3 = myCircularQueueFront(obj);
* int param_4 = myCircularQueueRear(obj);
* bool param_5 = myCircularQueueIsEmpty(obj);
* bool param_6 = myCircularQueueIsFull(obj);
* myCircularQueueFree(obj);
*/
2.2 general framework
2.2.1 ideas
Implemented with array or linked list
To realize the circular queue, we must use the circular linked list. We can't just use the single linked list, can we? Of course, the array can also be used. The linked list is more like a ring
According to the meaning of the title, the function we want to achieve is to use the previously used space. It is required that the queue can not be inserted when it is full, but after it is not full or deleted when it is full, we can use the previous location to store data
Solve empty and full
Do we need two pointers to complete such a topic
However, with this idea, it is impossible to judge whether the circular queue is empty or full
Therefore, it is necessary to distinguish between two situations: when it is judged to be full and when it is judged to be empty
This problem is solved by clearing a location without saving data. For example, if the queue is full of four data, I only save three. Then it can be judged at this time
- The following legend shows a linked list at the top and an array at the bottom
- Full ` ` tail - > next is front`
- Empty tail==front
Then we can also implement pop and push operations at this time
Summary:
When do we usually use this circular queue?
For example, producers and consumers in the operating system
2.2.2 specific steps
We use arrays to implement it, because arrays are a little simpler than linked lists
Note that the functions implemented in the following steps still have problems, which will be solved later when finding and reporting errors. The overall implementation is the correct code
myCircularQueueCreate
typedef struct {
int * a;
int k;//How many data can the queue store at most
int front; //head
int tail; //Tail (next to tail data)
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a=(int*)malloc(sizeof(int)*(k+1));//Leave one
obj->front=0;
obj->tail=0;
obj->k=k;
return obj;
}
myCircularQueueIsEmpty
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front==obj->tail;
}
myCircularQueueIsFull
bool myCircularQueueIsFull(MyCircularQueue* obj) {
int tailNext = obj->tail + 1;
if (tailNext == obj->k + 1)//Prevent next from going out
{
tailNext = 0;
}
return tailNext == obj->front;
}
myCircularQueueEnQueue
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (myCircularQueueIsFull(obj))
{
return false;
}
else
{
obj->a[obj->tail] = value;
++obj->tail;
if (obj->tail == obj->k + 1)
{
obj->tail = 0;
}
return true;
}
}
myCircularQueueDeQueue
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))
{
return false;
}
else
{
++obj->front;
if (obj->front == obj->k + 1)
{
obj->front = 0;
}
return true;
}
}
myCircularQueueFront
int myCircularQueueFront(MyCircularQueue* obj) {
return obj->a[obj->front];
}
myCircularQueueRear
int myCircularQueueRear(MyCircularQueue* obj) {
int tailPrev = obj->tail - 1;
if (tailPrev == -1)//Prevent prev from going out
{
tailPrev = obj->k;
}
return obj->a[tailPrev];
}
myCircularQueueFree
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
2.2.3 finding error reporting problems
It indicates that the problem lies in the Front. According to the valuable input, there is no data in the circular queue before executing the Front, so the returned Front should be empty, so it indicates that this point is not considered. If it is empty, return - 1
myCircularQueueFront
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->a[obj->front] ;
}
}
Then myCircularQueueRear should be the same. Although there is no prompt, you can think of it
int myCircularQueueRear(MyCircularQueue* obj) {
int tailPrev = obj->tail - 1;
if (tailPrev == -1)//Prevent prev from going out
{
tailPrev = obj->k;
}
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->a[tailPrev];
}
}
2.3 overall realization
#include<stdbool.h>
typedef struct {
int* a;
int k;//How many data can the queue store at most
int front; //head
int tail; //Tail (next to tail data)
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a = (int*)malloc(sizeof(int) * (k + 1));//Leave one
obj->front = 0;
obj->tail = 0;
obj->k = k;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
int tailNext = obj->tail + 1;
if (tailNext == obj->k + 1)//Prevent next from going out
{
tailNext = 0;
}
return tailNext == obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (myCircularQueueIsFull(obj))
{
return false;
}
else
{
obj->a[obj->tail] = value;
++obj->tail;
if (obj->tail == obj->k + 1)
{
obj->tail = 0;
}
return true;
}
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))
{
return false;
}
else
{
++obj->front;
if (obj->front == obj->k + 1)
{
obj->front = 0;
}
return true;
}
}
int myCircularQueueFront(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->a[obj->front];
}
}
int myCircularQueueRear(MyCircularQueue* obj) {
int tailPrev = obj->tail - 1;
if (tailPrev == -1)//Prevent prev from going out
{
tailPrev = obj->k;
}
if (myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
return obj->a[tailPrev];
}
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
Summary:
The difficulty of stack and queue mainly lies in the complex structure, not in a single logic. If you write more, you will feel much better
Later, the more difficult problems of stack and queue will be implemented using c + + stl library
If the old fellow has harvested, I hope to give a key to three links. Thank you.