数据结构：栈与队列的实现及应用

Stack.c

STInit: 对栈进行初始化，该栈使用数组实现，a(数组名)，top(指向栈顶位置的下一个位置)，capacity(容量)。

#include"stack.h"
void STInit(ST* pst) {
    assert(pst);
    pst->a = NULL; //top 指向栈顶数据的下一个位置
    pst->top = 0;
    pst->capacity = 0;
}

**STPush：**将数据导入栈中，首先，将空间进行扩容（防止空间不足引起的越界访问）,并将扩容后的空间传给数组 a，然后，再于新空间进行导入数据的操作，结尾记得改变新栈的个数。

//入栈
void STPush(ST* pst, STDataType x) {
    assert(pst);
    if (pst->top == pst->capacity) {
        //扩容
        int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
        if (tmp == NULL) {
            perror("Realloc failed\n");
            exit(1);
        }
        //将扩容后的地址 (指针) 传递给 pst->a
        pst->a = tmp;
        //更新扩容后，容器的大小
        pst->capacity = newcapacity;
    }
    //将 x 插入栈中
    pst->a[pst->top] = x;
    pst->top++;
}

**STPop：**导出栈中的数据，直接传数组的实参，将其栈的个数减少一位，便导出一个数据。

//出栈
void STPop(ST* pst) {
    assert(pst);
    assert(pst->top > 0);
    pst->top--;
}

**STTop：**由于 top 指向栈顶的下一个位置，使用我们解引用 top-1 位置，也就是栈顶数据。

//取出栈的数据
STDataType STTop(ST* pst) {
    assert(pst);
    assert(pst->top > 0);
    return pst->a[pst->top - 1];
}

**STEmpty：**通过 return 返回值(bool 型)

//判空
bool STEmpty(ST* pst) {
    assert(pst);
    return pst->top == 0;
}

**STSize：**top 指向栈顶的下一个位置，对应数组的数据个数=下标 +1，top 即栈的数据个数。

//获取数据个数
int STSize(ST* pst) {
    assert(pst);
    return pst->top;
}

**STDestroy：**将栈内的数据置空或变为 0。

//销毁
void STDestroy(ST* pst) {
    assert(pst);
    free(pst->a);
    pst->a = NULL;
    pst->top = pst->capacity = 0;
}

以上便是栈的实现全部过程。

2. 队列

2.1. 队列的概念及结构

队列与栈不同的是，队列是一种只允许一端进行插入数据，另一端进行删除数据的特殊线性表。队列采取的是先进先出 FIFO(First In First Out)。入队列，在队尾上进行插入数据操作，在队头进行删除数据操作。

2.2. 队列的实现

接下来，我们使用具体的代码进行队列的实现。

queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDataType;
// 链式结构：表示队列
typedef struct QListNode {
    struct QListNode* next;
    QDataType val;
}QNode;
// 队列的结构
typedef struct Queue {
    QNode* qhead;
    QNode* qtail;
    int size;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回 0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

queue.c

QueueInit: 首先，我们使用了一个 Queue 的结构体，声明了 qhead 和 qtail 两个链表，现在，我们将其进行初始化。

// 初始化队列
void QueueInit(Queue* q) {
    assert(q);
    q->qhead = NULL;
    q->qtail = NULL;
    q->size = 0;
}

**QueuePush：**我们可以先开辟链式结构的空间，如果 qtail 尾有节点，即：先将其 next 节点的值改为 newnode，再将 qtail 节点与 newnode 节点相互连接。

// 队尾入队列
void QueuePush(Queue* q, QDataType data) {
    assert(q);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL) {
        perror("malloc failed\n");
        exit(1);
    }
    newnode->next = NULL;
    newnode->val = data;
    if(q->qtail == NULL) {
        q->qhead = q->qtail = newnode;
    } else{
        q->qtail->next = newnode;
        q->qtail = newnode;
    }
    q->size++;
}

**QueuePop：**如果队列只有一个节点即队头，那我们直接将其 free，并置为空；若节点大于一个，那我们可以创建一个 QNode*的 next 节点指向队头指向的下一个节点，然后再将队头的节点 free，再重新将队头的节点改为 next 指针指向的新节点。

// 队头出队列
void QueuePop(Queue* q) {
    assert(q);
    assert(q->size!=0);
    if (q->qhead->next == NULL) {
        free(q->qhead);
        q->qhead = q->qtail = NULL;
    } else {
        QNode* next = q->qhead->next;
        free(q->qhead);
        q->qhead = next;
    }
    q->size--;
}

以下，获取队头元素、队尾元素、队列中有效元素个数、判空函数均于栈的实现思想大体一致，在这里就不赘述了。

