学习了一下新的一个大型一点的写法
登录 / 注册
标签搜索
侧边栏壁纸
博主昵称
小菩提

  • 累计撰写 92 篇文章
  • 累计收到 11 条评论
C/C++

学习了一下新的一个大型一点的写法

haimian
haimian
2024-11-26 / 2 评论 / 24 阅读 / 正在检测是否收录...
温馨提示：
本文最后更新于2024年11月26日，已超过144天没有更新，若内容或图片失效，请留言反馈。
  1. 用队列实现栈
    请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

代码如下


#define LEN 20
typedef struct queue {
    int *data;
    int head;
    int rear;
    int size;
} Queue;

typedef struct {
    Queue *queue1, *queue2;
} MyStack;

Queue *initQueue(int k) {
    Queue *obj = (Queue *)malloc(sizeof(Queue));
    obj->data = (int *)malloc(k * sizeof(int));
    obj->head = -1;
    obj->rear = -1;
    obj->size = k;
    return obj;
}

void enQueue(Queue *obj, int e) {
    if (obj->head == -1) {
        obj->head = 0;
    }
    obj->rear = (obj->rear + 1) % obj->size;
    obj->data[obj->rear] = e;
}

int deQueue(Queue *obj) {
    int a = obj->data[obj->head];
    if (obj->head == obj->rear) {
        obj->rear = -1;
        obj->head = -1;
        return a;
    }
    obj->head = (obj->head + 1) % obj->size;
    return a;
}

int isEmpty(Queue *obj) {
    return obj->head == -1;
}

MyStack *myStackCreate() {
    MyStack *obj = (MyStack *)malloc(sizeof(MyStack));
    obj->queue1 = initQueue(LEN);
    obj->queue2 = initQueue(LEN);
    return obj;
}

void myStackPush(MyStack *obj, int x) {
    if (isEmpty(obj->queue1)) {
        enQueue(obj->queue2, x);
    } else {
        enQueue(obj->queue1, x);
    }
}

int myStackPop(MyStack *obj) {
    if (isEmpty(obj->queue1)) {
        while (obj->queue2->head != obj->queue2->rear) {
            enQueue(obj->queue1, deQueue(obj->queue2));
        }
        return deQueue(obj->queue2);
    }
    while (obj->queue1->head != obj->queue1->rear) {
        enQueue(obj->queue2, deQueue(obj->queue1));
    }
    return deQueue(obj->queue1);
}

int myStackTop(MyStack *obj) {
    if (isEmpty(obj->queue1)) {
        return obj->queue2->data[obj->queue2->rear];
    }
    return obj->queue1->data[obj->queue1->rear];
}

bool myStackEmpty(MyStack *obj) {
    if (obj->queue1->head == -1 && obj->queue2->head == -1) {
        return true;
    }
    return false;
}

void myStackFree(MyStack *obj) {
    free(obj->queue1->data);
    obj->queue1->data = NULL;
    free(obj->queue1);
    obj->queue1 = NULL;
    free(obj->queue2->data);
    obj->queue2->data = NULL;
    free(obj->queue2);
    obj->queue2 = NULL;
    free(obj);
    obj = NULL;
}

解释如下
m3ym26rb.png

以下是对这段代码的详细解释：

1. 宏定义和结构体定义

#define LEN 20

这行代码定义了一个宏 LEN，其值为 20。在后续代码中，这个宏可以被用来表示一个固定的长度值，例如用于初始化队列的容量等，通过使用宏可以方便地在一处修改这个长度值，而不需要在多处代码中逐个修改具体的数字。

typedef struct queue {
    int *data;
    int head;
    int rear;
    int size;
} Queue;

这里定义了一个名为 Queue 的结构体。结构体中包含以下成员：

  • int *data：一个指向整数类型的指针，用于存储队列中的数据元素。
  • int head：表示队列头部的索引，用于标记队列头部元素的位置。
  • int rear：表示队列尾部的索引，用于标记队列尾部元素的位置。
  • int size：表示队列的容量大小，即可以存储的元素个数。
typedef struct {
    Queue *queue1, *queue2;
} MyStack;

