[数据结构与算法]2022版王道数据结构算法题C语言代码实现-第3章-栈和队列

概述

这是2022版王道数据结构的第3章——栈和队列的算法大题的C语言代码实现，主要分为栈，队列和栈和队列的应用三部分。代码都经过了简单的测试，基本上不会有太大问题。
编译环境为gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0，文件目录结构如下：

ch3
├── 3-1-stack.c
├── 3-2-queue.c
├── 3-3-application.c
├── application_test.c
├── queue_test.c
└── stack_test.c

栈

代码实现

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

#define MAXDSTACKSIZE 64

typedef char ElementType;

struct LNode {
    ElementType data;
    struct LNode* next;
};
typedef struct LNode* LinkList;
typedef struct LNode* PtrToLNode;

bool judge(const char* a) {
    int count = 0;
    for (int i = 0; a[i] != '\0'; ++i) {
        if (a[i] == 'I')
            count++;
        else
            count--;
        if (count < 0) {
            return false;
        }
    }
    return count == 0;
}

//判断一个单链表中的字符数据元素是否对称
bool isSymmetry(LinkList l, int n) {
    //空表姑且都认为是对称的
    if (l == NULL || l->next == NULL || l->next->next == NULL)
        return true;
    LinkList p = l->next;
    char* stk = (char*)malloc(sizeof(char) * (n / 2));
    int sp = -1;
    for (int i = 0; i < n / 2; ++i) {
        stk[++sp] = p->data;
        p = p->next;
    }
    if (n & 1)
        p = p->next;
    while (p != NULL) {
        if (p->data != stk[sp])
            return false;
        sp--;
        p = p->next;
    }
    free(stk);
    //stk中没有剩余元素，方对称
    return sp == -1;
}

//用一个数组实现双栈的操作集
struct DStackNode {
    int data[MAXDSTACKSIZE];
    int top0;
    int top1;
};
typedef struct DStackNode* DStack;

DStack CreateDStack() {
    DStack s = (DStack)malloc(sizeof(struct DStackNode));
    s->top0 = -1;
    s->top1 = MAXDSTACKSIZE;
    return s;
}

void DestoryDStack(DStack s) {
    if (s != NULL)
        free(s);
}

bool Push_DStack(DStack s, int index, int x) {
    if (s == NULL)
        return false;
    if (index != 0 && index != 1)
        return false;
    if (s->top1 - s->top0 == 1)
        return false;
    if (index == 0) {
        s->data[++s->top0] = x;
    } else {
        s->data[--s->top1] = x;
    }
    return true;
}

bool Pop_DStack(DStack s, int index, int* x) {
    if (s == NULL)
        return false;
    if (index != 0 && index != 1)
        return false;

    if (index == 0) {
        if (s->top0 == -1) {
            return false;
        } else {
            *x = s->data[s->top0--];
            return true;
        }
    } else {
        if (s->top1 == MAXDSTACKSIZE) {
            return false;
        } else {
            *x = s->data[s->top1++];
            return true;
        }
    }
}

测试代码

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

#include "3-1-stack.c"

LinkList initLinkListFromArray(ElementType* A, int arraySize) {
    LinkList l = (LinkList)malloc(sizeof(struct LNode));
    l->data = A[arraySize - 1];
    l->next = NULL;

    for (int i = arraySize - 2; i >= 0; --i) {
        PtrToLNode p = (PtrToLNode)malloc(sizeof(struct LNode));
        p->data = A[i];
        p->next = l;
        l = p;
    }
    return l;
}

void printLinkList(LinkList l) {
    printf("\n%s:\n", __func__);
    if (l == NULL)
        return;
    while (l) {
        printf("%c ", l->data);
        l = l->next;
    }
    printf("\n");
}

void desoryLinkList(LinkList l) {
    PtrToLNode p;
    while (l) {
        p = l->next;
        free(l);
        l = p;
    }
}

void test_judge() {
    char a[4][9] = {"IOIIOIOO", "IOOIOIIO", "IOOIOIIO", "IIIOOIOO"};
    for (int i = 0; i < 4; ++i) {
        printf("\njudge a[%d]:%d\n", i, judge(a[i]));
    }
}

