【面试题】循环队列&&队列实现栈&&栈实现队列

1️⃣设计循环队列OJ链接
2️⃣用队列实现栈OJ链接
3️⃣用栈实现队列OJ链接

这几道面试题需要栈和队列的知识，它们的相关知识可以看我的上一篇文章

1️⃣设计循环队列

先来了解一下环形队列，这也是循环队列的思想，空间是固定的，数据满的时候就不能再插入数据了。
在下面我们就需要考虑一个问题了？环形队列是用链表实现呢，还是用数组实现呢？
我们这里首先要说的是，两种方法是都可以的，而最终选择的方法是数组实现
因为使用链表更加的麻烦，虽然链表给我们的感觉更符合实际（需要循环），但是链表并不能很好的找到队尾数据，而且也并不知道，节点中是否有数据。数组就可以很好的解决这些麻烦。

循环队列的实现：使用数组来实现，在申请数组的空间时，多申请一个空间，用来解决判断队列为空为满的问题。主要问题都是围绕着当数据在数组的尽头时，和为空为满产生的。接下来我们将代码分为几个部分，分开解决。

🌎队列为空为满问题

判断为空时，当front==rear时就为空。

判断为满时，当(rear+1)%(k+1)==front时就为满，就由下面的图来证明一下，rear（数组下标）现在是为4，front为0，k（数组存放数量的容量）为4，(4+1)%(4+1)=0。

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj);
    if(obj->front==obj->rear)
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj);
    if((obj->rear+1)%(obj->k+1)==obj->front)
    {
        return true;
    }
    else
    {
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

🌎插入与删除数据

在插入数据时需要判断一下队列是否为满，这里仍是采用 (rear+1)%=k+1的方法，代码中没有加一是因为上面进行了++，这个表达式解决了队列循环的问题，保证一直往复。
在删除队列数据时需要判断一下是否为空，方法是一样的，都是为了解决循环问题。

//插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    assert(obj);
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    else
    {
        obj->a[obj->rear++]=value;
        (obj->rear)%=obj->k+1;
        return true;
    }
}
//删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        obj->front++;
        obj->front%=obj->k+1;
        return true;
    }
}
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

🌎返回队头和队尾数据

front指向的位置就是队头的位置，rear-1就是队尾的位置，因为当时多创建了一个空间，rear也就是指向那个空间。
在找队尾数据时，下面注释的代码是另一种方法，我个人更喜欢没有被注释的代码，代码更加的直观，被注释的代码更加的简洁。在查找之前都需要进行队列是否为空的判断。

