剑指offer刷题1——栈与队列

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

难度 简单

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTaildeleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,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);
*/