2. 栈和队列_牛客博客

文章目录

2.1 栈

2.1.1 栈的顺序存储

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 10

typedef struct {
   
    int data[MaxSize];  // 存储栈元素的静态数组
    int top;    // 栈顶指针，记录的是数组下标
} SqStack;

// 初始化栈
void InitStack(SqStack *s) {
   
    s->top = -1;
}

// 判断栈是否为空
void StackEmpty(SqStack *s) {
   
    if (s->top == -1)
        printf("栈为空！\n");
    else
        printf("栈不为空！\n");
}

// 压栈(将元素x添加到栈s中)
void Push(SqStack *s, int x) {
   
    if (s->top == MaxSize - 1) {
       // top记录的是数组下标
        printf("栈已满，无法压栈！\n");
        exit(1);
    }
    s->top++;
    s->data[s->top] = x;
    printf("入栈成功！\n");
}

// 出栈
int Pop(SqStack *s) {
   
    if (s->top == -1) {
   
        printf("栈为空，无法出栈！\n");
        exit(1);
    }
    int x = s->data[s->top];
    s->top--;
    return x;
}

// 取栈顶元素
int GetTopStack(SqStack s) {
   
    if (s.top == -1) {
   
        printf("栈为空，无法出栈！\n");
        exit(1);
    }
    return s.data[s.top];
}

// 打印栈
void PrintStack(SqStack s) {
   
    while (s.top != -1) {
   
        printf("%d\n", s.data[s.top]);
        s.top--;
    }
}

int main() {
   
    SqStack s;
    InitStack(&s);
    StackEmpty(&s);
    Push(&s, 123);  // 入栈
    Push(&s, 789);
    Push(&s, 0);
    printf("栈顶元素为：%d\n", GetTopStack(s));   // 打印栈顶元素
    PrintStack(s);  // 打印栈

    printf("出栈：%d\n", Pop(&s));     // 出栈
    printf("栈顶元素为：%d\n", GetTopStack(s));   // 打印栈顶元素
    PrintStack(s);  // 打印栈
}

2.1.2 栈的链式存储

#include <stdio.h>
#include <stdlib.h>

typedef struct Snode {
   
    int data;   // 数据域
    struct Snode *next;    // 每个栈元素的指针域，指向上一个入栈的元素
} StackNode, *LinkStack;

// 初始化链栈
void InitLinkStack(LinkStack *top) {
   
    *top = (StackNode *) malloc(sizeof(StackNode));
    if (*top == NULL) {
   
        printf("分配空间失败！\n");
    } else {
   
        (*top)->next = NULL;
        printf("分配空间成功！\n");
    }
}

// 判断链栈是否为空
void LinkStackEmpty(LinkStack top) {
   
    if (top->next == NULL)
        printf("栈为空！\n");
    else
        printf("栈不为空！\n");
}

// 压栈(将元素x添加到栈s中)
void Push(LinkStack *top, int x) {
   
    StackNode *s = (StackNode *) malloc(sizeof(StackNode));
    if (s == NULL) {
   
        printf("分配空间失败！\n");
        exit(1);
    }

    s->data = x;
    s->next = (*top)->next;
    (*top)->next = s;
    printf("压栈成功！\n");
}

// 出栈
int Pop(LinkStack *top) {
   
    if ((*top)->next == NULL) {
   
        printf("栈为空，无法出栈！\n");
        exit(1);
    }
    StackNode *s = (*top)->next;    // 定义一个指针指向要出栈的元素
    int x = s->data;   // 存储要出栈的元素的数据
    (*top)->next = s->next;
    free(s);
    return x;
}

// 取栈顶元素
int GetTopStack(LinkStack top) {
   
    if (top == NULL) {
   
        printf("栈为空，无法出栈！\n");
        exit(1);
    }
    return top->next->data;
}

// 打印栈
void PrintStack(LinkStack s) {
   
    StackNode *point = s->next;
    while (point != NULL) {
   
        printf("%d\n", point->data);
        point = point->next;
    }
}

int main() {
   
    LinkStack s;    // 声明指向链栈的指针
    InitLinkStack(&s);
    LinkStackEmpty(s);
    Push(&s, 123);  // 入栈
    Push(&s, 789);
    Push(&s, 0);
    printf("栈顶元素为：%d\n", GetTopStack(s));   // 打印栈顶元素
    PrintStack(s);  // 打印栈

    printf("出栈：%d\n", Pop(&s));     // 出栈
    printf("栈顶元素为：%d\n", GetTopStack(s));   // 打印栈顶元素
    PrintStack(s);  // 打印栈
}

2.2 队列

2.2.1 队列的顺序存储 - 循环队列

