队列（详解）——手撕队列习题_手撕消息队列

作者：羊村懒王 | 2024-05-15 16:13:13

踩

手撕消息队列

队列

队列的简单介绍
Queue.h
- Queue.c
- - Test.c
  - 习题：
用队列实现栈
- 用栈实现队列
- - 设计循环队列

队列的简单介绍

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
在这里插入图片描述
队列的实现，其实和栈差不多，数组和链表都可以实现，但是由于队列的特殊性，先进先出的这种特性，当我们用数组的时候，出队的时候时间复杂度会一直是O（n），
我们用单链表实现的话

@[TOC](

Queue.h

#define _CRT_SECURE_NO_WARNING
#pragma once 
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
	QueueNode* front;
	QueueNode* rear;

}Queue;
void QueueInit(Queue* ps);//队列的初始化
void QueueDestory(Queue* ps);//队列的销毁
void QueuePush(Queue* ps,QDataType x);//入队
void QueuePop(Queue* ps);//出队
bool QueueEmpty(Queue* ps);//判断队列是否为空
size_t QueueSize(Queue* ps);//返回队列中元素的个数
QDataType QueueFront(Queue* ps);//返回队头元素
QDataType QueueRear(Queue* ps);//返回队尾元素




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

Queue.c

 #define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void QueueInit(Queue* ps)//队列的初始化
{
    assert(ps);//如果储存指针的地址都为空的话，肯定是错误的
    //刚开始的头指针与尾指针肯定是相等的，并且都是NULL
    ps->front = ps->rear = NULL;
           
}




void QueueDestory(Queue* ps)//队列的销毁
{
    assert(ps);
    QueueNode* cur = ps->front;
    while (cur)
    {
        QueueNode* ret = cur->next;
        free(cur);
        cur = ret;
    }
    ps->front = ps->rear = NULL;



}



void QueuePush(Queue* ps, QDataType x)//入队
{
    assert(ps);//入队肯定是与尾指针rear有关的 先申请一个空间
    QueueNode* cur = (QueueNode*)malloc(sizeof(QueueNode));
    if (cur == NULL)
    {
        printf("malloc fail\n");
        exit(-1);


    }
    cur->data = x;
    cur->next = NULL;
   /* QueueNode* ret = ps->rear->next;
    ps->rear = cur;这样写的话很有问题，没有判断当两个指针都为空指针的情况
    ps->rear = ret;*/
    if (ps->rear == NULL)
    {
        assert(ps->front == NULL);//当尾指针为空的时候，头指针不可能不为空
        ps->front = ps->rear = cur;
    }
    else
    {
        ps->rear->next = cur;
        ps->rear = cur; 
    }
}







void QueuePop(Queue* ps)//出队
{
    
    assert(ps);//出队也是头删
    assert(ps->front != NULL);//如果头指针为空的话肯定是错误的
    //队列中只有一个结点
    if (ps->front == ps->rear)
        ps->front = ps->rear = NULL;
    else
    {
        //ps->front = ps->front->next;这样写的话涉及到内存泄露
        QueueNode* ret = ps->front->next;
        free(ps->front);
        ps->front = ret;//这样写的话就不会涉及到什么内存泄露啦
    }
}


bool QueueEmpty(Queue* ps)//判断队列是否为空
{
    assert(ps);
    //当头指针为空的时候，队列就是空的
    return ps->front == NULL;
}



size_t QueueSize(Queue* ps)//返回队列中元素的个数
{
    assert(ps);
    int sum = 0;
    QueueNode* cur = ps->front;
    while (cur)
    {
        sum++;
        cur = cur->next;
    }
    return sum;
}


QDataType QueueFront(Queue* ps)//返回队头元素
{
    assert(ps);
    assert(ps->front != NULL);
    return ps->front->data;
}


QDataType QueueRear(Queue* ps)//返回队尾元素
{
    assert(ps);
    assert(ps->rear != NULL);
    return ps->rear->data;
}





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
124
125

Test.c

 #define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
int main()
{
	Queue st;
	QueueInit(&st);
	QueuePush(&st, 1);
	QueuePush(&st, 2323);
	QueuePush(&st, 86);
	QueuePush(&st, 567);
	QueuePush(&st, 999);
	QueuePush(&st, 666);
	//printf("%d", QueueSize(&st));
	while (!QueueEmpty(&st))
	{
		printf("%-7d", QueueFront(&st));
		printf("%-7d", QueueRear(&st));
		printf("%d\n", QueueSize(&st));
		QueuePop(&st);
	}
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

习题：

用队列实现栈

在这里插入图片描述

用队列实现栈

在这里插入图片描述

上面就是这道题的思路了，有一说一，C语言实现这个实在是麻烦，但是我们现在用C语言写还是可以加深一下对这个结构的感觉的



typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
	QueueNode* front;
	QueueNode* rear;

}Queue;
void QueueInit(Queue* ps)//队列的初始化
{
    assert(ps);//如果储存指针的地址都为空的话，肯定是错误的
    //刚开始的头指针与尾指针肯定是相等的，并且都是NULL
    ps->front = ps->rear = NULL;
           
}




