线性表 -- 栈和队列

栈和队列都是线性表，只是规定：栈只能在一端进行插入/删除操作，队列只能在表的一端（队尾）插入，另一端（队头）删除

按存储（物理）结构：栈分为顺序栈和链式栈，队列分为顺序队和链队

注：在《数据结构与算法分析–C语言描述》这本书中，表 & 栈 & 队列是处于同一章的

文章目录

栈
- 基本操作--初始化和进/出栈（顺序表 & 非函数）
- - top = -1 时
  - top = 0 时
- 结构体定义（顺序表）
- 基本操作（顺序表）
- 节点定义（链表）
- 基本操作（链表）
- - 带头节点
  - 不带头节点
- 算法题
- - 1. 括号是否有效（ LeetCode 20题）
  - - 解法1: 遇左入栈，遇右出栈
  - 2. 处理后缀表达式（LeetCode 036题）
  - - 解法1: 栈
  - 3. 基本运算器（ LeetCode 227题）
队列
- 结构体定义（顺序表）
- 基本操作（顺序表）
- 结构体定义（链表）
- 基本操作（链表）

栈基本操作–初始化和进/出栈（顺序表 & 非函数）

top 值的设定取决于一个要素：指的是否是当前可存位置，不是就初始化为 -1（理解为指向栈顶元素），是就为 0。

top = -1 时

top = -1; 
s[++top] = val; 
val = s[top--];

top = 0 时

top = 0; 
s[top++] = val; 
val = s[--top];

结构体定义（顺序表）

typedef struct Stack{
    int capacity; 
    int top;
    int *array; 
}Stack;

基本操作（顺序表）

void Error(char *string);
Stack *createStack(int stackSize);
int isEmpty(Stack *s);
void push(Stack *s, int val);
int pop(Stack *s);


void Error(char *string){
    fprintf(stderr, string); 
    fprintf(stderr, "n");
    abort(); 
}


Stack *createStack(int stackSize){
    Stack *s = (Stack *)malloc(sizeof(Stack));
    
    if (!s) 
        Error("空间不足"); 
    else{
        s->capacity = stackSize;
        s->top = -1;
        s->array = (int *)malloc(sizeof(int) * stackSize);
        if (!s->array)
			Error("空间不足"); 
    }
    return s;
}

int isEmpty(Stack *s){
    return s->top == -1;
}

void push(Stack *s, int val){
//    if (isEmpty(s))
//        Error("栈满");
    s->array[++s->top] = val; 
}


int pop(Stack *s){
    if (isEmpty(s))
        Error("栈已空");
    return s->array[s->top--];
}

节点定义（链表）

typedef struct StackNode{
    int val;
    struct StackNode *next;
}StackNode;

基本操作（链表）带头节点

StackNode *createStack(void){
    StackNode *s = (StackNode *)malloc(sizeof(StackNode));
    if (!s){ 
        fprintf(stderr, "空间不足n"); 
        abort(); 
    }
    s->next = NULL;
    return s;
}


int isEmpty(StackNode *s){
    return s->next == NULL;
}


void push(StackNode *s, int val){
    StackNode *p = createStack();
	p->val = val;
    
    
    p->next = s->next;
    s-next = p;
}


int pop(StackNode *s){
   	StackNode *p;
    if (isEmpty(s)){
        fprintf(stderr, "栈为空n");
        abort();
    }else{
        p = s->next;
        int val = p->val;
        s->next = s->next->next;
        free(p);
    }
    return val;
}

不带头节点

int isEmpty(StackNode *s){
    return s == NULL;
}


void push(StackNode **s, int val){
    StackNode *p = createStack();
	p->val = val;
    
    
    p->next = *s;
    *s = p; 
}


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;
    }
}

算法题 1. 括号是否有效（ LeetCode 20题）解法1: 遇左入栈，遇右出栈

算法思路：遇到左括号将其入栈，遇到右括号出栈，若不匹配则无效

bool isValid(char * s){
    int i, top;
    char c;
    char stack[strlen(s)];

    for (i = 0, top = -1; (c = s[i]) != ''; i++){
        
        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. 处理后缀表达式（LeetCode 036题）解法1: 栈

算法思路：创建一个栈，用以保留数值以及计算结果，遇到运算符弹出两个数，对于“-”和“/”需要区分顺序（注意到tokens是指针数组，指向的是字符串数组对应的位置）

#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)){
            
            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])) 
        return str[0];
    else {
        i = 0;
        sign = 1;
        if (str[0] == '-'){
            ++i;
            sign = -1;
        }
        for (*ret = 0; str[i] != ''; i++){
            *ret = *ret * 10 + (str[i] - '0');
        }
    }
    *ret = sign * *ret;
    return NUMS;
}