//返回队头
int myCircularQueueFront(MyCircularQueue* obj) {
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        return obj->a[obj->front];
    }
}
//返回队尾
int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        //return obj->a[(obj->rear+obj->k)%(obj->k+1)];
        if(obj->rear==0)
        {
            return obj->a[obj->k];
        }
        else
        {
            return obj->a[obj->rear-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

🌎开辟空间等问题

在下面的代码中，使用的是柔性数组，它的好处在于在开辟空间的时候只需要一段代码就可以解决了，在释放空间是也是同样的得到了方便，当然也可以选择不用柔性数组。

typedef struct {
    //int *a;
    int front;
    int rear;
    int k;
    int a[];
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue *obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)+sizeof(int)*(k+1));
    //obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->front=obj->rear=0;
    obj->k=k;
    return obj;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    assert(obj);
    //free(obj->a);
    free(obj);
    obj=NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

以上的代码就是循环队列题的全部代码了

2️⃣用队列实现栈

​🐬这道题的意思就是用栈的性质来完成队列相关功能，还有一点就是C语言并没有栈和队列的库，所以需要我们自己实现一下栈和队列。
在实现之前先了解一下栈的性质：后进先出。队列性质：先进先出。
实现思路就是使用两个队列，保持一个队列总是空的，这样就可以将出队列的数据放进空的队列，而在原来的队列剩下的一个数据就是要出栈的数据，要插入数据也是往有数据的队列中插入，就这样一直往复，就实现栈了。

//先是创建两个队列，放在结构体里更方便
//并且题目中给的结构体是匿名结构体
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;
//对结构体开辟空间，并且初始化两个队列
//因为调用了队列的实现所以就可以直接用实现队列里的函数
//对新创建的队列进行初始化
MyStack* myStackCreate() {
    MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}
//实现入栈的操作
//先需要判断一下那个队列不是空的，然后将数据插入进去
//仍是需要掉用一下队列实现的函数就可以了
void myStackPush(MyStack* obj, int x) {
    assert(obj);
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}
//实现出栈的操作
//仍是需要判断一下那个队列是空的
//然后将另一个队列的数据就剩下一个，剩下的全部导入空队列
//这样在将那一个数据进行出队列
//就是实现了出栈的操作
int myStackPop(MyStack* obj) {
    assert(obj);
    Queue* empty=&obj->q1;
    Queue* noempty=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        empty=&obj->q2;
        noempty=&obj->q1;
    }

    while(noempty->size>1)
    {//将队列里的数据导入另一个队列
        QueuePush(empty,QueueFront(noempty));
        QueuePop(noempty);
    }
    //最后要求返回出栈的数据，素所以需要记录一下
    int ret=QueueBack(noempty);
    QueuePop(noempty);
    return ret;
}
//实现输出栈顶数据
//找到那个有数据的队列，在队尾的数据就是栈顶的数据
int myStackTop(MyStack* obj) {
    assert(obj);
    if(QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q2);
    }
    else
    {
        return QueueBack(&obj->q1);
    }
}
//判断栈是否为空
//需要将两个队列都进行判断，都为空栈才为空。
bool myStackEmpty(MyStack* obj) {
    assert(obj);
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
//释放空间
//需要先将队列的空间释放再将结构体的空间释放
//如果先释放的结构体的空间，会导致队列的空间释放不了
void myStackFree(MyStack* obj) {
    assert(obj);
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
    obj=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

下面的代码为队列实现的代码，需要放在上段代码的前面

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 = NULL;
	pq->tail = NULL;
	pq->size = 0;
}
//销毁数据，在这里需要一个一个的释放
//因为当时在开辟的时候也是一个一个的开辟的
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* prev = cur;
		cur = cur->next;
		free(prev);
	}
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}
//在队尾插入数据
//这里的size是用来记录在队列当中数据的个数的。
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
	newnode->data = x;
	newnode->next = NULL;
}
//在队头删除数据
bool QueueEmpty(Queue* pq);
void QueuePop(Queue* pq)
{
	assert(pq);
	//这里需要判断一下队列是否为空
	//当为空时并不能在删除数据
	assert(!QueueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* prev = pq->head;
		pq->head = pq->head->next;
		free(prev);
	}
	pq->size--;
}

