【数据结构初阶】(栈和队列)图文详解四道oj+三道easy概念题

你也会感到孤独吗？

---

---

一、队列和栈的接口

我们这里必须强调一下队列和栈的接口，如果队队列和栈的接口不熟悉的话，下面的几个OJ题做起来会很困难，所以我们有必要将队列和栈的接口重新说明一下，依托他们各自结构进行记忆。

栈： 我们对栈的结构应该是比较熟悉的了，栈就是一种类似于子弹夹的数据结构，具有先进后出的结构特点，所以栈有StackPush,StackPop,StackTop,StackEmpty,StackInit,StackDestroy,StackSize,等七个重要接口

队列： 队列其实就像我们生活中的队伍一样，先进先出，是一种很公平的数据结构，我们从队尾push数据，从队头pop数据等都可以做到，所以我们的队列有QueuePush,QueuePop,QueueFront,QueueBack,QueueInit,QueueDestroy,QueueEmpty,QueueSize等八个重要接口

总结： 其实不用记忆，只要你对其结构特点了解清晰，自然而然就可以想起来，无非就是核心的接口加几个边角料接口而已，由于队列结构的流畅性，所以他其实是比栈多一个获取队尾元素的接口的。

只有我们对这两个经典的数据结构掌握扎实了，后面的题才变得好处理，如果你连最基本的结构都不清楚的话，这不纯纯牛马么！

二、有效的括号

2.1 思路呈现

这道题其实是一道非常经典的使用栈结构来解决的一道题，由于栈结构的特殊性，我们可以利用栈结构来解决这道题。只要有左括号我们就将其进行入栈，如果遇到右括号我们就利用top将栈顶元素拿出来，然后再利用pop将栈顶元素删除掉。

正因为栈的先入后出这种结构，我们可以让最近的两个括号先匹配，然后再去判断后面的括号对是否有效，所以说这题简直就是专门为栈而生的。

下面是部分正确括号形式的示意图。

2.2 代码呈现+细节讲解

动态数组栈的各个接口实现：

//动态栈结构
typedef char STDataType;
typedef struct Stack
{
	STDataType* array;
	int top;//这代表我们栈顶的位置，top会随着栈空间数据的扩大随之变换
	int capacity;
}ST;

void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
STDataType StackTop(ST* ps);//取栈顶的数据
int StackSize(ST* ps);
bool StackEmpty(ST* ps);
void StackInit(ST* ps)
{
	assert(ps);
	ps->array = NULL;
	ps->top = 0;//ps->top = -1; 我们的top也是可以给-1的
	ps->capacity = 0;	

	//初始化时，top给的是0，意味着top指向栈顶数据的下一个
//我们的top指向的是最后栈顶数据的下一个，因为我们是先插入数据到下标为top的位置，然后top再++
	//初始化时，top给的是-1，意味着top指向栈顶数据
//我们的top指向的是栈顶数据，因为我们要先将top+1，然后再往此时的top位置放数据，下一次也是先将top位置+1再放数据

//这是一个什么问题呢？(就是)是先放数据再移动top呢？还是先移动top再放数据呢？
	
}
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->array);
	ps->array = NULL;
	ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDataType x)//将元素进行入栈
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->array, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->array = tmp;
		ps->capacity = newCapacity;
	}
	ps->array[ps->top] = x;	
	ps->top++;
}
void StackPop(ST* ps)//将元素进行出栈，删除数据
{
	assert(ps);
	assert(!StackEmpty(ps));//top为0的时候是不能进行删除的

	ps->top--;
}
STDataType StackTop(ST* ps)//取栈顶的数据
{
	assert(ps);
	assert(!StackEmpty(ps));//如果栈为空，就会报错

	//我们的栈必须得有数据你才能取数据啊，如果没有数据你还取数据的话，就是访问下标-1的数据了，造成越界访问
	return ps->array[ps->top - 1];
}
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;//top指向的是栈顶数据的下一个位置，又因为它从0开始增大，所以top的值正好就是栈数据的个数
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	/*if (ps->top > 0)
	{
		return false;
	}
	else
	{
		return true;
	}*/

	return ps->top == 0;//这里的判断条件的正确与否，正好就对应上我们返回的是逻辑真还是逻辑假。true or false
}
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

