数据结构每日亿题(六)

一.用队列实现栈

原题传送门：力扣
题目：题目的意思是：给你两个队列，让你实现后入先出的操作。因为队列是先入先出，栈是后入先出，队列实现栈就是先入先出->后入先出。

2.大概思路

我们先进入四个数据顺序是1，2，3，4，但是现在我们希望它能后入先出，意味着出数据的顺序是4，3，2，1.现在的问题是队列只能从队头出数据，所以我们必须依靠第二个队列来实现功能。

因为只能从对头出数据，所以我们一个一个的将第一个队列的数据移到第二个队列中。

当我们把前三个数据都移到下个队列后，发现第一个队列只剩一个4这个元素了。现在我们把这个元素之间删掉就行。
这样我么就把最后一个元素删掉了，像这样一直循环就能把3，2，1根据这个数据一个一个删掉了。

当然此时还要新增数据的时候也不妨碍：

3.代码实现

这个题目开始会给你几个接口函数，你需要依次实现这些函数。因为我们是用的C语言来写的，没办法直接用库里的队列，这能自己写关于队列的实现的函数，这里我在之前的文章：数据结构：队列中写过，这里我就直接拷贝过来：

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

//删除
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	
	return pq->size == 0;
}

//入对列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("QueuePush");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}

//取出队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

//取出队列头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

//队列大小
QDataType QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}
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

好，接下来要正式开始写题目有关的内容

3.1

typedef struct {
    //定义两个队列
    Queue q1;
    Queue q2;
} MyStack;
1
2
3
4
5

这个接口的目的就是为了让你声明一个结构体，成员是题目需要的两个队列。这里的Queue是定义队列时自定义的结构体变量：

typedef int QDataType;

//队列的一个节点
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

//包含指向队列头和尾的两个指针和一个定义队列大小的size
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.2

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

    return obj;
}
1
2
3
4
5
6
7

这个接口的目的是为了让你定义刚才的结构体并把这个定义好的结构体地址返回出来。

QueueInit是我在队列的实现时写的接口，目的就是为了初始化队列：

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->size = 0;
}
1
2
3
4
5
6
7
8

3.3

void myStackPush(MyStack* obj, int x) {
    //将x插到一个不是空的队列中

    //如果q1不是空
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1, x);
    }
    else
    {
        QueuePush(&obj->q2, x);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

这就是插入的接口了，通过上面思路的分析，我们需要将需要插入的元素之间插入到两个队列中有元素的那个队列里。判空函数如果是空返回的就是true，不是空返回false也就是假，前面加个逻辑取反符号说明q1不是空，if条件为真，所以x插到q1中。

同样这里用到的还是我自己写的判空函数和插入函数：

//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	
	return pq->size == 0;
}

//入对列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("QueuePush");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}
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

3.4

int myStackPop(MyStack* obj) {
    //此时先假设q1这个队列是空，q2不是空
    Queue* empty = &obj->q1;
    Queue* noempty = &obj->q2;
    //如果判断错了
    if(!QueueEmpty(&obj->q1))
    {
        noempty = &obj->q1;
        empty = &obj->q2;
    }

    //走到这里时noempty指向的是一个非空链表
    //empty指向的是一个空链表

    //将非空链表的数据放到空链表中，最后只剩一个元素
    while(noempty->size != 1)
    {
        QueuePush(empty, QueueFront(noempty));
        QueuePop(noempty);
    }
    //最后非空链表还剩一个元素，直接删掉
    int tmp = QueueFront(noempty);
    QueuePop(noempty);
    return tmp;
}
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

这里用了一个办法让我们知道不管队列里的元素怎么变化，我们都能判断出哪个为空，哪个不为空。
刚开始先用两个指针，假设q1为空，q2不为空。然后通过if判断，如果正确了就不执行if里面的程序，如果我们猜错了就把，两个指针指向的队列互换。
这样我们新定义的指针就可以总是指向该指向的队列。

通过大概思路的分析，将有元素的队列里面的元素一个一个的取到没有队列的里面，在只剩一个的时候就光取出来，不放到没有元素的那个队列中。