以下方案的区别在于，判队空/满的条件不一样（牺牲一个存储单位/增加辅助变量），队头队尾指针指向的位置不一样。

方案一：判空会牺牲掉一个空间

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 10

typedef struct {
   
    int data[MaxSize];  // 存储队列元素的静态数组
    int front, rear;    // 队头、队尾指针，记录的是数组下标
} SqQueue;

// 初始化队列
void InitQueue(SqQueue *s) {
   
    s->front = s->rear = 0;
}

// 判断队列是否为空
void EmptyQueue(SqQueue s) {
   
    if (s.front == s.rear)
        printf("队列为空！\n");
    else
        printf("队列不为空！\n");
}

// 入队(将元素x添加到队列s中)
void InQueue(SqQueue *s, int x) {
   
    if ((s->rear + 1) % MaxSize == s->front) {
       // 如果队尾指针指向的位置的下一个位置和队头指针指向的是一个位置，则队满
        printf("队列已满，无法入队！\n");
        exit(1);
    }
    s->data[s->rear] = x;   // 直接将数据存储到队尾指针指向的位置
    s->rear = (s->rear + 1) % MaxSize;  // 将队尾指针指向下一个位置（所以队尾指针指向的位置总是没有数据）
    printf("入队成功！\n");
}

// 出队
int OutQueue(SqQueue *s) {
   
    if (s->front == s->rear) {
   
        printf("队列为空，无法出队！\n");
        exit(1);
    }
    int x = s->data[s->front];
    s->front = (s->front + 1) % MaxSize;        // 让队头指针可以循环移动
    return x;
}

// 取队头元素
int GetHeadQueue(SqQueue s) {
   
    if (s.front == s.rear) {
   
        printf("队列为空，无法出队！\n");
        exit(1);
    }
    int x = s.data[s.front];
    return x;
}

// 打印队列
void PrintQueue(SqQueue s) {
   
    while (s.front != s.rear) {
   
        printf("%d\n", s.data[s.front]);
        s.front++;
    }
}

// 求队列长度
int GetQueueLength(SqQueue s) {
   
    return (s.rear - s.front + MaxSize) % MaxSize;
}

int main() {
   
    SqQueue s;
    InitQueue(&s);
    EmptyQueue(s);
    InQueue(&s, 123);  // 入队
    InQueue(&s, 789);
    InQueue(&s, 0);
    printf("队头元素为：%d\n", GetHeadQueue(s));   // 打印队头元素
    PrintQueue(s);  // 打印队列

    printf("出队：%d\n", OutQueue(&s));     // 出栈
    printf("队头元素为：%d\n", GetHeadQueue(s));   // 打印队头元素
    printf("队长：%d\n", GetQueueLength(s));
    PrintQueue(s);  // 打印对列
}

方案二：判空增加辅助变量size

在定义结构体的时候多设置一个属性size，记录插入数据的个数，这样判空条件就只需要关心size的大小了。

方案三：判空增加辅助变量flag

在定义结构体的时候多设置一个属性flag，记录当前是入队还是出队操作；如果是入队操作导致队头指针等于队尾指针，那么此时队满；如果是出队操作导致队头指针等于队尾指针，那么此时队空。

方案四

如果想要队头和队尾指针都指向当前队列的队头队尾元素，要注意初始化的时候让队尾指针指向0这个位置，让队头指针指向9这个位置；

当入队操作的时候只需要，先将队尾指针 (rear+1)%MaxSize 然后将筑据添加进去即可。

这样不会牺牲一个空间，并且让队头/尾指针实实在在的指向了队头/尾。

注意该方案的判空方式选前面的一种即可

2.2.2 队列的链式存储

带头节点

#include <stdio.h>
#include <stdlib.h>

typedef struct QNode {
   
    int data;   // 节点的数据域
    struct QNode *next;     // 节点的指针域，指向下一个节点
} QNode;

typedef struct {
   
    QNode *front;   // 队头指针
    QNode *rear;    // 队尾指针
} LinkQueue;

// 初始化链队（带头节点）
void InitQueue(LinkQueue *q) {
   
    // 初始化时 front 、rear 都指向头节点
    q->front = q->rear = (QNode *) malloc(sizeof(QNode));
    if (q->front == NULL) {
   
        printf("初始化分配空间失败！\n");
        exit(1);
    } else {
   
        printf("初始化分配空间成功！\n");
    }
    q->front->next = NULL;
}

// 判断队列是否为空
void EmptyQueue(LinkQueue q) {
   
    if (q.front == q.rear)
        printf("链队为空！\n");
    else
        printf("链队不为空！\n");
}

