【栈和队列】算法题 ---- 力扣（一）

typedef char SType;
typedef struct Stack {
    SType* arr;
    int size; // 栈顶
    int num;  // 空间大小
} Stack;
 
// 初始化
void STInit(Stack* ps) {
    assert(ps);
    ps->arr = NULL;
    ps->size = ps->num = 0;
}
// 判断栈是否为空
bool STEmpty(Stack* ps) {
    assert(ps);
    return ps->size == 0;
}
// 入栈
void STPush(Stack* ps, SType x) {
    assert(ps);
    // 判断空间大小是否足够
    if (ps->num <= ps->size) {
        int newnum = (ps->num == 0) ? 4 : 2 * ps->num;
        SType* tmp = (SType*)realloc(ps->arr, newnum * sizeof(Stack));
        if (tmp == NULL) {
            perror("realloc filed");
            exit(1);
        }
        ps->arr = tmp;
        ps->num = newnum;
    }
    ps->arr[ps->size++] = x;
}
// 出栈
void STPop(Stack* ps) {
    assert(ps);           // 不能传NULL
    assert(!STEmpty(ps)); // 栈不能为空
    ps->size--;
}
// 取栈顶数据
SType STtop(Stack* ps) {
    assert(ps);           // 不能传NULL
    assert(!STEmpty(ps)); // 栈不能为空
    return ps->arr[ps->size - 1];
}
// 获取栈中数据个数
int STSize(Stack* ps) {
    assert(ps);
    return ps->size;
}
// 栈的销毁
void STDesTroy(Stack* ps) {
    assert(ps);
    if (ps->arr)
        free(ps->arr);
    ps->arr = NULL;
    ps->size = ps->num = 0;
}
 
bool isValid(char* s) {
    Stack arr;
    // 初始化
    STInit(&arr);
    char* ps = s;
    while (*ps != '\0') {
        if (*ps == '(' || *ps == '[' || *ps == '{') {
            // 入栈
            STPush(&arr, *ps);
        } else {
            // 取栈顶数据
            if (STEmpty(&arr)) {
                return false;
            }
            char ch = STtop(&arr);
            if ((ch == '(' && *ps == ')') || (ch == '[' && *ps == ']') ||
                (ch == '{' && *ps == '}')) {
                STPop(&arr);
            } else {
                return false;
            }
        }
        ps++;
    }
    if (STEmpty(&arr)) // 栈为空
    {
        return true;
    }
    return false;
}

typedef int QType;
typedef struct QueueNode // 队列节结构
{
    QType data;
    struct QueueNode* next;
} QueueNode;
typedef struct Queue // 队列结构
{
    int size;         // 队列中的数据个数
    QueueNode* phead; // 队头
    QueueNode* ptial; // 队尾
} Queue;
 
// 初始化
void QueueInit(Queue* pq) {
    assert(pq);
    pq->phead = pq->ptial = NULL;
    pq->size = 0;
}
// 判断队列是否为空
bool QueueEmpty(Queue* pq) {
    assert(pq);
    return pq->size == 0;
}
// 入队列--从队尾插入数据
void QueuePush(Queue* pq, QType x) {
    assert(pq);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    newnode->data = x;
    newnode->next = NULL;
    if (QueueEmpty(pq)) // 队列为空
    {
        pq->phead = pq->ptial = newnode;
    } else { // 队列不为空
        pq->ptial->next = newnode;
        pq->ptial = newnode;
    }
    pq->size++;
}
// 出队列--从对头删除数据
void QueuePop(Queue* pq) {
    assert(pq);              // 不能传NULL
    //assert(!QueueEmpty(pq)); // 队列不能为空
    QueueNode* del = pq->phead;
    pq->phead = pq->phead->next;
    if (pq->size == 1) // 队列只有一个节点
    {
        pq->ptial = NULL;
    }
    pq->size--;
    free(del);
    del = NULL;
}
// 取队头数据
QType QueueFront(Queue* pq) {
    assert(pq);              // 不能传NULL
    //assert(!QueueEmpty(pq)); // 队列不能为空
    return pq->phead->data;
}
// 取队尾数据
QType QueueBack(Queue* pq) {
    assert(pq);              // 不能传NULL
    //assert(!QueueEmpty(pq)); // 队列不能为空
    return pq->ptial->data;
}
// 获取队列数据个数
int QueueSize(Queue* pq) {
    assert(pq); // 不能传NULL
    return pq->size;
}
// 销毁队列
void QueueDesTroy(Queue* pq) {
    assert(pq);              // 不能传NULL
    //assert(!QueueEmpty(pq)); // 队列不能为空
    QueueNode* pcur = pq->phead;
    while (pcur) {
        QueueNode* del = pcur;
        pcur = pcur->next;
        free(del);
        del = NULL;
    }
    pq->phead = pq->ptial = NULL;
    pq->size = 0;
}
 
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;
 
MyStack* myStackCreate() {
    MyStack* Qst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&Qst->q1);
    QueueInit(&Qst->q2);
    return Qst;
}
 
void myStackPush(MyStack* obj, int x) {
    // 往不为空的队列中插入数据
    if (QueueEmpty(&obj->q1)) {
        QueuePush(&obj->q2, x);
    } else {
        QueuePush(&obj->q1, x);
    }
}
 
int myStackPop(MyStack* obj) {
    // 先找到不为空的队列
    Queue* empq = &obj->q1;
    Queue* noneq = &obj->q2;
    if (!(QueueEmpty(&obj->q1))) // 如果q1不为空
    {
        empq = &obj->q2;
        noneq = &obj->q1;
    }
    //empq --  空队列
    //noneq --  非空队列
    while(QueueSize(noneq) > 1) {
        // 将noneq队列的数据导入到empq中去
        QueuePush(empq, QueueFront(noneq));
        QueuePop(noneq);
    }
    int ret = QueueFront(noneq);
    QueuePop(noneq);
    return ret;
}
 
int myStackTop(MyStack* obj) {
    if(QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q2);
    }else{
        return QueueBack(&obj->q1);
    }
}
 
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
 
void myStackFree(MyStack* obj) {
    free(obj);
    obj = NULL;
}