利用栈的结构处理这道题，具体细节已经标注在每行代码的后面了

bool isValid(char * s){
    ST st;//我们需要利用栈的结构类型创建一个栈空间出来，
    StackInit(&st);//我们的初始化接口会自动帮我们给数组开辟好空间，直接调用接口就好了，非常的方便
    while(*s)//这里开始遍历整个字符数组，遇到'\0'遍历完毕，跳出循环
    {
        if(*s=='('||*s=='{'||*s=='[')//只要遇到左括号我们就压栈
        {
            StackPush(&st,*s);
            s++;
        }
        else
        {
            if(StackEmpty(&st))//这里是为了避免数组里只有右括号的情形
            {//如果只有右括号的话，程序不用继续运行了，直接销毁栈空间返回false就可以了
                StackDestroy(&st);
                return false;
            }
            char top=StackTop(&st);//保存栈顶数据，方便后面和左括号进行比较
            StackPop(&st);//保存完之后我们就得比较接下来的括号了，所以更新一下栈顶数据，将原来的栈顶数据pop掉
            //下面进行左括号和右括号的比较
            if((top=='{'&&*s!='}')||(top=='('&&*s!=')')||(top=='['&&*s!=']'))
                return false;//如果不相等直接返回false，
            else
                s++;//相等就继续向后遍历字符数组，进行下一次的比较
        }
    }
    //运行到这里，栈的空间必须变为空，如果不为空，说明栈中还有左括号未出
    bool ret=StackEmpty(&st);
    StackDestroy(&st);
    return ret;//若为空，返回true，若不为空，返回false
}
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

这里还要在强调两个容易出毛病的点：

1.如果我们的测试用例中，只给我们一个左括号呢？这样的话，左括号就会入栈，然后指针指到了斜杠0，跳出循环，我们不加判断，直接返回true，这就有问题了，所以当数组遍历结束之后，我们的栈空间必须为0，只要不为0，就说明有的左括号没有匹配上，还留在栈里面呢。

2.如果测试用例只给我们有括号的话，这样也是不行的，所以我们在else语句里面先加一个判空，如果栈中没有左括号，你还匹配啥呀，光有右括号不行啊，所以我们直接返回false就可以了。

怎么样？这道题是不是很简单啊。看看后面的题能难住你不，嘻嘻🤭🤭🤭。

三、用队列实现栈

3.1 思路呈现

实现栈，主要实现的是StackPush,StackPop,StackTop,这几个重要的接口，然后再加上个初始化，判空，销毁等接口。

push这个接口和队列没什么区别，你只要将数据存储起来就可以，但出栈和获取栈顶元素实现起来就需要我们好好思考了。由于栈是先进后出，队列是先进后出，所以我们需要一个辅助队列帮助我们存放除最后一个入队列以外的其他元素，这个元素就可以用在pop接口里，而实现top接口其实也是简单的，我们只要获取队尾元素就可以了，队尾元素正好就是栈顶元素。

我们的队列是队尾入数据，队头出数据，栈顶入数据，栈顶出数据。

你看，当我们对栈和队列的实现，以及其各自结构特点的掌握明明白白的时候，这些题就迎刃而解了。

3.2 代码呈现+细节讲解

下面的代码是我们上篇博客实现过的链式队列，我们把它贴上去，然后后面创建两个队列进行栈结构的实现。

typedef int QDataType;
typedef struct QueueNode//队列结构中的每一个结点
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;
//1.我们之前的单链表不定义尾指针的原因是什么呢？其实这没有多大意义。你尾删确实方便了，可tail又得重新定义，你又得通过phead找到
//新的尾，然后将tail给到这个尾，所以我们的单链表定义tail其实是没多大意义的
//2.我们的双链表也没有定义尾指针，是因为我们完全可以通过phead找到我们的tail，所以定义也是没有意义的。
//3.所以我们在定义结构时，是要视需求和具体情况所定的，不是想定义什么就定义什么
typedef struct Queue//我们的队列结构
{
	QueueNode* head;
	QueueNode* tail;
//这里我们其实也可以将这两个队列结点指针单独定义出来，但是这样不太符合代码的主流风格，所以我们将他们包到一个结构体里。
}Queue;
//单链表那里，我们是单独将单链表的头指针拎出来，独立于结点结构体定义的，这里我们是将两个指针合在一起定义到一个
//队列结构里面

