剑指 Offer 09. 用两个栈实现队列

难度 简单

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

1
2
3
4
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

示例 2：

1
2
3
4
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

提示：

  • 1 <= values <= 10000
  • 最多会对 appendTail、deleteHead 进行 10000 次调用

思路与题解

使用两个数组和两个top表示出两个栈，然后一个栈用来入栈和存储数据，另一个用来做队列的出队列操作。

不过笔者在写这个题的时候偷了点懒，直接使用数组和top来实现队列了。

代码

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
typedef struct {
    int top;
    int data[10000];
} CQueue;


CQueue* cQueueCreate() {
    CQueue* Queue;
    Queue = (CQueue*)malloc(sizeof(CQueue));
    Queue->top = 0;
    for(int i = 0; i < 10000; i++)
        Queue->data[i] = -1;
    return Queue;
}

void cQueueAppendTail(CQueue* obj, int value) {
    obj->data[obj->top] = value;
    obj->top++;
}

int cQueueDeleteHead(CQueue* obj) {
    int value,i;
    if( obj->top == 0 )
            value = -1;
    else
        {
            value = obj->data[0];
            for( i = 0;i < obj->top;i++ )
                obj->data[i] = obj->data[i+1];
            obj->top--;
        }
        return value;
}

void cQueueFree(CQueue* obj) {
        free(obj);
}

/**
 * Your CQueue struct will be instantiated and called as such:
 * CQueue* obj = cQueueCreate();
 * cQueueAppendTail(obj, value);
 
 * int param_2 = cQueueDeleteHead(obj);
 
 * cQueueFree(obj);
*/

剑指 Offer 30. 包含min函数的栈

难度 简单

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

提示：

  1. 各函数的调用总次数不超过 20000 次

思路与题解

在设计的堆栈里增加一个数值min来存储最小值，每次入栈和出栈都更新堆栈里的最小值

不知道为什么，最后一个测试样例一直通不过，调试了无数次终于成功了

代码

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
typedef struct {
    long min;
    int top;
    int data[10000];
} MinStack;

/** initialize your data structure here. */

MinStack* minStackCreate() {
    MinStack* Mystack;
    Mystack = (MinStack*)malloc(sizeof(MinStack));
    Mystack -> top = 0;
    Mystack -> min = 0x01<<30;
    return Mystack;
}

void minStackPush(MinStack* obj, int x) {
    obj->data[obj->top++] = x;
    if(x < obj->min)obj->min = x;
}

void minStackPop(MinStack* obj) {
    if(obj->data[obj->top-1] == obj->min)
    {
        obj->min = obj->data[0];
        for(int i = 0;i < obj->top-1; i++)
            if(obj->min > obj->data[i])obj->min=obj->data[i];
    }
    obj->top--;
}

int minStackTop(MinStack* obj) {
    return obj->data[obj->top-1];
}

int minStackMin(MinStack* obj) {
    return (int)obj->min;
}

void minStackFree(MinStack* obj) {
    free(obj);
}

/**
 * Your MinStack struct will be instantiated and called as such:
 * MinStack* obj = minStackCreate();
 * minStackPush(obj, x);
 
 * minStackPop(obj);
 
 * int param_3 = minStackTop(obj);
 
 * int param_4 = minStackMin(obj);
 
 * minStackFree(obj);
*/