// 获取队列头部元素
QDataType QueueFront(Queue* q) {
    assert(q);
    assert(q->qhead);
    return q->qhead->val;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q) {
    assert(q);
    assert(q->qtail);
    return q->qtail->val;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q) {
    assert(q);
    return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回 0
int QueueEmpty(Queue* q) {
    assert(q);
    return q->size == 0;
}

**QueueDestroy：**销毁队列，我们可以采取遍历整个队列的方式，将其中的数据从头至尾进行 free。

// 销毁队列
void QueueDestroy(Queue* q) {
    assert(q);
    QNode* cur = q->qhead;
    while (cur) {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    q->qhead = q->qtail = NULL;
    q->size = 0;
}

3. 运用栈理解一道题

首先，我们已经实现好了栈，接下来，我们可以直接使用栈的函数。

对于这道题，我们应该先开辟一个栈(st),我们可以先将题目给定(s)的 '(' 、'[' 、 '{' 这三个左括号导入栈(st)中。然后，我们可以使用 STTop 取出栈(st)中的数据，进行对栈(s)的左右括号的匹配，如果匹配不成功，则返回 false，直到栈(s)为空时，过程结束。代码如下所示：

bool isValid(char* s) {
    ST st;
    STInit(&st);
    while(*s) {
        if(*s =='(' || *s == '[' || *s == '{') {
            STPush(&st,*s); //入栈：让字符串 s 的括号进入栈 st 中
        } else {
            if(STEmpty(&st)) {
                STDestroy(&st);
                return false;
            }
            char top = STTop(&st);//STtop 为取栈中数据的函数
            STPop(&st);//pst->top--;
            //检验不匹配
            if((top == '(' && *s != ')') ||(top == '[' && *s != ']') ||(top == '{' && *s != '}')) {
                STDestroy(&st);
                return false;
            }
        }
        ++s;
    }
    bool ret = STEmpty(&st);
    STDestroy(&st);
    return ret;
}

4. 使用两个队列实现一个栈

为了加深栈和队列的理解，我们来分析这道题。

依照题意，我们创建一个栈(MyStack),包含两个队列(Queue q1\q2)；

然后，我们需要为新创建的栈开辟新的空间(obj)，并将其中的两个队列 q1、q2 初始化；

设计一个函数 myStackPush，用于非空队列尾部添加数据；

在函数 myStackPop 中，我们将非空队列的 size-1 个元素移动至空队列中；

然后，使用 mytStackTop 函数取得栈顶元素；

为了检测我们实现的栈是否为空，我们可以直接使用 QueueEmpty 返回这两个队列 q1、q2；

最后，当我们释放内存的时候，我们应先将这两个队列 q1、q2 先释放，最后再释放 obj 这个指向栈(MyStack) 的指针。

大致结构如下图所示：

代码实现见下图分析：

typedef struct {
    Queue q1;
    Queue q2;//新创建的栈有两个队列 q1，q2
} MyStack;
//创建新的栈
MyStack* myStackCreate() {
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&(obj->q1));
    QueueInit(&(obj->q2));
    return obj;
}
//在非空队列尾部添加数据 x
void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&(obj->q1))) {
        QueuePush(&(obj->q1),x);
    }else{
        QueuePush(&(obj->q2),x);
    }
}
int myStackPop(MyStack* obj) {
    //假设法
    Queue* empty = &(obj->q1);
    Queue* nonEmpty = &(obj->q2);
    if(!QueueEmpty(&(obj->q1))) {
        nonEmpty = &(obj->q1);
        empty = &(obj->q2);
    }
    while(QueueSize(nonEmpty)>1)//把前 size-1 个元素导走
    {
        QueuePush(empty,QueueFront(nonEmpty));//将有非空队列的队列头部元素 导入 空队列中
        QueuePop(nonEmpty);//然后，删除非空队列的头部元素
    }
    int top = QueueFront(nonEmpty);//再取出非空队列的队头元素
    QueuePop(nonEmpty);//将非空元素的最后一个队头导出队列
    return top;//此时 top 就是最开始的最后一个数据：即栈顶数据
}
int myStackTop(MyStack* obj) {
    //判断哪个队列不为空，然后取该对队列的最后一个元素，即栈顶数据
    if(!QueueEmpty(&(obj->q1))) {
        return QueueBack(&(obj->q1));
    }else{
        return QueueBack(&(obj->q2));
    }
}
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2));//boolean empty() 如果栈是空的，返回 true；否则，返回 false
}
void myStackFree(MyStack* obj) {
    QueueDestroy(&(obj->q1));
    QueueDestroy(&(obj->q2));
    free(obj);
}
/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 * int param_2 = myStackPop(obj);
 * int param_3 = myStackTop(obj);
 * bool param_4 = myStackEmpty(obj);
 * myStackFree(obj);
 */