//因为我们的队列不会在队尾进行删除，所以我们定义的尾指针的价值就得到了体现，而且用结构体封装这些指针还是有很多
//好处的，我们通过结构体指针就可以找到这些指针了，如果你不用结构体单独定义两个结点的指针，也不是不可以，但是
//你后面接口实现的时候，你就得传两个参数了，一个头指针一个尾指针，而且你要想修改他们的指向还得传二级指针
//就像下面这样来使用，那你调用接口的时候很有可能会被它烦死
//void QueueInit(Queue** pphead, Queue** pptail);
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);//队尾入队列
void QueuePop(Queue* pq);//队头出队列
QDataType QueueFront(Queue* pq);//获取队列头部元素

QDataType QueueBack(Queue* pq);//获取队列队尾元素

int QueueSize(Queue* pq);//获取队列中有效元素个数
bool QueueEmpty(Queue* pq);// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 ,true or false

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}

void QueueDestroy(Queue* pq)//销毁队列
{
	assert(pq);//head和tail可以为空，但我们的队列结构肯定不可以为空，如果队列结构都为空了，那肯定是我们传的参数出了问题
	QueueNode* cur = pq->head;
	//while (cur != pq->tail)
	//{
	//	//我们这里进行释放队列结点
	//	//但这种逻辑其实有问题，因为你最后一个队列结点的空间是没有进行删除的，会造成内存泄漏。
	//}
	while (cur != NULL)//当我们的cur走到NULL时，正好说明队列结点空间已经释放完毕了
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
	//这里我们要分两种情况
	//1.我们的tail和head都是正常的，然后我们直接在tail后面插入队列结点，这就相当于我们的入队列，然后再更新一下tail的位置。
	//2.如果我们的tail和head都为空的话，我们直接将新的队列结点的地址赋值给我们的head和tail，此刻我们的尾和头所指位置是相同的
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->data = x;
	newnode->next = NULL;//将我们队列结点初始化

	if (pq->head == NULL) 
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
void QueuePop(Queue* pq)
{
	assert(pq);//表达式计算结果为假(0)，assert就会报错
	assert(!QueueEmpty(pq));//我们的队列不可以为空
	QueueNode* next = pq->head->next;//如果我们这里的队列头指针为空，这里就造成内存读取权限访问冲突。
	free(pq->head);
//我们队列中的结点全被free掉了，可是tail的指向还是没人给他改一下，它还在指向一个已经被释放掉了的空间，
//tail就是一个典型的野指针
	pq->head = next;
	if (pq->head == NULL)
	{
		pq->tail = NULL;//我们的链表已经删除完之后，为了防止tail变为野指针，我们也让tail置为空
	}
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//断言为假，程序就会崩
	return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//粗暴判断队列结构和队列中的结点不为空

	return pq->tail->data;
}
int QueueSize(Queue* pq)//我们也可以在队列结构体定义那里加一个成员size_t _size，我们push它就++，pop它就--。
{
	assert(pq);
	QueueNode* cur = pq->head;
	int i = 0;
	while (cur)
	{
		i++;
		cur = cur->next;
	}
	return i;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
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

利用两个队列实现栈的结构，具体细节标注在代码里了

typedef struct {
    Queue q1;//我们在栈的结构里定义两个队列
    Queue q2;

} MyStack;


MyStack* myStackCreate() {
//这个接口是我们栈空间的创建，所以需要malloc一块空间作为栈的地址，然后调用队列初始化接口将栈里面的两个队列进行初始化，
//最后我们返回栈空间的地址，以便测试模块儿中对栈的各个接口进行实现。
    MyStack*st=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}

void myStackPush(MyStack* obj, int x) {
//这个模块儿是压栈,因为我们后面的出栈等会对两个队列进行频繁的换值，但肯定会有一个队列是不为空的，
//我们压栈操作一定是往非空队列中压栈的，两个队列都有可能是非空，所以我们这里分支处理了一下
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
//由于我们的pop操作一定是将非空队列中除尾数据的其他数据入队列到空队列当中，
//所以我们先假设定义了一个非空和空的队列，这样做可以让代码的命名风格更好一些。

    Queue* emptyQ=&obj->q1;//注意这里是栈结构中的队列1，你直接搞个q1，疯球了你妹的。
    Queue* nonemptyQ=&obj->q2;
    if(!QueueEmpty(&obj->q1))//假设错了，我们重新赋值一下
    {
        emptyQ=&obj->q2;//注意这里是栈结构中的队列1，你直接搞个q1，疯球了你妹的。
        nonemptyQ=&obj->q1;
    }
    int w=QueueSize(nonemptyQ);
    while(--w)//什么时候就转移元素停止了？因为要留一个尾数据，所以我们的循环次数比数据个数少1
    {
       QDataType top= QueueFront(nonemptyQ);
       QueuePush(emptyQ,top);
       QueuePop(nonemptyQ);
    }
    QDataType i=QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);
    return i;
}

int myStackTop(MyStack* obj) {
//这个接口是取栈顶数据，这个也比较简单，通过我们对队列结构的清晰认识，我们可知队尾数据即为栈顶数据。
//所以我们找出非空队列，将队尾数据返回即可，其他什么都不用做。
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }


}