在这里QueueFront是找到队列的对头的数据。QueuePop是取出数据：

//取出队列头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}
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

3.5

int myStackTop(MyStack* obj) {
    //如果q1不是空
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}
1
2
3
4
5
6
7
8
9
10
11

这是取出队列顶的元素的函数接口，因为我们拥有的这两个队列只有一个有元素，我们需要取出这个队列的最后一个元素。

QueueBack是我写的得到队列尾的元素的函数接口：

//取出队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}
1
2
3
4
5
6
7
8

3.6

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

判断队列是否为空，如果两个队列都为空，结果才是空。所以这里用到了逻辑与。

3.7

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}
1
2
3
4
5

这是要完成释放队列空间的函数接口，我们把最开始定义的q1,q2两个链表和obj这个结构体释放掉就可以了。

QueueDestroy也是我自己写的函数接口：

//删除
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
	pq->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二.用栈实现队列

原题传送门：力扣

题目：
这和第一题差不多，但是这里需要实现的内容相反。

2.大概思路

栈本身是后入先出，这里我们需要用两个栈来实现先入先出。
我们假设有三个元素进栈的顺序是1，2，3现在我们希望它出栈的顺序也是1，2，3.但是因为2，3这两个元素挡着，1不能直接出去，所以我们将3，2放到新的栈中：
但是现在问题来了，这和第一题不一样，这一题2，3这两个元素再进到新的栈时，顺序就反过来了。如果此时在添加一个元素呢？
我们要取出2，3，4这样做就没什么规律了。所以现在我们换一种思路，现在将两个栈分别完成进栈和出栈的任务：
像这样如果此时需要进栈的话，直接在q1这里进就行。那如果是出栈呢？我们就先看q2是否为空，如果是空的话，就把q1里的元素全部倒到q2里去：
倒过来就可以把q2的元素删掉就相当于出栈了，如果此时出完之后还想入栈也不耽误：
直接放到q1中就行。这样我们就把入栈出栈的大概思路讲明白了。

3.代码实现

同样我是用C语言来实现的，也就是说用不了C++里的栈，这里只能自己写，具体代码我在数据结构：栈中讲过了，这里我直接拷贝过来。

typedef char STDataType;
typedef struct Stack
{
	STDataType* a;
	int capacity; //栈空间大小
	int top; // 栈顶
}Stack;

// 初始化栈
void StackInit(Stack* ps)
{
	assert(ps);

	//刚开始为栈提前开辟4个元素的空间
	ps->a = (STDataType*)malloc(4 * sizeof(STDataType));
	if (ps->a == NULL)
	{
		perror("StackInit");
		exit(-1);
	}

	ps->capacity = 4;
	ps->top = 0; //这里top指向栈顶元素的下一个位置
}

//入栈
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	//在栈尾添加一个元素

	//首先判断需不需要扩容
	if (ps->capacity == ps->top)
		//相等说明此时元素个数已经和总容量相等了，如果在添加元素需要扩容
	{
		//扩容为原来的两倍
		STDataType* cap = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (cap == NULL)
		{
			perror("StackPush");
			exit(-1);
		}

		ps->a = cap;
		ps->capacity *= 2;
	}

	ps->a[ps->top] = data;
	ps->top++;
}

//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	//如果栈里面没有元素了，就不能进行出栈的操作
	assert(ps->top);

	ps->top--;
}

//检测栈是否为空，如果为空返回true，如果不为空返回false
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

//销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

//获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);

	assert(!StackEmpty(ps));
		//如果栈的数据是0的话，下面访问的就是ps->a[-1],造成数组越界访问
	return ps->a[ps->top - 1];
}

//获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->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
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

3.1

typedef struct {
    Stack q1;
    Stack q2;
} MyQueue;
1
2
3
4

这个接口是为了让我们定义两个栈，封装在一个结构体里。

3.2

MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&obj->q1);
    StackInit(&obj->q2);

    return obj;
}
1
2
3
4
5
6
7

定义一个结构体，并且初始化。StackInit是我自己写的栈的接口函数：

