算法开启队列实现栈 用队列实现栈

发表于

「这是我参与11月更文挑战的第29天，活动详情查看：2021最后一次更文挑战」

用队列实现栈

题目

image-20211101211340400

栈结构体

1
2
3
4
c复制代码typedef struct {
    Queue q1;
    Queue q2;//两个队列
} MyStack;

栈初始化

1
2
3
4
5
6
c复制代码MyStack* myStackCreate() {
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}

入“栈”

1
2
3
4
5
6
7
8
9
10
c复制代码void myStackPush(MyStack* obj, int x) {
    if(!QueueErase(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else//两个都为空时push给q2
    {
        QueuePush(&obj->q2,x);
    }
}

出“栈”并取栈顶元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
C复制代码int myStackPop(MyStack* obj) {
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;//假设q2空，q1非空
    //不是我们就互换位置
    if(!QueueErase(emptyQ))
    {
        nonemptyQ = &obj->q1;
        emptyQ = &obj->q2;
    }
    //非空队长大于一时朝空队里面挪动数据
    while(QueueSize(nonemptyQ)>1)
    {
        //把非队空的对头数拿出push给对空的
        QueuePush(emptyQ,QueueFront(nonemptyQ));
        //然后把非队空的对头数pop掉
        QueuePop(nonemptyQ);
    }
    //因为要返回栈顶数据所以存完再pop
    int tmp = QueueFront(nonemptyQ);
    //此时非空队就只还有一个数据，pop掉就行
    QueuePop(nonemptyQ);
    return tmp;
}

取栈顶元素

1
2
3
4
5
6
7
8
9
10
11
c复制代码int myStackTop(MyStack* obj) {
    //谁不为空就去谁队尾数据
    if(!QueueErase(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

判断栈空

1
2
3
c复制代码bool myStackEmpty(MyStack* obj) {
    return QueueErase(&obj->q1)&&QueueErase(&obj->q2);
}

栈销毁

1
2
3
4
5
c复制代码void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

image-20211102002834360

栈代码（接口代码去我上面文章取） 算法开启小码农队列血脉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
c复制代码
typedef struct {
    Queue q1;
    Queue q2;//两个队列
} MyStack;


MyStack* myStackCreate() {
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}

void myStackPush(MyStack* obj, int x) {
    if(!QueueErase(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else//两个都为空时push给q2
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;//假设q2空，q1非空
    //不是我们就互换位置
    if(!QueueErase(emptyQ))
    {
        nonemptyQ = &obj->q1;
        emptyQ = &obj->q2;
    }
    //非空队长大于一时朝空队里面挪动数据
    while(QueueSize(nonemptyQ)>1)
    {
        //把非队空的对头数拿出push给对空的
        QueuePush(emptyQ,QueueFront(nonemptyQ));
        //然后把非队空的对头数pop掉
        QueuePop(nonemptyQ);
    }
    //因为要返回栈顶数据所以存完再pop
    int tmp = QueueFront(nonemptyQ);
    //此时非空队就只还有一个数据，pop掉就行
    QueuePop(nonemptyQ);
    return tmp;
}

int myStackTop(MyStack* obj) {
    //谁不为空就去谁队尾数据
    if(!QueueErase(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

bool myStackEmpty(MyStack* obj) {
    return QueueErase(&obj->q1)&&QueueErase(&obj->q2);
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%