bool myStackEmpty(MyStack* obj) {
//这个接口是判断栈是否为空的接口，当两个队列均为空时，便可以说明我们的栈也为空了。
//这里我们利用逻辑表达式的特点，将逻辑表达式的结果进行返回
//两个队列都为空，逻辑为真，返回true，只要有一个不为空，逻辑为假，返回false。
    return QueueSize(&obj->q1)==0&&QueueSize(&obj->q2)==0;
}

void myStackFree(MyStack* obj) {
//这个接口是栈空间的销毁，我们要看一看我们都malloc了哪些空间，销毁应该将我们申请的空间全还给操作系统
//否则就会出现内存泄露的问题。

//我们每一次的push，队列都会向操作系统申请空间，所以我们先得把两个队列的空间销毁掉，
//然后再把我们开辟的栈空间销毁掉，因为我们对栈初始化时，是malloc了一个栈空间的，所以要free。
//对队列空间销毁，我们直接调用队列接口就可实现。
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(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

3.3 总结

其实要想解决这些题，我们还是得熟练掌握栈和队列的各个接口如何实现，每个接口的参数以及返回值如何设计，以及两种结构的相似性，差异性等等。

掌握好这些的话，我们对结构就会有更深一步的理解

四、用栈实现队列

4.1 思路呈现

用栈实现队列的话，其实就是实现QueuePush,QueuePop,QueueFront,QueueBack等核心接口,以及QueueInit,QueueDestroy,QueueSize,QueueEmpty这些边角料接口。

实现入队列的话，我们直接压栈就好了，都是入数据，存储数据的功能，出队列的话，队列是先进先出，栈是先进后出，这时我们便可构造另外一个辅助栈空间，来实现队列的这种出队列结构

其实这道题还是偏简单了，它只让我们实现push，pop，返回队头元素，判空等接口的实现，如果它还让我们实现返回队尾元素这个接口的话，这道题就会又稍微的复杂一点，我们需要不断在两个栈中移动我们的数据来满足队列接口的要求，如果你想pop当然需要在另一个栈中弹出栈顶数据，如果你想返回队头数据，直接返回栈顶数据。

如果你想返回队尾数据，我们要看原来栈中是否有数据，如果没有数据这时你就必须对栈中元素做出调整了，重新出栈返回到原本栈的那种结构，然后再返回此时栈顶数据，正好相当于队尾的元素。

如果原来栈中有数据，可能是之前没调用pop接口，也可能是调用pop接口之后，又调用了push接口，我们这时直接返回原来栈中的栈顶数据

但这题并没有要求我们实现返回队尾元素的接口，那我们也就不管它了。

4.2 代码呈现+细节讲解

将我们之前实现的数组栈贴到这里，后面利用栈实现队列

typedef int STDataType;
typedef struct Stack
{
	STDataType* array;
	int top;//这代表我们栈顶的位置，top会随着栈空间数据的扩大随之变换
	int capacity;
}ST;

void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
STDataType StackTop(ST* ps);//取栈顶的数据
int StackSize(ST* ps);
bool StackEmpty(ST* ps);

void StackInit(ST* ps)
{
	assert(ps);
	ps->array = NULL;
	ps->top = 0;//ps->top = -1; 我们的top也是可以给-1的
	ps->capacity = 0;	

	//初始化时，top给的是0，意味着top指向栈顶数据的下一个
//我们的top指向的是最后栈顶数据的下一个，因为我们是先插入数据到下标为top的位置，然后top再++
	//初始化时，top给的是-1，意味着top指向栈顶数据
//我们的top指向的是栈顶数据，因为我们要先将top+1，然后再往此时的top位置放数据，下一次也是先将top位置+1再放数据

//这是一个什么问题呢？(就是)是先放数据再移动top呢？还是先移动top再放数据呢？
	
}
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->array);
	ps->array = NULL;
	ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDataType x)//将元素进行入栈
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->array, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->array = tmp;
		ps->capacity = newCapacity;
	}
	ps->array[ps->top] = x;	
	ps->top++;
}
void StackPop(ST* ps)//将元素进行出栈，删除数据
{
	assert(ps);
	assert(!StackEmpty(ps));//top为0的时候是不能进行删除的

	ps->top--;
}
STDataType StackTop(ST* ps)//取栈顶的数据
{
	assert(ps);
	assert(!StackEmpty(ps));//如果栈为空，就会报错

	//我们的栈必须得有数据你才能取数据啊，如果没有数据你还取数据的话，就是访问下标-1的数据了，造成越界访问
	return ps->array[ps->top - 1];
}
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;//top指向的是栈顶数据的下一个位置，又因为它从0开始增大，所以top的值正好就是栈数据的个数
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	/*if (ps->top > 0)
	{
		return false;
	}
	else
	{
		return true;
	}*/

	return ps->top == 0;//这里的判断条件的正确与否，正好就对应上我们返回的是逻辑真还是逻辑假。true or false
}
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

