数据结构-栈与队列

栈

1. 是只允许在一端进行插入或者删除的线性表

   每接触一种新的数据结构，要从其逻辑结构，存储结构，运算三方面着手。

2. n个不同元素进栈，出栈的方式有卡特兰数个。

栈的顺序存储方式

#define Max 100
typedef struct Stack{
    ELementType data[Max];
    int top;
}SqStack;

栈空：S.top=-1。栈满：S.top==Max-1。或者分别为0与Max。

顺序栈的基本操作

1. 初始化（设置top值）
2. 入栈
3. 出栈
4. 读栈顶元素
5. 判断空栈
6. 销毁栈

队列

1. 队头：出队列的一端
2. 队尾：入队列的一段

顺序队列的存储方式

#define Max 100
#define element int
typedef struct Queue{
    element data[Max];
    int front,rear;
}SeQueue;

顺序队列的基本操作

1. 初始化：front与rear都为0
2. 判空
3. 插入：尾指针加一
4. 删除：头指针加一
5. 读取队头元素

顺序队列的假溢出问题

即是q.rear==Max时并不能说明为空

循环队列

1. 初始化：q.front = q.rear = 0
2. 判空：牺牲一个单元，(q.rear+1)%Max == q.front
3. 入队：q.rear = (q.rear+1)%Max
4. 出队：q.front = (q.front+1)%Max
5. 队列长度：(q.rear+Max-q.front)%Max

队列的链式存储结构

1. 存储类型

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct {
    struct LinkNode *front,*rear;
}LinkQueue;

2. 操作（均带有头结点）

• 初始化

LinkQueue InitQueue(LinkQueue *q){
    q->front = q->rear = (LinkNode*)malloc(sizeof(LinkNode));
    q->front->next = NULL;
}

课本上使用了C++语言，这里讨论下点运算符与箭头运算符

//当 q 是一个对象（即变量本身）时，使用点运算符 . 来访问其成员。
//当 q 是一个指针（即指向对象的指针）时，使用箭头运算符 -> 来访问其成员。
//两者的关系：q->front 等价于 (*q).front
#include <iostream>
struct LinkNode {
    int data;
    LinkNode* next;
};

struct LinkQueue {
    LinkNode* front;
    LinkNode* rear;
};

int main() {
    // 场景 1：q 是一个对象
    LinkQueue q; // q 是对象
    q.front = nullptr; // 使用 . 访问成员
    q.rear = nullptr;

    // 场景 2：q 是一个指针
    LinkQueue* qPtr = new LinkQueue(); // qPtr 是指针
    qPtr->front = nullptr; // 使用 -> 访问成员
    qPtr->rear = nullptr;

    // 场景 3：解引用指针后使用 .
    (*qPtr).front = nullptr; // 等价于 qPtr->front = nullptr;

    std::cout << "q.front: " << q.front << std::endl;
    std::cout << "qPtr->front: " << qPtr->front << std::endl;

    delete qPtr; // 释放动态分配的内存
    return 0;
}

• 判空

#include <stdbool.h>
bool IsEmpty(LinkQueue *q){
    if(q->front == q->rear){
        return true;
    }else{
        return false;
    }
}

• 入队

void InQueue(LinkQueue *q,element x){//是element x，而非LinkNode x
    LinkNode p = (LinkNode*)malloc(sizeof(LinkNode));
    p->data = x;
    p->next = NULL;
    q->rear->next = p;
    q->rear = p;
}

• 出队

bool OutQueue(LinkQueue *q,element *x){
    if(q->front == q->rear){
        return false;
    }
    LinkNode *p = q->front->next;
    x = p->data;
    q->front->next = p->next;
    if(p == q->rear){
        q->front = q->rear;
    }//只有一个结点，这样做的目的是使之删除后符合队列为空的条件
    free(p);
}

双端队列与输入或输出受限的双端队列

经典括号匹配算法

#include <stdbool.h>
#include <stdio.h>
typedef struct {
    char data[30];
    int top;
}SeStack;

void InitStack(SeStack* s) {
    s->top = -1;
}//注意

bool IsEmpty(SeStack *s) {
    if (s->top == -1) {
        return true;
    }
    else {
        return false;
    }
}

bool EnStack(SeStack* s, char x) {
    if (s->top == 29) {
        return false;
    }
    s->data[++(s->top)] = x;
    return true;
}

bool DeStack(SeStack* s, char* x) {
    if (IsEmpty(s)) {
        return false;
    }
    *x = s->data[(s->top)--];//注意*x
    return true;
}

bool Compare(char a[]) {
    SeStack s;
    InitStack(&s);
    char* ptr = a;
    while (*ptr != '\0') {
        if (*ptr == '[' || *ptr == '{') {
            EnStack(&s, *ptr);
        }
        else if (*ptr == ']' || *ptr == '}') {
            char temp;
            if (!DeStack(&s, &temp)) {//注意条件
                return false;
            }
            if (temp == '{' && *ptr != '}' ||temp == '[' && *ptr != ']') {
                    return false;
                }
            }
        ptr++;
    }
    return IsEmpty(&s);
}
int main(void) {
    printf("%d", Compare("{{}}"));
}