void test_isSymmetry() {
    printf("\n%s:\n", __func__);
    PtrToLNode head = (PtrToLNode)malloc(sizeof(struct LNode));

    char a1[] = "xyzyx";
    head->next = initLinkListFromArray(a1, 5);
    printLinkList(head->next);
    printf("\nisSymmetry:%d\n", isSymmetry(head, 5));

    a1[0] = 'a';
    head->next = initLinkListFromArray(a1, 5);
    printLinkList(head->next);
    printf("\nisSymmetry:%d\n", isSymmetry(head, 5));

    char a2[] = "xyyx";
    head->next = initLinkListFromArray(a2, 4);
    printLinkList(head->next);
    printf("\nisSymmetry:%d\n", isSymmetry(head, 4));

    a2[2] = 'a';
    head->next = initLinkListFromArray(a2, 4);
    printLinkList(head->next);
    printf("\nisSymmetry:%d\n", isSymmetry(head, 4));

    desoryLinkList(head);
}

void test_DStack() {
    DStack s = CreateDStack();
    int x;
    //偶数放入0号栈，奇数放入1号栈，直到栈满为止
    for (int i = 0; Push_DStack(s, i & 1, i); ++i)
        ;
    //打印输出0号栈
    while (Pop_DStack(s, 0, &x)) {
        printf("%d ", x);
    }
    printf("\n");
    //打印输出1号栈
    while (Pop_DStack(s, 1, &x)) {
        printf("%d ", x);
    }
    printf("\n");

    //测试1号栈
    for (int i = 0; i < 10; ++i) {
        Push_DStack(s, 1, i);
    }
    while (Pop_DStack(s, 1, &x)) {
        printf("%d ", x);
    }
    printf("\n");
    DestoryDStack(s);
}

int main(int argc, char* argv[]) {
    //test_judge();
    //test_isSymmetry();
    test_DStack();
    return 0;
}

队列

代码实现

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

#define MAXSIZE 64

//实现用tag区分队空和队满的循环队列
struct QueueWithTagNode {
    int front;
    int rear;
    int tag;
    int data[MAXSIZE];
};
typedef struct QueueWithTagNode* QueueWithTag;

QueueWithTag CreateQueueWithTag() {
    QueueWithTag q = (QueueWithTag)malloc(sizeof(struct QueueWithTagNode));
    q->front = 0;
    q->rear = 0;
    q->tag = 0;
    return q;
}

void DestoryQueueWithTag(QueueWithTag q) {
    if (q != NULL)
        free(q);
    return;
}

bool EnQueueWithTag(QueueWithTag q, int x) {
    if (q->front == q->rear && q->tag == 1)
        return false;
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAXSIZE;
    q->tag = 1;
    return true;
}

bool DeQueueWithTag(QueueWithTag q, int* x) {
    if (q->front == q->rear && q->tag == 0)
        return false;
    *x = q->data[q->front];
    q->front = (q->front + 1) % MAXSIZE;
    q->tag = 0;
    return true;
}

//先手撕一个栈和一个队列吧，不想用cpp的stl了
//栈及其操作集
struct StackNode {
    int data[MAXSIZE];
    int top;
};
typedef struct StackNode* Stack;

Stack CreateStack() {
    Stack s = (Stack)malloc(sizeof(struct StackNode));
    s->top = -1;
    return s;
}

void DestoryStack(Stack s) {
    if (s != NULL)
        free(s);
    return;
}

bool Push(Stack s, int x) {
    if (s == NULL || s->top == MAXSIZE - 1)
        return false;
    s->data[++s->top] = x;
    return true;
}

bool Pop(Stack s, int* x) {
    if (s == NULL || s->top == -1)
        return false;
    *x = s->data[s->top--];
    return true;
}

bool StackEmpty(Stack s) {
    return s->top == -1;
}

bool StackFull(Stack s) {
    return s->top == MAXSIZE - 1;
}

//队列及其操作集
struct QueueNode {
    int data[MAXSIZE];
    int front;
    int rear;
};
typedef struct QueueNode* Queue;

Queue CreateQueue() {
    Queue q = (Queue)malloc(sizeof(struct QueueNode));
    q->front = 0;
    q->rear = 0;
    return q;
}

void DestoryQueue(Queue q) {
    if (q != NULL)
        free(q);
    return;
}

bool EnQueue(Queue q, int x) {
    if (q->front == (q->rear + 1) % MAXSIZE)
        return false;
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAXSIZE;
    return true;
}

bool DeQueue(Queue q, int* x) {
    if (q->front == q->rear)
        return false;
    *x = q->data[q->front];
    q->front = (q->front + 1) % MAXSIZE;
    return true;
}

bool QueueEmpty(Queue q) {
    return q->front == q->rear;
}

bool QueueFull(Queue q) {
    return q->front == (q->rear + 1) % MAXSIZE;
}

//用一个栈和一个队列将队列中的元素逆置
void InverseQueue(Stack s, Queue q) {
    if (s == NULL || q == NULL)
        return;
    int x;
    while (!QueueEmpty(q)) {
        DeQueue(q, &x);
        Push(s, x);
    }
    while (!StackEmpty(s)) {
        Pop(s, &x);
        EnQueue(q, x);
    }
}