// 入队(将 x 添加到链队 q 中)
void InQueue(LinkQueue *q, int x) {
   
    QNode *s = (QNode *) malloc(sizeof(QNode));
    if (s == NULL) {
   
        printf("添加数据分配空间失败！\n");
        exit(1);
    }
    s->data = x;
    s->next = NULL;
    q->rear->next = s;
    q->rear = s;    // 让队尾指针指向最后一个元素
    printf("入队成功！\n");
}

// 出队
int OutQueue(LinkQueue *q) {
   
    if (q->front == q->rear) {
   
        printf("队列为空，无法出队！\n");
        exit(1);
    }
    QNode *s = q->front->next;  // 指向头节点的下一个节点
    int x = s->data;
    q->front->next = s->next;
    if (q->rear == s)   // 如果删除的是最后一个节点的话，就得修改队尾指针
        q->rear = q->front;
    free(s);
    return x;
}

// 取队头元素
int GetHeadQueue(LinkQueue q) {
   
    if (q.front == q.rear) {
   
        printf("队列为空！\n");
        exit(1);
    }
    return q.front->next->data;
}

// 打印队列(带头节点)
void PrintQueue(LinkQueue q) {
   
    QNode *s = q.front->next;
    while (s != NULL) {
   
        printf("%d\n", s->data);
        s = s->next;
    }
}

int main() {
   
    LinkQueue s;
    InitQueue(&s);
    EmptyQueue(s);
    InQueue(&s, 123);  // 入队
    InQueue(&s, 789);
    InQueue(&s, 0);
    printf("队头元素为：%d\n", GetHeadQueue(s));   // 打印队头元素
    PrintQueue(s);  // 打印队列

    printf("出队：%d\n", OutQueue(&s));     // 出栈
    printf("队头元素为：%d\n", GetHeadQueue(s));   // 打印队头元素
    PrintQueue(s);  // 打印对列
}

不带头节点

2.3 双端队列

1、两端入，两端删

2、一端入，两端删

3、两端入，一端删

常考点：栈的输出序列的合法性

2.4 栈的应用

2.4.1 括号配对

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 10
typedef struct {
   
    char data[MaxSize];   // 栈的数据域
    int top;     // 栈的头指针
} Stack;

// 初始化栈
void InitStack(Stack *s) {
   
    s->top = -1;
}

// 判断栈是否为空
int EmptyStack(Stack s) {
   
    if (s.top == -1)
        return 1;   // 返回true，即为空
    else
        return 0;   // 返回false，即不为空
}

// 入栈(将 x 添加到栈 s 中)
void Push(Stack *s, char x) {
   
    s->top++;
    s->data[s->top] = x;
    printf("入栈成功！\n");
}

// 出栈
char Pop(Stack *s) {
   
    if (EmptyStack(*s)) {
   
        printf("栈为空，无法出栈！\n");
        exit(1);
    }
    char x = s->data[s->top];
    s->top--;
    printf("出栈成功！\n");
    return x;
}

// 打印栈
void PrintStack(Stack s) {
   
    while (s.top != -1) {
   
        printf("%d\n", s.data[s.top]);
        s.top--;
    }
}

/** * 括号匹配 * @param str 存储需要配对的括号字符数组 * @param length 该字符数组的长度 * @return 返回 1-匹配成功，0-匹配失败 */
int bracketCheck(char str[], int length) {
   
    Stack s;
    InitStack(&s);  // 初始化栈
    for (int i = 0; i < length; ++i) {
   
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
     // 如果扫描到左括号就入栈
            Push(&s, str[i]);
        } else {
   
            if (EmptyStack(s))  // 如果匹配到右括号且当前栈为空
                return 0;   // 匹配失败

            char topElem = Pop(&s);     // 取出栈顶元素
            if (str[i] == ')' && topElem != '(')
                return 0;
            if (str[i] == ']' && topElem != '[')
                return 0;
            if (str[i] == '}' && topElem != '{')
                return 0;
        }
    }
    return EmptyStack(s);   // 所有括号全部匹配后，栈为空才说明匹配成功
}

int main() {
   
    char str[] = {
   '(', '(', '(', '{', '{', '[', '}', '}', ')', ')', ')'};
    if (bracketCheck(str, 10)) {
   
        printf("匹配成功！\n");
    } else {
   
        printf("匹配失败！\n");
    }
}

2.4.2 表达式求值

三种算数表达式：

中缀表达式
后缀表达式（常考）
前缀表达式

1、用栈实现中缀表达式转后缀表达式

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 10
typedef struct {
   
    char data[MaxSize];   // 栈的数据域
    int top;     // 栈的头指针
} Stack;

// 初始化栈
void InitStack(Stack *s) {
   
    s->top = -1;
}