3. 基本运算器（ LeetCode 227题）

（处理整数级的加减乘除，基于中缀转后缀）

思路源于《数据结构与算法分析–C语言描述》P58 中缀到后缀的转换

题目简述：给定一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分。

算法思路：本题可以拆分为以下四个小步骤

正确处理字符串中的操作数

用双栈分别记录操作数和运算符，以中缀转后缀的思路进行栈的弹出

中转后的思路为：若运算符栈顶元素的优先级不低于准备入栈元素的优先级，那么先出栈进行运算，重复上述行为直到栈空或者遇到优先级更低的元素。

这种出栈的顺序保证了同优先级情况下计算按照从左往右进行，若仅出比入栈优先级低的元素，那么则相反，而且会出现错误。如 2*3/4，正常整数运算结果为 1，若从右到左进行，则为 2 * (3 / 4) = 0。

正确处理弹出优先级

计算

Ps：在LeetCode中选择执行代码可以获取正确结果，但是提交代码会bug，应该又是平台设置原因

#define NUMS 1
#define SYMBOL 0
#define END -1

int getOp(char *s, int *op); 
int shouldPop(int s_op, int op); 
int getPriority(int op); 
int compute(int lop, int rop, int operator); 

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];
}




int getOp(char *s, int *op){
    static int i = 0;
    *op = 0;

    if (s[i] == '')
        return END;

    while (isspace(s[i])) 
        i++;

    if (!isdigit(s[i])){ 
        *op = s[i++];
        return SYMBOL;
    }

    while (isdigit(s[i])){ 
        *op = *op * 10 + (s[i++] - '0');
    }
    return NUMS;
}


int shouldPop(int s_op, int op){
    if (getPriority(s_op) >= getPriority(op)) 
        return 1;
    else
        return 0;
}


int getPriority(int op){
    if (op == '+' || op == '-')
        return 1;
    else if (op == '*' || op == '/')
        return 2;
    else
        return 3;
}


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;
}

队列

队列出/入队会使 front/rear 指针后移，这就导致经过一系列的出入队后，front/rear 可能到达数组的末尾，故将数组优化为循环数组

结构体定义（顺序表）

typedef struct Queue{
    int front;
    int rear;
    int capacity;
    int *array;
}Queue;

基本操作（顺序表）

Queue *createQueue(int queueSize){
    Queue *q = (Queue *)malloc(sizeof(Queue));
    
    if (!q) 
        Error("空间不足"); 
    else{
        q->capacity = queueSize;
        q->front = 0;
        q->rear = 0;
        q->array = (int *)malloc(sizeof(int) * queueSize);
        if (!q->array)
			Error("空间不足"); 
    }
    return q;
}


int isEmpty(Queue *q){
    return q->front == q->rear;
}


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;
}


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;
}

结构体定义（链表）

typedef struct Node{
    int val;
    struct Node *next;
}Node;

typedef struct Queue{
 	Node *front;
    Node *rear;
}Queue;

基本操作（链表）

Queue *createQueue(void){
    Queue *q = (Queue *)malloc(sizeof(Queue));
    
    if (!q)
        Error("空间不足");
    q->rear = q->front = NULL;
    return q;
}


Node *createNode(int val){
    Node *p = (Node *)malloc(sizeof(Node));
    
    if (!p)
        Error("空间不足");
    p->val = val;
    p->next = NULL;
    return p;
}


int isEmpty(Queue *q){
    return (q->rear == NULL || q->front == NULL); 
}

void enQueue(Queue *q, int val){
    Node *node;
    
    node = createNode(val);
    if (isEmpty(q)) 
        q->rear = q->front = node;
    else{
    	q->rear->next = node;
        q->rear = node;
    }
}


int deQueue(Queue *q, int *val){
    Node *tmp;
    
    if (isEmpty(q))
        return 0;
    tmp = q->front;
    if (q->front == q->rear) 
        q->front = q->rear = NULL;
    else
        q->front = q->front->next;
    
    *val = tmp->val;
	free(tmp);
    return 1;
}

线性表 -- 栈和队列

Java相关栏目本月热门文章