//用两个栈模拟一个队列
bool enQueue_2Stack(Stack s1, Stack s2, int x) {
    //s1用于入队
    int t;
    if (!StackFull(s1)) {
        //如果s1没满，直接入栈
        Push(s1, x);
        return true;
    } else {
        //如果s1满了
        if (!StackEmpty(s2)) {
            //如果s2非空，入队失败
            return false;
        } else {
            //s2为空，将s1中的所有元素转移到s2，然后将x入栈到s1
            while (!StackEmpty(s1)) {
                Pop(s1, &t);
                Push(s2, t);
            }
            Push(s1, x);
            return true;
        }
    }
}

bool deQueue_2Stack(Stack s1, Stack s2, int* x) {
    int t;
    if (!StackEmpty(s2)) {
        Pop(s2, x);
        return true;
    } else {
        if (StackEmpty(s1)) {
            return false;
        } else {
            while (!StackEmpty(s1)) {
                Pop(s1, &t);
                Push(s2, t);
            }
            Pop(s2, x);
            return true;
        }
    }
}

bool queueEmpty_2Stack(Stack s1, Stack s2) {
    return StackEmpty(s1) && StackEmpty(s2);
}

//2019年真题：设计一个链式循环队列，要求出队后元素所占的空间可以重复使用，
//即整个队列所占用的空间只增不减

typedef int ElementType;
struct LNode {
    ElementType data;
    struct LNode* next;
};
typedef struct LNode* LinkList;
typedef struct LNode* PtrToLNode;

struct Queue_cycleListNode {
    LinkList front;
    LinkList rear;
};

typedef struct Queue_cycleListNode* Queue_cycleList;

Queue_cycleList CreateQueue_cycleList() {
    Queue_cycleList q = (Queue_cycleList)malloc(sizeof(struct Queue_cycleListNode));
    q->front = (LinkList)malloc(sizeof(struct LNode));
    q->front->next = q->front;
    q->rear = q->front;
    return q;
}

void Destory_Queue_cycleList(Queue_cycleList q) {
    if (q != NULL) {
        q->rear->next = NULL;
        LinkList p = q->front;
        LinkList q;
        while (p != NULL) {
            q = p->next;
            free(p);
            p = q;
        }
        free(q);
    }
}

void enQueue_cycleList(Queue_cycleList q, int x) {
    if (q->rear->next == q->front) {
        //队满，添加节点，然后赋值
        LinkList new = (LinkList)malloc(sizeof(struct LNode));
        new->next = q->rear->next;
        q->rear->next = new;
        q->rear->data = x;
    } else {
        //队空，直接赋值
        q->rear->data = x;
    }
    q->rear = q->rear->next;
}

bool deQueue_cycleList(Queue_cycleList q, int* x) {
    if (q->front == q->rear) {
        //队空
        return false;
    } else {
        *x = q->front->data;
        q->front = q->front->next;
        return true;
    }
}

测试代码

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

#include "3-2-queue.c"

void test_QueueWithTag() {
    printf("\n%s\n", __func__);
    QueueWithTag q = CreateQueueWithTag();
    int x;
    //压满队列
    for (int i = 0; EnQueueWithTag(q, i); ++i)
        ;
    //弹空队列
    while (DeQueueWithTag(q, &x))
        printf("%d ", x);
    printf("\n\n");

    //压入1~16，遇到3的倍数弹出
    for (int i = 0; i < 16; ++i) {
        EnQueueWithTag(q, i + 1);
        if ((i + 1) % 3 == 0) {
            DeQueueWithTag(q, &x);
            printf("%d ", x);
        }
    }
    printf("\n\n");
    //弹空队列剩余元素
    while (DeQueueWithTag(q, &x))
        printf("%d ", x);
    printf("\n\n");
    DestoryQueueWithTag(q);
}

void test_InverseQueue() {
    printf("\n%s\n", __func__);
    Queue q = CreateQueue();
    Stack s = CreateStack();
    for (int i = 0; i < 16; ++i) {
        EnQueue(q, i);
    }
    InverseQueue(s, q);
    int x;
    while (DeQueue(q, &x)) {
        printf("%d ", x);
    }
    printf("\n\n");

    DestoryQueue(q);
    DestoryStack(s);
}