// 判断栈是否为空
int EmptyStack(Stack s) {
   
    if (s.top == -1)
        return 1;   // 返回true，即为空
    else
        return 0;   // 返回false，即不为空
}

// 入栈(将 x 添加到栈 s 中)
void Push(Stack *s, char x) {
   
    s->top++;
    s->data[s->top] = x;
    printf("入栈成功！\n");
}

// 出栈
char Pop(Stack *s) {
   
    if (EmptyStack(*s)) {
   
        printf("栈为空，无法出栈！\n");
        exit(1);
    }
    char x = s->data[s->top];
    s->top--;
    printf("出栈成功！\n");
    return x;
}

// 取栈顶元素
char GetTopStack(Stack s) {
   
    if (s.top == -1) {
   
        printf("栈为空，无法出栈！\n");
        exit(1);
    }
    return s.data[s.top];
}

// 打印栈
void PrintStack(Stack s) {
   
    while (s.top != -1) {
   
        printf("%d\n", s.data[s.top]);
        s.top--;
    }
}

/** * 用栈实现中缀表达式转后缀表达式 * * 算法思想： * 1、初始化一个栈，用于保存暂时还不能确定运算顺序的运算符 * 2、从左到右处理各个元素，直到末尾。可能遇到三种情况： * ① 遇到操作数。 * 直接加入后缀表达式。 * ②遇到界限符。 * 遇到"（"直接入栈；遇到"）”则依次弹出栈内运算符并加入后缀表达式，直到弹出"（"为止。注意："（"不加入后缀表达式。 * ③遇到运算符。 * 依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到"（"或栈空则停止。之后再把当前运算符入栈。 * 3、按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。 * * @param str 存储需要进行转换的中缀表达式 * @param length 该字符数组的长度 * @param expression 存放后缀表达式 * @return 返回转换好后的后缀表达式 */

void getPostfixNotation(char str[], int length, char expression[]) {
   
    Stack s;
    InitStack(&s);  // 初始化栈
    int point = 0;  // 记录后缀表达式的长度
    for (int i = 0; i < length; ++i) {
   
        if (str[i] != '(' && str[i] != ')' && str[i] != '+' && str[i] != '-' && str[i] != '*' &&
            str[i] != '/') {
     // 如果是int类型的数据（即操作数）
            expression[point] = str[i]; // 直接加入后缀表达式
            point++;
        }

        if (str[i] == '(') {
       // 如果匹配到'('
            Push(&s, str[i]);   // 直接入栈
        } else if (str[i] == ')') {
    // 如果匹配到')'
            int index = s.top;
            for (int j = 0; j <= index; ++j) {
   
                char c = GetTopStack(s);
                if (c != '(') {
    // 依次弹出栈内运算符并加入后缀表达式，直到弹出"（"为止
                    Pop(&s);
                    expression[point] = c;
                    point++;
                } else {
   
                    Pop(&s);    // 当遇到了'('，也要弹出
                    break;
                }
            }
        }

        if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/') {
    // 如果遇到运算符
            int index = s.top;
            for (int j = 0; j <= index; ++j) {
     // 弹出栈中优先级高于或等于当前运算符的所有运算符
                char c = GetTopStack(s);
                if (c == '(' || EmptyStack(s))
                    break;

                if (str[i] == '+' || str[i] == '-') {
   
                    if (c == '+' || c == '-') {
   
                        Pop(&s);
                        expression[point] = c;
                        point++;
                    }
                }
                if (str[i] == '*' || str[i] == '/') {
   
                    if (c == '*' || c == '/') {
   
                        Pop(&s);
                        expression[point] = c;
                        point++;
                    }
                }
            }
            Push(&s, str[i]);   // 把当前运算符入栈
        }
    }
    // 处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式
    int index = s.top;
    for (int k = index; k >= 0; --k) {
   
        if (s.data[k] == '+' || s.data[k] == '-' || s.data[k] == '*' || s.data[k] == '/') {
   
            expression[point] = s.data[k];
            point++;
        }
    }
}

int main() {
   
    char str[] = "((5/(7'-(1+1)))*3)-(2+(1+1))";
// char str[] = "1+(1+2)*2";

    char expression[50];
    getPostfixNotation(str, 9, expression);
    printf("%s", expression);
}

2、用栈实现后缀表达式的计算

①从左往右扫描下一个元素，直到处理完所有元素
②若扫描到操作数则压入栈，并回到①；否则执行③
③若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①

3、用栈实现中缀表达式的计算

①初始化两个栈，操作数栈和运算符栈
②若扫描到操作数，压入操作数栈
③若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）

2.4.3 递归

2.5 队列的应用

树的层次遍历
图的广度优先遍历