【数据结构】栈与队列面试题（C语言）

我们再用C语言做题时，是比较不方便的，因此我们在用到数据结构中的某些时只能手搓或者Ctrl+cv

我们这里用到的栈或队列来自栈与队列的实现

有效的括号

有效的括号，链接奉上。

解题思路：

先说结论：
因为我们是在讲栈与队列的面试题，故当然此题用栈或者队列做最为合适
但是为什么会想到使用栈与队列呢？
这就要求我们对数据结构具有比较高的熟悉度，看到题目就会想出比较恰当的应对措施，这与我们的做题程度也密不可分

利用栈的特性，当有左括号出现时，需要压栈，有右括号出现时pop出左括号进行匹配

解决完最主要的问题就可以逐步探测一些比较不容易被发现的坑点
，我会在代码实现中一步一步带大家深入

代码实现：

bool isValid(char* s) 
{
    Stack st;
    StackInit(&st);
    while(*s)
    {
        if(*s == '{' || *s == '[' || *s == '(')
        {
            StackPush(&st, *s);
        }
        else
        {
            char tmp = StackTop(&st);
            StackPop(&st);
            if(!(*s == '}' && tmp == '{'
              || *s == ']' && tmp == '['
              || *s == ')' && tmp == '('))
            {
                StackDestroy(&st);
                return false;
            }
        }
        s++;
    }
    StackDestroy(&st);
    return true;
}
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

写完之后我们提交，发现：
这就说明我们应当在加一个判断，当栈中有剩余时，说明数量不匹配

    if(StackSize(&st) > 0)
    {
        StackDestroy(&st);
        return false;
    }
1
2
3
4
5

继续提交，发现当只有一个右括号时，因为会top，而栈用又没有元素，所以报错，我们继续加一个判断

加的位置在while中的else

            if(StackSize(&st) == 0)
            {
                StackDestroy(&st);
                return false;
            }
1
2
3
4
5

完整代码：

bool isValid(char* s) 
{
    Stack st;
    StackInit(&st);
    while(*s)
    {
        if(*s == '{' || *s == '[' || *s == '(')
        {
            StackPush(&st, *s);
        }
        else
        {
            if(StackSize(&st) == 0)
            {
                StackDestroy(&st);
                return false;
            }
            char tmp = StackTop(&st);
            StackPop(&st);
            if(!(*s == '}' && tmp == '{'
             || *s == ']' && tmp == '['
             || *s == ')' && tmp == '('))
            {
                StackDestroy(&st);
                return false;
            }
        }
        s++;
    }
    if(StackSize(&st) > 0)
    {
        StackDestroy(&st);
        return false;
    }
    StackDestroy(&st);
    return true;
}
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

用队列实现栈

用队列实现栈，链接奉上

解题思路：

代码实现：

typedef struct 
{
    Queue q1;
    Queue q2;
} MyStack;


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

void myStackPush(MyStack* obj, int x) 
{
    Queue empty = obj->q1;
    if(!QueueEmpty(&empty))
        QueuePush(&obj->q1, x);
    else
        QueuePush(&obj->q2, x);
}

int myStackPop(MyStack* obj) 
{
    Queue* emptyq = &obj->q1;
    Queue* nonemptyq = &obj->q2;
    if(!QueueEmpty(emptyq))
    {
        emptyq = &obj->q2;
        nonemptyq = &obj->q1;
    }
    
    
    while(QueueSize(nonemptyq) > 1)
    {
        QueuePush(emptyq, QueueFront(nonemptyq));
        QueuePop(nonemptyq);    
    }

    int tmp = QueueFront(nonemptyq);
    QueuePop(nonemptyq);
    return tmp;
}

int myStackTop(MyStack* obj) {
    Queue* emptyq = &obj->q1;
    Queue* nonemptyq = &obj->q2;
    if(!QueueEmpty(emptyq))
    {
        emptyq = &obj->q2;
        nonemptyq = &obj->q1;
    }
    return QueueBack(nonemptyq);
}

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

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

    free(obj);
}

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

用栈实现队列

用栈实现队列

解题思路：

与上一题类似，可以将两个栈来回导，最终实现

代码实现：

typedef struct {
    Stack s1;
    Stack s2;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* ret = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&ret->s1);
    StackInit(&ret->s2);
    return ret;
}

void myQueuePush(MyQueue* obj, int x) {
    if(!(StackEmpty(&obj->s1)))
    {
        StackPush(&obj->s2, x);
    }
    else
    {
        StackPush(&obj->s1, x);
    }
}

int myQueuePop(MyQueue* obj) {
    MyQueue* emptys = &obj->s1; 
    MyQueue* nonemptys = &obj->s2; 

    if(!StackEmpty(&obj->s1))
    {
        emptys = &obj->s2; 
        nonemptys = &obj->s1; 
    }
    
    while(StackSize(nonemptys) > 1)
    {
        StackPush(emptys, StackTop(nonemptys));
        StackPop(nonemptys);
    }
    int ret = StackTop(nonemptys);
    StackPop(nonemptys);

    while(StackSize(emptys))
    {
        StackPush(nonemptys, StackTop(emptys));
        StackPop(emptys);
    }

    return ret;
}

int myQueuePeek(MyQueue* obj) {
    MyQueue* emptys = &obj->s1; 
    MyQueue* nonemptys = &obj->s2; 

    if(!StackEmpty(&obj->s1))
    {
        emptys = &obj->s2; 
        nonemptys = &obj->s1; 
    }
    
    while(StackSize(nonemptys) > 1)
    {
        StackPush(emptys, StackTop(nonemptys));
        StackPop(nonemptys);
    }
    int ret = StackTop(nonemptys);
    StackPush(emptys, StackTop(nonemptys));
    StackPop(nonemptys);

    while(StackSize(emptys))
    {
        StackPush(nonemptys, StackTop(emptys));
        StackPop(emptys);
    }

    return ret;
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->s1) && StackEmpty(&obj->s2);
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->s1);
    StackDestroy(&obj->s1);
    
    free(obj);
}

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

遇到问题可以及时与博主沟通，定知无不言，言无不尽