void test_Queue_2Stack() {
    printf("\n%s\n", __func__);
    Stack s1 = CreateStack();
    Stack s2 = CreateStack();
    int t;
    //压满队列
    for (int i = 0; enQueue_2Stack(s1, s2, i); ++i)
        ;
    //弹空队列
    while (deQueue_2Stack(s1, s2, &t)) {
        printf("%d ", t);
    }
    printf("\n\n");
    //压入1~66，逢3的倍数弹出
    for (int i = 0; i < 66; ++i) {
        enQueue_2Stack(s1, s2, i + 1);
        if ((i + 1) % 3 == 0) {
            deQueue_2Stack(s1, s2, &t);
            printf("%d ", t);
        }
    }
    printf("\n\n");

    //弹空队列剩余元素
    while (!queueEmpty_2Stack(s1, s2)) {
        deQueue_2Stack(s1, s2, &t);
        printf("%d ", t);
    }
    printf("\n\n");
    DestoryStack(s1);
    DestoryStack(s2);
}

void test_Queue_cycleList() {
    printf("\n%s\n", __func__);
    Queue_cycleList q = CreateQueue_cycleList();
    int t;
    for (int i = 0; i < 16; ++i) {
        enQueue_cycleList(q, i + 1);
        if ((i + 1) % 3 == 0) {
            deQueue_cycleList(q, &t);
            printf("%d ", t);
        }
    }
    printf("\n\n");
    while (deQueue_cycleList(q, &t)) {
        printf("%d ", t);
    }
    printf("\n\n");

    Destory_Queue_cycleList(q);
}

int main(int argc, char* argv[]) {
    test_QueueWithTag();
    test_InverseQueue();
    test_Queue_2Stack();
    test_Queue_cycleList();

    return 0;
}

栈和队列的应用

代码实现

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

#define MAXSIZE 64
//栈及其操作集
struct StackNode {
    int data[MAXSIZE];
    int top;
};
typedef struct StackNode* Stack;

Stack CreateStack() {
    Stack s = (Stack)malloc(sizeof(struct StackNode));
    s->top = -1;
    return s;
}

void DestoryStack(Stack s) {
    if (s != NULL)
        free(s);
    return;
}

bool Push(Stack s, int x) {
    if (s == NULL || s->top == MAXSIZE - 1)
        return false;
    s->data[++s->top] = x;
    return true;
}

bool Pop(Stack s, int* x) {
    if (s == NULL || s->top == -1)
        return false;
    *x = s->data[s->top--];
    return true;
}

bool StackEmpty(Stack s) {
    return s->top == -1;
}

bool StackFull(Stack s) {
    return s->top == MAXSIZE - 1;
}

//队列及其操作集
struct QueueNode {
    int data[MAXSIZE];
    int front;
    int rear;
};
typedef struct QueueNode* Queue;

Queue CreateQueue() {
    Queue q = (Queue)malloc(sizeof(struct QueueNode));
    q->front = 0;
    q->rear = 0;
    return q;
}

void DestoryQueue(Queue q) {
    if (q != NULL)
        free(q);
    return;
}

bool EnQueue(Queue q, int x) {
    if (q->front == (q->rear + 1) % MAXSIZE)
        return false;
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAXSIZE;
    return true;
}

bool DeQueue(Queue q, int* x) {
    if (q->front == q->rear)
        return false;
    *x = q->data[q->front];
    q->front = (q->front + 1) % MAXSIZE;
    return true;
}

bool QueueEmpty(Queue q) {
    return q->front == q->rear;
}

bool QueueFull(Queue q) {
    return q->front == (q->rear + 1) % MAXSIZE;
}
//括号匹配
/*
    由于上面的栈是针对int的，下面处理字符只能用ascii码了
    (-40
    )-41
    [-91
    ]-93
    {-123
    }-125
*/
bool bracketsCheck(const char* str) {
    if (str == NULL)
        return false;
    Stack s = CreateStack();
    int val = 0;
    while (*str != '\0') {
        switch (*str) {
            case '(': {
                Push(s, *str);
                break;
            }
            case '[': {
                Push(s, *str);
                break;
            }
            case '{': {
                Push(s, *str);
                break;
            }
            case ')': {
                Pop(s, &val);
                if (val != 40)
                    return false;
                break;
            }
            case ']': {
                Pop(s, &val);
                if (val != 91)
                    return false;
                break;
            }

            case '}': {
                Pop(s, &val);
                if (val != 123)
                    return false;
                break;
            }
        }
        str++;
    }
    bool ret = StackEmpty(s);
    DestoryStack(s);
    return ret;
}

void trainArrange(char* train) {
    if (train == NULL)
        return;
    Stack s = CreateStack();
    char* finished = train;
    while (*train != '\0') {
        if (*train == 'H')
            Push(s, *train);
        else
            *(finished++) = *train;
        train++;
    }
    int t;
    while (!StackEmpty(s)) {
        Pop(s, &t);
        *(finished++) = t;
    }
    DestoryStack(s);
}