利用两个栈实现队列结构，具体细节标注在代码里了

typedef struct {
    ST st1;//在这里提前说明一点，st1是用来push数据的，st2是为了模仿队列出数据的。
    //只要入数据，我们直接入到st1里面，出数据时，将数据出栈到st2里，在出st2里的数据。
    ST st2;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue*queue=(MyQueue*)malloc(sizeof(MyQueue));
    //动态申请一个队列的空间后续通过队列空间的地址，实现队列的各个接口
    StackInit(&queue->st1);//将队列中两个栈进行初始化，为各个栈malloc好初始化的空间大小。
    StackInit(&queue->st2);
    return queue;//返回malloc好的队列地址
}

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->st1,x);//只要入队列的数据，我们都入到st1里边
}

int myQueuePop(MyQueue* obj) {
//值得注意的是只要我们的st2中有数据，我们直接出栈st2的元素即可，如果没有，我们才会将st1中的数据出栈再压栈到st2里，所以第一件事情就是判断st2是否为空。
    if(StackEmpty(&obj->st2))
    {
        while(StackSize(&obj->st1)>0)//如果为空我们将st1中的数据挪动到st2里
	    {
	        STDataType top=StackTop(&obj->st1);
	        StackPush(&obj->st2,top);
	        StackPop(&obj->st1);
	    }

    }
    
    STDataType i=StackTop(&obj->st2);//保存一下st2的栈顶元素，等会儿将他返回
    StackPop(&obj->st2);//直接出栈st2中的数据，和出队列数据一样了就。
    return i;

}

int myQueuePeek(MyQueue* obj) {
//返回队头数据，我们也得返回st2的栈顶数据，所以这个接口和上面出队列的接口甚是相似
//第一件事就是判断st2中的数据是否为空，如果为空，我们就得赶紧将st1中的数据挪到st2里
//如果不为空，直接返回st2的栈顶数据即可，利用我们的StackTop接口
    if(StackEmpty(&obj->st2))//只要st2是空的，我们就赶紧得将st1中的数据压栈到st2里边
    {
        while(StackSize(&obj->st1)>0)
        {
            STDataType top=StackTop(&obj->st1);
            StackPush(&obj->st2,top);
            StackPop(&obj->st1);
        }
    }
    return StackTop(&obj->st2);
}

bool myQueueEmpty(MyQueue* obj) {
//当我们的两个栈均为空时，队列才会为空，所以这里利用逻辑表达式的结果返回

    return StackEmpty(&obj->st1)&&StackEmpty(&obj->st2);
    //两个栈都为空，逻辑判断为真，返回true，只要有一个栈不为空，逻辑判断为假，返回false。

}

