栈和队列面试题

发表于

标题：栈和队列面试题

面试题一：实现一个栈，要求实现Push(出栈)、Pop(入栈)、Min(返回最小值)的时间复杂度为O(1)

  • 解题思路：我们可以利用一个辅助栈(MinStack),用来存储最小值,在最开始的情况下两个栈同时入,当继续入栈时判断该元素是否小于或等于上一个入栈元素,若小于或等于则同时入两个栈,否则只入Stack,当出栈时用MinStack的栈顶元素和Stack栈顶元素比较,若相等则两个栈同时出栈,最后Stack的最小值就为MinStack的栈顶元素

MinStackNum.h 头文件

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
 #pragma once
 #define _CRT_SECURE_NO_DEPRECATE
 #include <stdio.h>
 #include <assert.h>
 #include <malloc.h>
 #include <stdlib.h>
 #include "Stack.h"
typedef  int DataType;
typedef struct Stack
{
	DataType  *_a;
	int _top;
	int _capacity;
}Stack;
//建立两个栈，一个辅助栈
typedef struct StackMin
{
	Stack s1;
	Stack s2;
}StackMin;
//栈的基本操作
void StackInit(Stack *p);
void StackDestroy(Stack *p);
void StackPush(Stack *p, DataType x);
void StackPop(Stack *p);
DataType StackTop(Stack *p);
int StackEmpty(Stack *p);
int StackSize(Stack *p);
//新实现StackMin操作
//初始化
void StackMinInit(StackMin *ps);
//销毁
void StackMinDestroy(StackMin *ps);
//入栈
void StackMinPush(StackMin *ps,DataType x);
//出栈
void StackMinPop(StackMin *ps);
//取栈中最小元素
int StackMinNum(StackMin *ps);

MinStackNum.c 主函数文件

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
 #include "StackM.h"
 #include "Stack.h"
//初始化
void StackMinInit(StackMin *ps)
{
	StackInit(&ps->s1);
	StackInit(&ps->s2);
}
//销毁
void StackMinDestroy(StackMin *ps)
{
	assert(ps);
	StackDestroy(&ps->s1);
	StackDestroy(&ps->s2);
}
//入栈
void StackMinPush(StackMin *ps,DataType x)
{
	assert(ps);
	StackPush(&ps->s1, x);
	if (StackSize(&ps->s1) == 1){
		StackPush(&ps->s2, StackTop(&ps->s1));
	}
	else{
		if (StackTop(&ps->s1) <= StackTop(&ps->s2)){
			StackPush(&ps->s2, StackTop(&ps->s1));
		}
	}
}
//出栈
void StackMinPop(StackMin *ps)
{
	assert(ps);
	if (StackTop(&ps->s1) >= StackTop(&ps->s2)){
		StackPop(&ps->s1);
		StackPop(&ps->s2);
	}
	elseP{
		StackPop(&ps->s1);
	}
}
//取栈中最小元素
DataType StackMinNum(StackMin *ps)
{
	assert(ps);
	return StackTop(&ps->s2);
}

MinStackNum.c 测试文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 #include "Stack.h"
 #include "StackM.h"
int main()
{
	StackMin ps;
	StackMinInit(&ps);
	StackMinPush(&ps, 5);
	StackMinPush(&ps, 4);
	StackMinPush(&ps, 2);
	StackMinPush(&ps, 3);
	StackMinPush(&ps, 1);
	StackMinPop(&ps);
	printf("栈的最小值为: %d\n", StackMinNum(&ps););
	StackMinDestroy(&ps);
	system("pause");
	return 0;
}