定义了一个名为 MyStack 的结构体，它包含两个指向 Queue 结构体的指针 queue1 和 queue2。这个结构体将用于实现一个栈的数据结构，通过两个队列来模拟栈的操作。

2. 队列相关操作函数

2.1 initQueue 函数

Queue *initQueue(int k) {
    Queue *obj = (Queue *)malloc(sizeof(Queue));
    obj->data = (int *)malloc(k * sizeof(int));
    obj->head = -1;
    obj->rear = -1;
    obj->size = k;
    return obj;
}

这个函数用于初始化一个队列。它接受一个整数参数 k，用于指定队列的容量大小。函数内部的操作如下：

  • 首先，通过 malloc 函数动态分配内存来创建一个 Queue 结构体对象，并将其指针赋值给 obj。
  • 然后，再次使用 malloc 函数为队列的数据存储区域（data 指针所指向的区域）分配足够的内存空间，以存储 k 个整数类型的数据元素。
  • 接着，将队列的头部索引 head 和尾部索引 rear 都初始化为 -1，表示队列初始为空。
  • 最后，将队列的容量大小 size 设置为传入的参数 k，并返回初始化好的队列对象指针 obj。

2.2 enQueue 函数

void enQueue(Queue *obj, int e) {
    if (obj->head == -1) {
        obj->head = 0;
    }
    obj->rear = (obj->rear + 1) % obj->size;
    obj->data[obj->rear] = e;
}

该函数用于向队列中插入一个元素。它接受一个指向 Queue 结构体的指针 obj 和一个整数元素 e 作为参数。具体操作如下：

  • 首先，如果队列的头部索引 head 为 -1，说明队列当前为空，那么将头部索引 head 设置为 0，表示队列即将插入第一个元素。
  • 然后，通过 (obj->rear + 1) % obj->size 的方式计算新的尾部索引 rear。这种取模运算的方式实现了循环队列的效果，当队列尾部到达数组末尾时，会自动循环回到数组开头继续插入元素。
  • 最后，将传入的元素 e 存储到队列数据数组中由新的尾部索引 rear 所指向的位置。

2.3 deQueue 函数

int deQueue(Queue *obj) {
    int a = obj->data[obj->head];
    if (obj->head == obj->rear) {
        obj->rear = -1;
        obj->head = -1;
        return a;
    }
    obj->head = (obj->head + 1) % obj->size;
    return a;
}

这个函数用于从队列中删除并返回头部的元素。它接受一个指向 Queue 结构体的指针 obj 作为参数。操作步骤如下：

  • 首先，取出队列头部索引 head 所指向的数据元素，并将其存储到变量 a 中。
  • 然后，判断如果队列的头部索引 head 和尾部索引 rear 相等，说明队列中只剩下一个元素，此时将头部索引 head 和尾部索引 rear 都重新设置为 -1，表示队列再次变为空。
  • 否则，如果队列中还有多个元素，就通过 (obj->head + 1) % obj->size 的方式更新头部索引 head，使其指向下一个元素，实现删除头部元素的效果。
  • 最后，返回之前取出的头部元素 a。

2.4 isEmpty 函数

int isEmpty(Queue *obj) {
    return obj->head == -1;
}

这个函数用于判断队列是否为空。它接受一个指向 Queue 结构体的指针 obj 作为参数，通过检查队列的头部索引 head 是否为 -1 来判断队列是否为空，如果 head 为 -1，则表示队列中没有元素，函数返回 1（在C语言中，非零值表示真），否则返回 0（表示假）。

3. 栈相关操作函数

3.1 myStackCreate 函数

MyStack *myStackCreate() {
    MyStack *obj = (MyStack *)malloc(sizeof(MyStack));
    obj->queue1 = initQueue(LEN);
    obj->queue2 = initQueue(LEN);
    return obj;
}

这个函数用于创建一个模拟栈的数据结构对象。它首先通过 malloc 函数动态分配内存来创建一个 MyStack 结构体对象，并将其指针赋值给 obj。然后，分别调用 initQueue 函数初始化 obj 结构体中的两个队列 queue1 和 queue2，并将它们的指针赋值给对应的成员变量。最后，返回创建好的模拟栈对象指针 obj。

3.2 myStackPush 函数