void QueueDestory(Queue* ps)//队列的销毁
{
    assert(ps);
    QueueNode* cur = ps->front;
    while (cur)
    {
        QueueNode* ret = cur->next;
        free(cur);
        cur = ret;
    }
    ps->front = ps->rear = NULL;



}



void QueuePush(Queue* ps, QDataType x)//入队
{
    assert(ps);//入队肯定是与尾指针rear有关的 先申请一个空间
    QueueNode* cur = (QueueNode*)malloc(sizeof(QueueNode));
    if (cur == NULL)
    {
        printf("malloc fail\n");
        exit(-1);


    }
    cur->data = x;
    cur->next = NULL;
   /* QueueNode* ret = ps->rear->next;
    ps->rear = cur;这样写的话很有问题，没有判断当两个指针都为空指针的情况
    ps->rear = ret;*/
    if (ps->rear == NULL)
    {
        assert(ps->front == NULL);//当尾指针为空的时候，头指针不可能不为空
        ps->front = ps->rear = cur;
    }
    else
    {
        ps->rear->next = cur;
        ps->rear = cur; 
    }
}





void QueuePop(Queue* ps)//出队
{
    
    assert(ps);//出队也是头删
    assert(ps->front&&ps->rear);//如果头指针为空的话肯定是错误的
    //队列中只有一个结点
  if (ps->front->next == NULL)
       
       {
       
       free(ps->front);
       ps->front = ps->rear = NULL; 
       } 
    else
    {
        //ps->front = ps->front->next;这样写的话涉及到内存泄露
        QueueNode* ret = ps->front->next;
        free(ps->front);
        ps->front = ret;//这样写的话就不会涉及到什么内存泄露啦
    }
}


bool QueueEmpty(Queue* ps)//判断队列是否为空
{
    assert(ps);
    //当头指针为空的时候，队列就是空的
    return ps->front == NULL;
}



size_t QueueSize(Queue* ps)//返回队列中元素的个数
{
    assert(ps);
    int sum = 0;
    QueueNode* cur = ps->front;
    while (cur)
    {
        sum++;
        cur = cur->next;
    }
    return sum;
}


QDataType QueueFront(Queue* ps)//返回队头元素
{
    assert(ps);
    assert(ps->front != NULL);
    return ps->front->data;
}


QDataType QueueRear(Queue* ps)//返回队尾元素
{
    assert(ps);
    assert(ps->rear != NULL);
    return ps->rear->data;
}





typedef struct {
    Queue st1;
    Queue st2;

} MyStack;


MyStack* myStackCreate() {
     
     MyStack*obj = (MyStack*)malloc(sizeof(MyStack));
     assert(obj);
     QueueInit(&(obj->st1));
     QueueInit(&(obj->st2));//这边一定不能忘记初始化

     return obj;
}

void myStackPush(MyStack* obj, int x) {
         assert(obj);
        // if(obj->st1->front==NULL) obj->st1是一个队列，不是指针
        if(QueueEmpty(&(obj->st1)))
         {
             QueuePush(&(obj->st2),x);
         }
         else
         {
             QueuePush(&(obj->st1),x);
         }
}

int myStackPop(MyStack* obj) {
     assert(obj);
    //这部分是一个小技巧，通过一个简单的操作使得无论哪个队列为空，我们需要操作的都是
    //一样的 避免了代码的重复性  
   Queue*noEmpty = &(obj->st1);
   Queue*Empty = &(obj->st2);
   if(QueueEmpty(&obj->st1))//题目要注意的是传进去的都是地址，千万不要忘记取地址了
   {
       noEmpty = &(obj->st2);
       Empty = &(obj->st1);
   }
    while(QueueSize(noEmpty)>1)
    {
        QueuePush(Empty,QueueFront(noEmpty));
        QueuePop(noEmpty);
    }
    int ret = QueueFront(noEmpty);
    QueuePop(noEmpty);
    return ret;

      

}

int myStackTop(MyStack* obj) {
    assert(obj);
   if(QueueEmpty(&(obj->st1)))
    {
        return QueueRear(&(obj->st2));
    }
    else
     return QueueRear(&(obj->st1));
}

bool myStackEmpty(MyStack* obj) {
      assert(obj);
      return QueueEmpty(&(obj->st1))&&QueueEmpty(&(obj->st2));      
}

void myStackFree(MyStack* obj) {
       assert(obj);
     
        QueueDestory(&(obj->st2));
        QueueEmpty(&(obj->st1));
         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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222

用栈实现队列

坚持就是胜利！

在这里插入图片描述

用栈实现队列

在这里插入图片描述

**注意：**一定得保持一个栈始终有数字，另外一个栈始终没有数字，这样写代码的时候方便很多！

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//栈顶的位置
	int capacity;//容量
}ST;
void StackInit(ST* ps)//栈的初始化
{ 
	assert(ps);//栈可以为空，但是储存栈的结构体不可能是空的
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}



void StackDestory(ST* ps)//栈的销毁
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;



}