void myQueueFree(MyQueue* obj) {
//我们队列的空间和两个栈的空间都是malloc出来的，但我们得分先后顺序进行释放空间
    StackDestroy(&obj->st1);
    //我们栈中的接口都用栈地址作为接口参数，所以我们要取队列中栈空间的地址，
    //将地址传回栈的接口，接口用指针来作为参数接收，好对栈结构进行修改。
    StackDestroy(&obj->st2);
    free(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

4.3 总结

其实吧，总结来总结去的，就几句话想提醒大家，栈和队列经典实现的各个接口大家都要很熟悉，怎么算熟悉呢？只要我一说栈和队列，你就能说出他们有什么接口？每个接口如何实现？他们的结构是怎么样设计的？实现时需要注意的细节有哪些？包括他们各自的结构特点，不同的地方相同的地方，这些你都得烂熟于心，做到这样以后，这些题肯定难不倒你了就。

而且有了基础的沉淀之后，通过拔高的题的练习，更能加强你对底层知识的理解。

五、设计循环队列

5.1 思路呈现

我们可以用两种方式来解决这道题，像我们之前实现的经典队列的话，是用链表的方式来解决的，因为出队列对于数组这种结构并不太适用，一旦出队列，数组整个元素都得移动，所以我们当时采用了链表。

但现在情况就会不一样了，我们实现的是循环队列，通过数组的下标索引就可以完成出队列操作，这时有人可能会有疑问，之前的队列数组这样的结构需要挪动整个数据，现在怎么不用了啊？

我们可以这样做，如果要出队列，我们直接将front下标++，这样就不会访问到头元素了，入队列我们直接在back位置插入元素，然后让back++，这样的话，空间就会被我们利用起来了。肯定又会有人问到，那原来的队列为什么不可以这样搞啊？

要知道我们原来的队列可不是循环的啊，如果你出队列一下，front++，那front前面的空间是不全被你浪费掉了，你出队列多少下，空间就被你浪费多少，你自己想吧，你定义的这结构不废了？哪有链表结构更优啊！

所以这道题我们可以使用数组的方式来解答。

另外一种方式就是利用链表来解决，我们控制结点的个数小于等于k，让结点的个数不可以超过k，如果相等则空间就满了，无法继续入队列，入队列也就失败了，返回-1。

与上面删除元素是不同的，我们链表删除元素直接释放结点空间，数组删除元素就是让下标++，令其无法访问到原来下标位置的元素。

5.2 数组

typedef struct {
    int*array;
    int front;
    int tail;
    int k;//环形队列的有效长度

} MyCircularQueue;

 bool myCircularQueueIsFull(MyCircularQueue* obj);
 bool myCircularQueueIsEmpty(MyCircularQueue* obj);
MyCircularQueue* myCircularQueueCreate(int k) {
//我们malloc一个循环队列的空间出来，并且将队列内容进行初始化
    MyCircularQueue*cq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    cq->array=NULL;
    cq->front=cq->tail=0;
    cq->k=k;
    cq->array=(int*)malloc(sizeof(int)*(k+1));
    //我们开辟的空间要比循环队列的有效空间多一个，否则空间满和空的情况会是一样的
    return cq;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    {
        return false;
        //入队列之前，需要判断队列空间是不是满了，如果满了，增加数据失败。
    }
    obj->array[obj->tail]=value;//直接在下标为tail的位置插入数据
    obj->tail++;
    obj->tail=(obj->tail)%(obj->k+1);//要保证我们的下标在有效数据个数里
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;//同样的，删除数据时我们也要判断队列是否为空
    }
    obj->front++;//删除数据就比较简单了，只要前面的下标++，我们就无法访问到头部数据了，也就是出队列操作。从队头出嘛。
    obj->front=(obj->front)%(obj->k+1);//保证我们的下标在有效数据个数里面
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->array[obj->front];//直接返回Front下标位置的数据就可以了

}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    //这个获取队尾数据的接口，大家一定要小心啊，这里是有两种情况的
    //队列恰好满，和队列没满这两种情况是不一样的，我们返回的元素位置也不同
    if(obj->tail==0)//这里有两种情况，一定要小心呐
    {
        return obj->array[obj->k];
    }
    else
    {
        return obj->array[obj->tail-1];
    }
    

}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->tail;//front==tail时，队列为空
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1)%(obj->k+1)==obj->front;
    //tail的下一个位置若是front，说明队列已满
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->array);//释放动态数组的空间
    free(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

队列初始化接口：

返回队尾元素接口：

5.3 链表

具体细节已经在代码里标识了

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


typedef struct {//下面就是链式循环队列的属性
    QNode*front;//头指针
    QNode*back;//尾指针
    int capacity;//最大容量
    int size;//当前的结点个数
} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj);//把函数声明放前面一下，要不然接口中的调用会没有函数声明
bool myCircularQueueIsFull(MyCircularQueue* obj) ;

