面试题 03.03. 堆盘子-c语言

面试题 03.03. 堆盘子

堆盘子。设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。 进阶：实现一个popAt(int index)方法，根据指定的子栈，执行pop操作。

当某个栈为空时，应当删除该栈。当栈中没有元素或不存在该栈时，pop，popAt 应返回 -1.

示例1:

输入：
[“StackOfPlates”, “push”, “push”, “popAt”, “pop”, “pop”]
[[1], [1], [2], [1], [], []]
输出：
[null, null, null, 2, 1, -1]

示例2:

输入：
[“StackOfPlates”, “push”, “push”, “push”, “popAt”, “popAt”, “popAt”]
[[2], [1], [2], [3], [0], [0], [0]]
输出：
[null, null, null, null, 2, 1, 3]

个人觉得这题挺难的，大家很有必要学习一下。

typedef struct {
    int limit_count;
    int *stack;
    int top;
    struct StackOfPlates *next;

} StackOfPlates;


StackOfPlates* stackOfPlatesCreate(int cap) {
    StackOfPlates* obj=(StackOfPlates*)malloc(sizeof(StackOfPlates));
    obj->limit_count=cap;
    obj->stack=(int *)malloc(sizeof(int)*obj->limit_count);
    obj->top=0;
    obj->next=NULL;
    return obj;






}

void stackOfPlatesPush(StackOfPlates* obj, int val) {
    StackOfPlates* p=obj->next;
       printf("%d ",val);
       if(obj->limit_count!=0){
        if(p==NULL){
            obj->next=stackOfPlatesCreate(obj->limit_count);
            p=obj->next;
            p->stack[p->top]=val;
            p->top=p->top+1;

        }
        else{
            while(p->next!=NULL){
                p=p->next;
            }
            if(p->top<p->limit_count){
                p->stack[p->top]=val;
                p->top=p->top+1;

            }
            else{
            p->next=stackOfPlatesCreate(p->limit_count);
            p=p->next;
            p->stack[p->top]=val;
            p->top=p->top+1;

            }

        }


   }
}

int stackOfPlatesPop(StackOfPlates* obj) {
    
    StackOfPlates* p=obj->next;
    StackOfPlates* pre=obj;
    if(p==NULL){
        return -1;
    }
    while(p->next){
        pre=p;
        p=p->next;
    }
    int re=p->stack[p->top-1];
    p->top=p->top-1;
    if(p->top==0){
        pre->next=NULL;
    }
    printf("%d ",re);
    return re;
   
   


}

int stackOfPlatesPopAt(StackOfPlates* obj, int index) {
    StackOfPlates *p=obj->next;
    StackOfPlates *pre=obj;
     if(p==NULL){
            return -1;
        }
    while(index--){
        
        pre=p;
        p=p->next;
        if(p==NULL){
            return -1;
        }

    }
    int re=p->stack[p->top-1];
    p->top=p->top-1;
    if(p->top==0){
        pre->next=p->next;

    }
    return re;



}

void stackOfPlatesFree(StackOfPlates* obj) {

}

/**
 * Your StackOfPlates struct will be instantiated and called as such:
 * StackOfPlates* obj = stackOfPlatesCreate(cap);
 * stackOfPlatesPush(obj, val);
 
 * int param_2 = stackOfPlatesPop(obj);
 
 * int param_3 = stackOfPlatesPopAt(obj, index);
 
 * stackOfPlatesFree(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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127