void myStackPush(MyStack *obj, int x) {
    if (isEmpty(obj->queue1)) {
        enQueue(obj->queue2, x);
    } else {
        enQueue(obj->queue2, x);
    }
}

该函数用于向模拟栈中压入一个元素。它接受一个指向 MyStack 结构体的指针 obj 和一个整数元素 x 作为参数。函数通过检查 obj 结构体中的队列 queue1 是否为空来决定将元素压入哪个队列。如果 queue1 为空，就将元素 x 压入队列 queue2；否则，将元素 x 压入队列 queue1。

3.3 myStackPop 函数

int myStackPop(MyStack *obj) {
    if (isEmpty(obj->queue1)) {
        while (obj->queue2->head!= obj->queue2->rear) {
            enQueue(obj->queue1, deQueue(obj->queue2));
        }
        return deQueue(obj->queue2);
    }
    while (obj->queue1->head!= obj->queue1->rear) {
        enQueue(obj->queue2, deQueue(obj->queue1));
    }
    return deQueue(obj->queue1);
}

这个函数用于从模拟栈中弹出一个元素。它接受一个指向 MyStack 结构体的指针 obj 作为参数。函数首先判断队列 queue1 是否为空，如果为空，则将队列 queue2 中的元素除了最后一个之外全部转移到队列 queue1 中，然后弹出队列 queue2 的最后一个元素并返回；如果队列 queue1 不为空，则将队列 queue1 中的元素除了最后一个之外全部转移到队列 queue2 中，然后弹出队列 queue1 的最后一个元素并返回。通过这种方式实现了模拟栈的弹出操作，使得每次弹出的元素都是最后压入的元素。

3.4 myStackTop 函数

int myStackTop(MyStack *obj) {
    if (isEmpty(obj->queue1)) {
        return obj->queue2->data[obj->queue2->rear];
    }
    return obj->queue1->data[obj->queue1->rear];
}

该函数用于获取模拟栈的栈顶元素。它接受一个指向 MyStack 结构体的指针 obj 作为参数。函数通过检查队列 queue1 是否为空来决定返回哪个队列的尾部元素作为栈顶元素。如果 queue1 为空，则返回队列 queue2 的尾部元素；否则，返回队列 queue1 的尾部元素。

3.5 myStackEmpty 函数

bool myStackEmpty(MyStack *obj) {
    if (obj->queue1->head == -1 && obj->queue2->head == -1) {
        return true;
    }
    return false;
}

这个函数用于判断模拟栈是否为空。它接受一个指向 MyStack 结构体的指针 obj 作为参数。通过检查 obj 结构体中的两个队列 queue1 和 queue2 的头部索引是否都为 -1 来判断模拟栈是否为空。如果两个队列的头部索引都为 -1，则表示模拟栈中没有元素，函数返回 true；否则，返回 false。

3.6 myStackFree 函数

void myStackFree(MyStack *obj) {
    free(obj->queue1->data);
    obj->queue1->data = NULL;
    free(obj->queue1);
    obj->queue1 = NULL;
    free(obj->queue2->data);
    obj->queue2->data = NULL;
    free(obj->queue2);
    obj->queue2 = NULL;
    free(obj);
    obj = NULL;
}

这个函数用于释放模拟栈所占用的内存资源。它接受一个指向 MyStack 结构体的指针 obj 作为参数。函数首先释放两个队列 queue1 和 queue2 中数据存储区域的内存，然后将对应的 data 指针设置为 NULL，以避免悬空指针。接着，释放两个队列结构体本身的内存，并将队列指针设置为 NULL。最后，释放模拟栈结构体 MyStack 本身的内存，并将模拟栈指针 obj 设置为 NULL，确保所有相关内存都被正确释放，防止内存泄漏。

0
暂无标签
版权属于： haimian
本文链接： https://blog.wzl.icu/archives/leetcode255.html
作品采用： 《 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 》许可协议授权

评论 (2)

取消
  1. 头像
    GGBond
    Windows 10 · Google Chrome

    哥哥~~~可以教一下我吗，不知道姐姐会不会生气呀，千万不要影响你和姐姐的关系呀

    回复
    1. 头像
      爱你爱你
      Windows 7 · Google Chrome
      @ GGBond

      画图

      回复