//用来判断队列是否为空。
//通过下面的两种方法是都可以的，一种是通过size
//另一种是对队头队尾进行判断
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	if (pq->size == 0)
	{
		return true;
	}
	return false;
	//return pq->head == NULL && pq->tail == NULL;
}
//返回队头数据
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)
{
	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

3️⃣用栈实现队列

🐬这道题和上面的题大同小异，这道题是用栈的性质实现队列。
在实现之前先了解一下栈的性质：后进先出。队列性质：先进先出。
实现思路就是创建两个栈，分别记s1和s2，先将数据放入s1，再将s1中的数据全部导入s2这样s2中在出栈就是出队列的操作了，而在入队列的时候，将数据入栈到s1，一直入栈就在s1上面一直入站就可以了，只有将s2中的数据出栈完全才可以再将s1中的数据导入s2。

//先是创建两个栈，放在结构体里更方便
//并且题目中给的结构体是匿名结构体
typedef struct {
    ST s1;
    ST s2;
} MyQueue;
//为结构体申请空间，并且为栈进行初始化
MyQueue* myQueueCreate() {
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&obj->s1);
    StackInit(&obj->s2);
    return obj;
}
//实现进队列
//仍是直接调用实现栈函数的操作
void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    StackPush(&obj->s1,x);
}
//实现出队列
//先进行判断s2中是否为空如果为空就将是s1中的数据导入s2
//最后返回出队列的数据，
int myQueuePop(MyQueue* obj) {
    assert(obj);
    if(StackEmpty(&obj->s2))
    {
        while(!StackEmpty(&obj->s1))
        {
            StackPush(&obj->s2,StackTop(&obj->s1));
            StackPop(&obj->s1);
        }
    }
    int top=StackTop(&obj->s2);
    StackPop(&obj->s2);
    return top;
}
//实现返回队列开头的元素
//进行判断s2是否为空，如果不为空，就直接返回栈顶数据
//如果为空，需要将s1中的数据全部导入到s2，在返回栈顶数据。
int myQueuePeek(MyQueue* obj) {
    assert(obj);
    if(!StackEmpty(&obj->s2))
    {
        return StackTop(&obj->s2);
    }
    else
    {
        while(!StackEmpty(&obj->s1))
        {
            StackPush(&obj->s2,StackTop(&obj->s1));
            StackPop(&obj->s1);
        }
        return StackTop(&obj->s2);
    }
}
//判断队列是否为空
//仍是需要两个栈全部都为空时，队列才为空
bool myQueueEmpty(MyQueue* obj) {
    assert(obj);
    return StackEmpty(&obj->s1)&&StackEmpty(&obj->s2);
}
//释放空间
//需要先将栈的空间释放再将结构体的空间释放
//如果先释放的结构体的空间，会导致栈的空间释放不了
void myQueueFree(MyQueue* obj) {
    assert(obj);
    StackDestroy(&obj->s1);
    StackDestroy(&obj->s2);
    free(obj);
    obj=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

下面的代码为栈实现的代码，需要放在上段代码的前面

typedef int STDatatype;
typedef struct Stack
{
	STDatatype* a;
	int capacity;
	int top;   // 初始为0，表示栈顶位置下一个位置下标
}ST;
void StackInit(ST* ps)
{//对栈进行初始化
	assert(ps);
	ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
	//开始先创建四个整型的空间
	if (ps->a == NULL)
	{//必须要进行是否开辟成功的判断！
		perror("malloc");
		exit(-1);
	}

	ps->top = 0;//初始化为零
	ps->capacity = 4;//开辟空间时开了四个整型空间，所以初始化时的容量为四。
}

void StackPush(ST* ps, STDatatype x)
{//将数据进行入栈
	assert(ps);
	if (ps->top == ps->capacity)
	{//判断是否需要扩容
		STDatatype* prev = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2);
		//这里扩容就直接扩容为原来的二倍
		if (prev == NULL)
		{//必须判断时候开辟成功
			perror("relloc");
			exit(-1);
		}
		ps->a = prev;
		ps->capacity *= 2;
	}
	ps->a[ps->top] = x;//把数据进行入栈
	ps->top++;
}
bool StackEmpty(ST* ps);
void StackPop(ST* ps)
{//出栈
	assert(ps);
	assert(!StackEmpty(ps));
	//当top为零时，也就是该函数true时，不能在进行出栈的操作
	ps->top--;
}
void StackDestroy(ST* ps)
{//销毁栈，并释放空间
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

STDatatype StackTop(ST* ps)
{//找到栈顶
	assert(ps);
	assert(!StackEmpty(ps));
	//当top为零时，也就是该函数true时，不能在进行出栈的操作
	return ps->a[ps->top - 1];
	//因为top指向的是栈顶的下一个位置，所以，在查找栈顶是需要进行减一
}

bool StackEmpty(ST* ps)
{//判断栈中是否为空
	assert(ps);

	/*if (ps->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/

	return ps->top == 0;
	//和上面注释的代码作用是一样的，下面的更简洁，上面的可读性更强
}

int StackSize(ST* 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