MyCircularQueue* myCircularQueueCreate(int k) {
//开辟一个循环队列结构空间，并对此结构进行初始化
    MyCircularQueue*cq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    cq->front=cq->back=NULL;
    cq->capacity=k;
    cq->size=0;
    return cq;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
//入队列之前要检查队列是否已满，调用我们的判满接口
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    QNode*newnode=(QNode*)malloc(sizeof(QNode));
    newnode->data=value;
    newnode->next=NULL;
    if(obj->front==NULL)//第一次入队列是将结点地址赋值给我们的头尾指针
    {
        obj->front=obj->back=newnode;
    }
    else//之后的入队列是将我们malloc的结点尾插到尾指针back后面。
    {
        obj->back->next=newnode;
        obj->back=newnode;
    }
    obj->size++;//结点个数+1
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
//删除之前要判断队列是否为空
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    QNode*next=obj->front->next;
    free(obj->front);//若不为空，我们直接释放掉头结点的空间。
    obj->front=next;
    obj->size--;//节点数--
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->front->data;

}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->back->data;

}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->size==0;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->size==obj->capacity;
}

void myCircularQueueFree(MyCircularQueue* obj) {
//这里空间的释放需要我们注意一些，我们的空间是一个一个malloc出来的。
//所以释放的时候需要做一个循环来进行结点空间的释放。
//最后再释放一下循环队列的空间就好了。
   while(obj->front)
    {
        QNode*next=obj->front->next;
        free(obj->front);
        obj->front=next;
    }
    free(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

兄弟们size和capacity是真的好用啊，呜呜呜。

用指针判断的时候，喵的，一直报错，想死都。

这道题用指针判断真的很不方便，用size和capacity是真的挺高效的。

5.4 总结

关于删除元素： 链表中删除元素利用释放空间的形式，数组中删除元素利用移动下标索引，阻止访问先前下标对应的元素。
关于释放空间： free掉维护动态数组的指针即可，free掉每一个链表中的结点才行。
对于判空和判满： 对于判空和判满，我们有两种解决的思路，一种是利用结构本身特征来进行判断，另一种是在结构里面多定义两个变量，一个是size，一个是capacity，我们用这两个变量可以非常轻松的解决判空和判满的问题。

六、三道概念题

6.1 测试你的理解程度

如果我们入队和退队的次数相同，那么队列中剩下的元素个数就是0了，如果我们入队比退队次数多一圈，那么队列中所剩元素正好就是队列的有效空间个数。

这个问题就类似于我们上面讲的判空和判满那个问题，正因为我们开辟的空间没有比有效空间多1，所以导致当Front==Rear时，我们无法判断现在的循环队列中元素到底是满还是空。自然答案也就有两种可能0或者100。

队列的基本接口要烂熟于心，QueueInit,QueueDestroy,QueuePush,QueuePop,QueueFront,QueueBack,QueueEmpty,QueueSize八个基本接口。

这个有效长度其实就是普通队列的有效长度，也就是头指针和尾指针的差值，我们可以看到我们之前在利用数组设计循环队列时，开辟的空间大小实际上是要比有效长度大1的，因为我们要区分循环队列空和满的情况，那样的结构是我们设计的，并不是主流的循环队列结构。

主流的循环队列结构就是，开辟空间个数和有效空间个数是一样的，或许人家增加了一个size的变量用于区别空和满这两种情况吧。

我们这个题就是普遍的那种，加个取余就是为了解决指针做差时可能会出现负数的情况，答案应该选B，只要+队列长度之后再取模队列长度，就能避免负数这样的情况了。