The column is used to write the basic code definitions and algorithm problems of each data structure, which is convenient for sorting out ideas.
The algorithm questions in this article are mainly encountered during personal learning. Because some of them correspond in LeetCode, the question number is attached for reference & only for personal ideas. If you want to brainstorm, you can look at the solution according to the question number
Both stack and queue are linear tables, which only stipulate that the stack can only be inserted / deleted at one end, and the queue can only be inserted at one end (tail of the queue) and deleted at the other end (head of the queue)
According to the storage (physical) structure: the stack is divided into sequential stack and chain stack, and the queue is divided into sequential team and chain team
Note: in the book data structure and algorithm analysis - C language description, table, stack and queue are in the same chapter
Stack
Basic operations – initialization and stack in / out (sequence table & non function)
The setting of the top value depends on one element: whether it refers to the current storable location. It is initialized to - 1 (understood as pointing to the top element of the stack) or 0.
When top = -1
top = -1; /* initialization */ s[++top] = val; /* val Push */ val = s[top--]; /* Out of stack */
When top = 0
top = 0; /* initialization */ s[top++] = val; /* Push */ val = s[--top]; /* Out of stack */
Structure definition (sequence table)
typedef struct Stack{
int capacity; /* storage capacity */
int top;
int *array; /* Arrays defined as pointers rather than fixed size can be allocated according to the actual situation in the program, which is more universal */
}Stack;
Basic operation (sequence table)
void Error(char *string);
Stack *createStack(int stackSize);
int isEmpty(Stack *s);
void push(Stack *s, int val);
int pop(Stack *s);
/* Error reporting (not a basic operation, just to avoid repeating the code below) */
void Error(char *string){
fprintf(stderr, string); /* Display error message */
fprintf(stderr, "\n");
abort(); /* Termination procedure */
}
/* Create empty stack */
Stack *createStack(int stackSize){
Stack *s = (Stack *)malloc(sizeof(Stack));
if (!s) /* When s == NULL, it means that there is insufficient memory. At this time, s cannot be initialized */
Error("Insufficient space");
else{
s->capacity = stackSize;
s->top = -1;
s->array = (int *)malloc(sizeof(int) * stackSize);
if (!s->array)
Error("Insufficient space");
}
return s;
}
/* Air judgment */
int isEmpty(Stack *s){
return s->top == -1;
}
/* Push */
void push(Stack *s, int val){
// if (isEmpty(s))
// Error("stack full");
s->array[++s->top] = val; /* '->' Priority is higher than '+ +' */
}
/* Out of stack */
int pop(Stack *s){
if (isEmpty(s))
Error("Stack is empty");
return s->array[s->top--];
}
Node definition (linked list)
typedef struct StackNode{
int val;
struct StackNode *next;
}StackNode;
Basic operation (linked list)
Leading node
/* Create empty stack */
StackNode *createStack(void){
StackNode *s = (StackNode *)malloc(sizeof(StackNode));
if (!s){ /* When s == NULL, it means that there is insufficient memory. At this time, s cannot be initialized */
fprintf(stderr, "Insufficient space\n"); /* Display error message */
abort(); /* Termination procedure */
}
s->next = NULL;
return s;
}
/* Air judgment */
int isEmpty(StackNode *s){
return s->next == NULL;
}
/* Push */
void push(StackNode *s, int val){
StackNode *p = createStack();
p->val = val;
/* Use the header insertion method, so that the header node is the top pointer of the stack */
p->next = s->next;
s-next = p;
}
/* Out of stack */
int pop(StackNode *s){
StackNode *p;
if (isEmpty(s)){
fprintf(stderr, "Stack is empty\n");
abort();
}else{
p = s->next;
int val = p->val;
s->next = s->next->next;
free(p);
}
return val;
}
No lead node
/* Air judgment */
int isEmpty(StackNode *s){
return s == NULL;
}
/* Stack, usage: push (& head, Val), the declaration of head is stackenode * head (because the pointer is to be modified, the address of the head pointer should be passed, so the corresponding formal parameter in the function is declared as the pointer of the pointer)*/
void push(StackNode **s, int val){
StackNode *p = createStack();
p->val = val;
/* Head insertion */
p->next = *s;
*s = p; /* Make the head pointer point to p */
}
/* Usage: pop(&head, &val) */
int pop(StackNode **s, int *val){
StackNode *p;
if (isEmpty(s)){
return 0;
}else{
p = *s;
*val = p->val;
*s = *s->next;
free(p);
return 1;
}
}
Algorithm problem
1. Whether brackets are valid (LeetCode 20 questions)
Solution 1: enter the stack on the left and exit the stack on the right
Algorithm idea: put the left bracket into the stack and the right bracket out of the stack. If it does not match, it will be invalid
bool isValid(char * s){
int i, top;
char c;
char stack[strlen(s)];
for (i = 0, top = -1; (c = s[i]) != '\0'; i++){
/* You can use if() */
switch (c){
case '(':
case '[':
case '{':
stack[++top] = c;
break;
case ')':
if (top == -1 || stack[top--] != '(')
goto mismatch;
break;
case ']':
if (top == -1 || stack[top--] != '[')
goto mismatch;
break;
case '}':
if (top == -1 || stack[top--] != '{')
goto mismatch;
break;
default:
goto mismatch;
break;
}
}
if (top == -1)
return 1;
mismatch:
return 0;
}
2. Processing suffix expression (LeetCode 036 question)
Solution 1: stack
Algorithm idea: create a stack to retain values and calculation results. When encountering an operator, two numbers pop up. For "-" and "/", you need to distinguish the order (note that tokens is a pointer array and points to the corresponding position of the string array)
#define NUMS 0
int strToNum(char *str, int *ret);
int evalRPN(char *tokens[], int tokensSize){
/* */
int sum, product, bop, rop;
int i, top, ret, s[tokensSize];
for(i = 0, top = -1; i < tokensSize; i++){
switch (strToNum(tokens[i], &ret)){
/* It should be noted that it is wrong to process the operator first through switch(ret) and then default: to process the value, because the character is also a number, '/' is 47. When ret == 47, it will start with case '/': and cause program errors */
case NUMS:
s[++top] = ret;
break;
case '+':
sum = s[top--] + s[top--];
s[++top] = sum;
break;
case '*':
product = s[top--] * s[top--];
s[++top] = product;
break;
case '-':
rop = s[top--];
bop = s[top--];
s[++top] = bop - rop;
break;
case '/':
rop = s[top--];
bop = s[top--];
s[++top] = bop / rop;
break;
}
}
return s[top--];
}
int strToNum(char *str, int *ret){
int i, sign;
int len = strlen(str);
if(len == 1 && !isdigit(str[0])) /* len Must be equal to 1, otherwise negative numbers will be processed together, resulting in an error */
return str[0];
else {
i = 0;
sign = 1;
if (str[0] == '-'){
++i;
sign = -1;
}
for (*ret = 0; str[i] != '\0'; i++){
*ret = *ret * 10 + (str[i] - '0');
}
}
*ret = sign * *ret;
return NUMS;
}
3. Basic arithmetic unit (LeetCode 227 questions)
(handle addition, subtraction, multiplication and division of integer level, based on infix to suffix)
The idea comes from the conversion from affix to suffix in P58 of data structure and algorithm analysis - C language description
Topic Description: given a string expression s, please implement a basic calculator to calculate and return its value. Integer division preserves only the integer part.
Algorithm idea: this problem can be divided into the following four small steps
-
Handle operands in strings correctly
-
Double stack is used to record operands and operators respectively, and the idea of infix to suffix is used to pop up the stack
The idea after transfer is as follows: if the priority of the element at the top of the operator stack is not lower than the priority of the element ready to be put into the stack, first get out of the stack for operation, and repeat the above behavior until the stack is empty or encounter the element with lower priority.
This stack out order ensures that the calculation is carried out from left to right in the case of the same priority. If only the elements with lower priority than the stack in, it will be the opposite and errors will occur. If 2 * 3 / 4, the normal integer operation result is 1. If it is carried out from right to left, it is 2 * (3 / 4) = 0.
-
Correctly handle pop-up priority
-
calculation
Ps: selecting execute code in LeetCode can obtain correct results, but submitting code will cause bug s, which should be the reason for platform setting
#define NUMS 1
#define SYMBOL 0
#define END -1
int getOp(char *s, int *op); /* Handle operands in strings */
int shouldPop(int s_op, int op); /* Give pop-up signal */
int getPriority(int op); /* Get operator priority */
int compute(int lop, int rop, int operator); /* calculation */
int calculate(char * s){
int op, type, top1, top2;
int op_tmp, lop, rop;
int *operator = (int *)malloc(strlen(s) * sizeof(int));
int *operand = (int *)malloc(strlen(s) * sizeof(int));
top1 = top2 = -1;
while((type = getOp(s, &op)) != END){
switch(type){
case NUMS:
operand[++top2] = op;
break;
default:
while (top1 != -1 && shouldPop(operator[top1], op)){
op_tmp = operator[top1--];
rop = operand[top2--];
lop = operand[top2--];
operand[++top2] = compute(lop, rop, op_tmp);
}
operator[++top1] = op;
}
}
while (top1 != -1){
op_tmp = operator[top1--];
rop = operand[top2--];
lop = operand[top2--];
operand[++top2] = compute(lop, rop, op_tmp);
}
assert(top2 == 0);
return operand[top2];
}
/* If you are interested, you can check whether the calculation results are correct
int main(void){
printf("%d", calculate("3/2"));
}
*/
/* Returns the current operand and operator */
int getOp(char *s, int *op){
static int i = 0;
*op = 0;
if (s[i] == '\0')
return END;
while (isspace(s[i])) /* skip blanks */
i++;
if (!isdigit(s[i])){ /* Processing operator */
*op = s[i++];
return SYMBOL;
}
while (isdigit(s[i])){ /* Get the correct operand */
*op = *op * 10 + (s[i++] - '0');
}
return NUMS;
}
/* Returns whether the operator in the stack should pop up. Principle: compare the priority between the operator in the stack and the operator in the stack. If the priority in the stack is not lower than the operator in the stack, it will be out of the stack */
int shouldPop(int s_op, int op){
if (getPriority(s_op) >= getPriority(op)) /* You need > =, otherwise the operation order of 2 * 3 / 4 = 1 will change to 2 * (3 / 4) = 0 */
return 1;
else
return 0;
}
/* Get operator priority */
int getPriority(int op){
if (op == '+' || op == '-')
return 1;
else if (op == '*' || op == '/')
return 2;
else
return 3;
}
/* Evaluates and returns the result based on the left and right operands and operators */
int compute(int lop, int rop, int operator){
int ans;
switch(operator){
case '+':
ans = lop + rop;
break;
case '-':
ans = lop - rop;
break;
case '*':
ans = lop * rop;
break;
case '/':
ans = lop / rop;
break;
default:
abort();
break;
}
return ans;
}
queue
Queue out / in will cause the front/rear pointer to move backward, which leads to the possibility that the front/rear may reach the end of the array after a series of queue out / in, so the array is optimized into a circular array
Structure definition (sequence table)
typedef struct Queue{
int front;
int rear;
int capacity;
int *array;
}Queue;
Basic operation (sequence table)
/* Create an empty queue */
Queue *createQueue(int queueSize){
Queue *q = (Queue *)malloc(sizeof(Queue));
if (!q) /* When s == NULL, it means that there is insufficient memory. At this time, s cannot be initialized */
Error("Insufficient space");
else{
q->capacity = queueSize;
q->front = 0;
q->rear = 0;
q->array = (int *)malloc(sizeof(int) * queueSize);
if (!q->array)
Error("Insufficient space");
}
return q;
}
/* Air judgment */
int isEmpty(Queue *q){
return q->front == q->rear;
}
/* Join the team */
int enQueue(Queue *q, int val){
if ((q->rear+1) % q->capacity == q->front)
return 0;
q->array[q->rear] = val;
q->rear = (q->rear+1) % q->capacity;
return 1;
}
/* Out of the team */
int deQueue(Queue *q, int *val){
if (q->front == q->rear)
return 0;
*val = q->array[q->front];
q->front = (q->front+1) % q->capacity;
return 1;
}
Structure definition (linked list)
typedef struct Node{
int val;
struct Node *next;
}Node;
typedef struct Queue{
Node *front;
Node *rear;
}Queue;
Basic operation (linked list)
/* Create an empty team */
Queue *createQueue(void){
Queue *q = (Queue *)malloc(sizeof(Queue));
if (!q)
Error("Insufficient space");
q->rear = q->front = NULL;
return q;
}
/* Create queue node according to val */
Node *createNode(int val){
Node *p = (Node *)malloc(sizeof(Node));
if (!p)
Error("Insufficient space");
p->val = val;
p->next = NULL;
return p;
}
/* Air judgment */
int isEmpty(Queue *q){
return (q->rear == NULL || q->front == NULL); /* In fact, if empty, both are NULL */
}
/* Join the team */
void enQueue(Queue *q, int val){
Node *node;
node = createNode(val);
if (isEmpty(q)) /* When null, two pointers need to be processed */
q->rear = q->front = node;
else{
q->rear->next = node;
q->rear = node;
}
}
/* Out of the team */
int deQueue(Queue *q, int *val){
Node *tmp;
if (isEmpty(q))
return 0;
tmp = q->front;
if (q->front == q->rear) /* If there is only one element left in the queue */
q->front = q->rear = NULL;
else
q->front = q->front->next;
*val = tmp->val;
free(tmp);
return 1;
}