//用栈计算一个递归定义的函数
int calculateRecursiveFunc(int n, int x) {
    struct stack {
        int no;
        int val;
    } stk[64];
    int top = -1;
    int fv1 = 1;
    int fv2 = 2 * x;
    //从上到下填入系数2,3,4,5...n
    for (int i = n; i >= 2; --i) {
        top++;
        stk[top].no = i;
    }
    //弹栈
    while (top != -1) {
        //计算栈顶的val值，如第一个计算P2(x)=2*x*P1(x)-2*(2-1)*P0(x)
        stk[top].val = 2 * x * fv2 - 2 * (stk[top].no - 1) * fv1;
        //更新迭代对儿
        fv1 = fv2;
        fv2 = stk[top].val;
        top--;
    }
    if (n == 0)
        return fv1;
    else
        return fv2;
}

//渡口管理
void ferryManager(Queue boat, Queue coach, Queue truck) {
    int boatCnt = 0;   //渡船上的总车辆数
    int coachCnt = 0;  //客车计数
    int x;
    //渡船未满
    while (boatCnt < 10) {
        if (!QueueEmpty(coach) && coachCnt < 4) {
            //先上4辆客车
            DeQueue(coach, &x);
            EnQueue(boat, x);
            ++coachCnt;
            ++boatCnt;
        } else if (coachCnt == 4 && !QueueEmpty(truck)) {
            //上了4辆客车了，再上一辆货车
            DeQueue(truck, &x);
            EnQueue(boat, x);
            coachCnt = 0;
            ++boatCnt;
        } else {
            //客车队列空了
            while (boatCnt < 10 && coachCnt < 4 && !QueueEmpty(truck)) {
                DeQueue(truck, &x);
                EnQueue(boat, x);
                ++coachCnt;
                ++boatCnt;
            }
            coachCnt = 0;
        }
        //检查货车和客车队列是否都空了，若是，跳出循环
        if (QueueEmpty(coach) && QueueEmpty(truck))
            break;
    }
}

测试代码

#include "3-3-application.c"

void test_bracketsCheck() {
    printf("\n%s\n", __func__);
    char s0[] = "([{}])";
    char s1[] = "()[]{}";
    char s2[] = "([{}])([])({})";
    char s3[] = "[([][])]";

    char s4[] = "([{}]]";
    char s5[] = "()[](}";
    char s6[] = "([{}])([])[{})";
    char* ss[7] = {s0, s1, s2, s3, s4, s5, s6};
    for (int i = 0; i < 7; ++i) {
        printf("\n%s\nbracketsCheck:%d\n", ss[i], bracketsCheck(ss[i]));
    }
}

void test_trainArrange() {
    printf("\n%s\n", __func__);
    char s1[] = "HHSSHSHSSH";
    char s2[] = "HHHHHHHHHHHSHSH";
    printf("\n%s\n", s1);
    trainArrange(s1);
    printf("\nafter trainArrange:%s\n", s1);

    printf("\n%s\n", s2);
    trainArrange(s2);
    printf("\nafter trainArrange:%s\n", s2);
}

void test_calculateRecursiveFunc() {
    printf("\n%s\n", __func__);
    int n = 3;
    int x = 1;
    printf("\nn=%d,x=%d,calculateRecurisiveFunc:%d\n", n, x, calculateRecursiveFunc(n, x));
}

void test_ferryManager() {
    printf("\n%s\n", __func__);
    Queue boat = CreateQueue();
    Queue coach = CreateQueue();
    Queue truck = CreateQueue();
    int i = 0;
    int x;
    for (; i < 5; ++i) {
        EnQueue(coach, 2 * i + 1);
        EnQueue(truck, 2 * i + 2);
    }
    ferryManager(boat, coach, truck);
    while (DeQueue(boat, &x)) {
        printf("%d ", x);
    }
    printf("\n\n");

    //添加一些客车，再运行一次
    for (i = 0; i < 10; ++i) {
        EnQueue(coach, 2 * i + 1);
        EnQueue(truck, 2 * i + 2);
    }
    ferryManager(boat, coach, truck);
    while (DeQueue(boat, &x)) {
        printf("%d ", x);
    }
    printf("\n\n");

    DestoryQueue(boat);
    DestoryQueue(coach);
    DestoryQueue(truck);
}

int main(int argc, char* argv[]) {
    test_bracketsCheck();
    test_trainArrange();
    test_calculateRecursiveFunc();
    test_ferryManager();

    return 0;
}