// 初始化栈
void StackInit(Stack* ps)
{
	assert(ps);

	//刚开始为栈提前开辟4个元素的空间
	ps->a = (STDataType*)malloc(4 * sizeof(STDataType));
	if (ps->a == NULL)
	{
		perror("StackInit");
		exit(-1);
	}

	ps->capacity = 4;
	ps->top = 0; //这里top指向栈顶元素的下一个位置
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.3

void myQueuePush(MyQueue* obj, int x) {
    //q1用来输入，q2用来输出
    //将元素放到q1中
    StackPush(&obj->q1, x);
}
1
2
3
4
5

我们规定q1这个栈是专门输入元素，q2是出元素的。这里的StackPush是我自己写的入栈的函数：

//入栈
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	//在栈尾添加一个元素

	//首先判断需不需要扩容
	if (ps->capacity == ps->top)
		//相等说明此时元素个数已经和总容量相等了，如果在添加元素需要扩容
	{
		//扩容为原来的两倍
		STDataType* cap = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (cap == NULL)
		{
			perror("StackPush");
			exit(-1);
		}

		ps->a = cap;
		ps->capacity *= 2;
	}

	ps->a[ps->top] = data;
	ps->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

3.4

int myQueuePop(MyQueue* obj) {
    //如果q2为空就把此时q1里的元素放到q2内
    if(StackEmpty(&obj->q2))
    {
        //将q1的元素放到q2中
        while(StackSize(&obj->q1))
        {
            StackPush(&obj->q2, StackTop(&obj->q1));
            StackPop(&obj->q1);
        }
    }
    //先将q2的栈顶元素保存下来，方便后来的返回
    int tmp = StackTop(&obj->q2);
    //将栈顶元素删掉
    StackPop(&obj->q2);

    return tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这是出栈，根据我们刚才讲的思路，出栈是直接在q2这个栈中出就行，但是有一种情况是元素现在都在q1中，还没有倒进q2中，所有根据这个多写一个while循环。循环的条件是q1的元素个数是否为0，不为0就把q1的元素先放到q2中，然后把q1中的这个元素删掉。
StackSize，StackEmpty，StackPop，StackTop用到的这四个函数都是我自己写的：

//获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

//检测栈是否为空，如果为空返回true，如果不为空返回false
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	//如果栈里面没有元素了，就不能进行出栈的操作
	assert(ps->top);

	ps->top--;
}

//获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);

	assert(!StackEmpty(ps));
		//如果栈的数据是0的话，下面访问的就是ps->a[-1],造成数组越界访问
	return ps->a[ps->top - 1];
}

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

3.5

int myQueuePeek(MyQueue* obj) {
    //如果q2为空就把此时q1里的元素放到q2内
    if(StackEmpty(&obj->q2))
    {
        //将q1的元素放到q2中
        while(StackSize(&obj->q1))
        {
            StackPush(&obj->q2, StackTop(&obj->q1));
            StackPop(&obj->q1);
        }
    }
    int tmp = StackTop(&obj->q2);

    return tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

获取栈顶的元素，这个函数和刚才出栈的那个函数基本一样，只是这个函数不用再把栈顶元素销毁掉，而是直接返回该元素。

3.6

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->q1) && StackEmpty(&obj->q2);
}
1
2
3

判断栈是否为空，只有两个栈全为空的时候最后结果才为空，所以这里用到是逻辑与的符号。
StackEmpty函数：

//检测栈是否为空，如果为空返回true，如果不为空返回false
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}
1
2
3
4
5
6

3.7

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->q1);
    StackDestroy(&obj->q2);
    free(obj);
}
1
2
3
4
5

销毁栈，这里把最开始创建的指针，结构体销掉就行。
StackDestroy同样是我自己写的函数：

//销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
1
2
3
4
5
6
7
8

三.结束

上面两道题，都用了我自己曾经写的栈，队列实现的函数，这里你们不熟悉也没关系，复制过去，知道怎么用就行了。如果感兴趣也可以，这两个数据结构的实现我在每道题后面都有链接。