void StackPush(ST* ps, STDataType x)//压栈
{
	assert(ps);
	//压栈之前要检查一下栈是否满 因为我们的top始终是位于栈顶的下一个位置
	//所以当top的值等于capacity的时候栈就满了或者是一开始栈空的情况
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  		ps->a = (ST*)realloc(ps->a, sizeof(ST) * newCapacity);//在原来的基础上扩容，所以用realloc
		if (ps->a == NULL)
		{
			printf("malloc fail\n");
			exit(-1);
		}
		ps->capacity = newCapacity;
	}
	//压栈
	ps->a[ps->top] = x;
	ps->top++;
}





void StackPop(ST* ps)//出栈
{
	assert(ps);
	//出栈之前要考虑一下栈是否为空，空的话就不用出栈了 所以还需要一个断言
	assert(ps->top > 0);
	ps->top--;//因为我们打印的时候是从头开始遍历的，只会遍历到top所以只需要top--

}

bool StackEmpty(ST* ps)//检测栈是否为空
{
	assert(ps);
	//如果top = 0的时候就是栈空 所以
	return ps->top == 0;
}


int StackSize(ST* ps)//返回栈中元素的个数
{
	assert(ps);
	return ps->top;
}


STDataType StackTop(ST* ps)//返回栈顶的元素
{
	assert(ps);//同时这里要确保栈中不为空
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}



typedef struct {
    ST s1;
    ST s2;

} MyQueue;


MyQueue* myQueueCreate() {
        MyQueue*cur = (MyQueue*)malloc(sizeof(MyQueue));
        StackInit(&cur->s1);
        StackInit(&cur->s2);
        return cur;

}
//始终保持s1有数字
void myQueuePush(MyQueue* obj, int x) {
     assert(obj);
     StackPush(&obj->s1,x);
}

int myQueuePop(MyQueue* obj) {
     assert(obj);
     while(StackSize(&obj->s1)>1)
     {
         StackPush(&obj->s2,StackTop(&obj->s1));
         StackPop(&obj->s1);
     }
     int ret = StackTop(&obj->s1);
     StackPop(&obj->s1);
      while(StackSize(&obj->s2)>0)
     {
         StackPush(&obj->s1,StackTop(&obj->s2));
         StackPop(&obj->s2);
     }
     return ret;
}

int myQueuePeek(MyQueue* obj) {
    assert(obj);
    ST*cur = &obj->s1;
    return cur->a[0];//队列的开头也就是栈底 栈底也就是a[0];
}

bool myQueueEmpty(MyQueue* obj) {
    assert(obj);
      return StackEmpty(&obj->s1);
}

void myQueueFree(MyQueue* obj) {
     assert(obj);
     StackDestory(&obj->s1);//摧毁的时候一定要分别free，因为free只会消除其指向的
                            //空间
     StackDestory(&obj->s2);
     free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

设计循环队列

最后一题啦！
在这里插入图片描述

循环队列

在这里插入图片描述

我们先看下循环队列大致是怎样的，然后思考一下我们怎样去实现它

在这里插入图片描述
可以看出用数组或者是循环单链表都是可以的，但是单链表要考虑的东西有点多，我在这就用数组实现一下

typedef struct {
    int *a;
    int front;
    int rear;
    int k;//表示循环队列的长度为k但是有效长度为k-1 因为rear+1==front是判断队列满的条件

} MyCircularQueue;

bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
MyCircularQueue* myCircularQueueCreate(int k) {
   MyCircularQueue*cur = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
   cur->a = (int*)malloc(sizeof(int)*(k+1));
   cur->front = 0;
   cur->rear = 0;//我们代码设置的是rear初始值虽然是0
   //但是随着数据入队列，rear始终在最后一个数字的下一位，同时为了方便
   //判断队列空和满，我们必须留一个位置 //同时rear与front的值我们必须//记住取模
   cur->k = k+1;     
   return cur;
   
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
     assert(obj);//入队之前要判断一下队是否满了
     if(myCircularQueueIsFull(obj))
     return false;
     else
     {
          obj->a[obj->rear] = value;
          obj->rear = (obj->rear+1)%(obj->k);
          return true;    
     }
      
     

}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj);
    //需要判断队列是否为空
    if(myCircularQueueIsEmpty(obj))
    return false;
    else
    {
        obj->front = (obj->front+1)%(obj->k);
        return true;
    }
}

int myCircularQueueFront(MyCircularQueue* obj) {
   assert(obj);
     if(myCircularQueueIsEmpty(obj))
     return -1;
     return obj->a[obj->front];

}

int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj);
    if (myCircularQueueIsEmpty(obj))
        return -1;
    if (obj->rear == 0)
        return obj->a[obj->k-1];

    return obj->a[obj->rear - 1];//这边要注意一下 当这个rear值为0的时候呢？
    //此时-1的话就会造成越界访问，所以应该加上第二个判定条件
}

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

bool myCircularQueueIsFull(MyCircularQueue* obj) {
   assert(obj);
    return ((obj->rear+1)%(obj->k))==obj->front;
}

void myCircularQueueFree(MyCircularQueue* obj) {
      assert(obj);
      free(obj->a);
      free(obj);

}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(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
101
102

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/573741