<数据结构> 队列Queue

作者：weixin_40725706 | 2024-03-01 17:43:56

踩

对于顺序存储的队列,含有两个指针

一.队列Queue：先进先出 FIFO

1.队列有两个指针一个是队首一个是队尾可以理解成链表的头删除和尾添加

2.存储方式：

①顺序存储 ②链式存储

3.顺序存储的应用：循环队列

（以下来自本人看过百度文库后的个人理解）

循环队列：开辟一个数组空间把这个数组空间想象成一个首尾相连的圆环空间存储在这个循环空间的队列就称为循环队列

循环队列存在一个问题就是假溢出什么叫假溢出呢？

假溢出可以理解成：明明这个循环存储空间并没有满但是却不让我们插入新的数据造成一个假的溢出现象

用一个一维数组arr[m]来存储一个循环队列这个循环队列的队列元素为m 元素下标是从0到m-1结束

队首为Head 队尾为Tail 队首指向队头元素的前一个位置队尾指针就是指向队尾元素

当Head为-1时说明这个队列是空的当Tail为m-1的时候说明这个队列是满的

由于队列的性质是链表的头删除和尾添加当Tail为m-1但是Head不等于-1的时候说明这个队列是有空闲空间可以用来存储的但是已经存不进去

如果这个时候要插入新的数据就会出现队满插不进去的现象这种现象就可以叫“假溢出”

4.应用2：优先级队列

优先级队列是由一组数据组成的数据集合给每个元素分配一个数字来标记它的优先级数字越小优先级越高

优先级队列不同于队列的地方是每次出队的是队中优先级最高的元素

如果两个元素的优先级相同那么就按照先进先出的规则进行操作

二.代码实现

1.队列的操作：①Init ②Push ③Pop ④IsEmpty

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 typedef struct node
 5 {
 6     int num;
 7     struct node* pNext;
 8 }MyQueue;
 9 
10 typedef struct node2
11 {
12     int count;
13     MyQueue* pHead;
14     MyQueue* pTail;
15 }Queue;
16 
17 void q_Init(Queue** pQueue)
18 {
19     *pQueue = (Queue*)malloc(sizeof(Queue));
20     (*pQueue) -> count = 0;
21     (*pQueue) -> pHead = NULL;
22     (*pQueue) -> pTail = NULL;
23 }
24 
25 void q_Push(Queue* pQueue,int n)
26 {
27     if(pQueue == NULL) return ;
28 
29     MyQueue* pMyQueue = (MyQueue*)malloc(sizeof(Queue));
30     pMyQueue -> num = n;
31     pMyQueue -> pNext = NULL;
32 
33     if(pQueue -> pHead == NULL)
34     {
35         pQueue -> pHead = pMyQueue;
36         pQueue -> pTail = pMyQueue;
37     }
38     else
39     {
40         pQueue -> pTail -> pNext = pMyQueue;
41         pQueue -> pTail = pMyQueue;
42     }
43 
44     pQueue -> count ++;
45 }
46 
47 int q_Pop(Queue* pQueue)
48 {
49     if(pQueue == NULL || pQueue -> count == 0) return -1;
50 
51     MyQueue* pDel = pQueue -> pHead;
52     int n = pDel -> num;
53     pQueue -> pHead = pQueue -> pHead -> pNext;
54 
55     if(pQueue -> pHead == pQueue -> pTail)
56     {
57         pQueue -> pTail = NULL;
58     }
59 
60     free(pDel);
61     pDel = NULL;
62 
63     pQueue -> count --;
64     return n;
65 }
66 
67 int q_IsEmpty(Queue* pQueue)
68 {
69     return pQueue -> count == 0? 1:0;
70 }
71 
72 int main()
73 {
74     Queue* pQueue;
75     q_Init(&pQueue);
76     q_Push(pQueue,11);
77     q_Push(pQueue,12);
78     q_Push(pQueue,13);
79 
80     printf("%d\n",q_Pop(pQueue));
81     printf("%d\n",q_Pop(pQueue));
82     printf("%d\n",q_Pop(pQueue));
83     printf("%d\n",q_Pop(pQueue));
84     return 0;
85 }

2.用两个栈实现队列的功能

①思想：定义一个新的队列的结构体里面放两个栈的指针

在进行入队操作时首先检查栈2中是否还有元素没有放回栈1 如果栈2中还有元素逐个放回

如果没有把想要入队的元素直接插入到栈1中即可

在进行出队操作时应该先检查栈1中是否还有元素没有放回到栈2中如果栈1中还有元素逐个放回

如果没有在栈2中取走想要得到的元素的值即可

②代码：

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 
  4 typedef struct node
  5 {
  6     int num;
  7     struct node * pNext;
  8 }MyStack;
  9 
 10 typedef struct node2
 11 {
 12     int count;
 13     MyStack* pTop;
 14 }Stack;
 15 
 16 typedef struct node3
 17 {    
 18     int count;
 19     Stack* pStack1;
 20     Stack* pStack2;
 21 }Queue;
 22 
 23 void s_Init(Stack** ppStack)
 24 {
 25     (*ppStack) = (Stack*)malloc(sizeof(Stack));
 26     (*ppStack) -> count = 0;
 27     (*ppStack) -> pTop = NULL;
 28 }
 29 
 30 void s_Push(Stack* pStack,int n)
 31 {
 32     if(pStack == NULL) return ;
 33     
 34     MyStack* pMyStack = (MyStack*)malloc(sizeof(MyStack));
 35     pMyStack -> num = n;
 36     pMyStack -> pNext = pStack -> pTop;
 37     pStack -> pTop = pMyStack;
 38 
 39     pStack -> count ++;
 40 }
 41 
 42 int s_Pop(Stack* pStack)
 43 {
 44     if(pStack == NULL || pStack -> count == 0) return -1;
 45     
 46     MyStack* pDel = pStack -> pTop;
 47     int n = pDel -> num;
 48     pStack -> pTop = pStack -> pTop -> pNext;
 49     free(pDel);
 50     pDel = NULL;
 51 
 52     pStack -> count --;
 53     return n;
 54 }
 55 
 56 void q_Init(Queue** pQueue)
 57 {
 58     *pQueue = (Queue*)malloc(sizeof(Queue));
 59     (*pQueue) -> count = 0;
 60     (*pQueue) -> pStack1 = NULL;
 61     (*pQueue) -> pStack2 = NULL;
 62 
 63     s_Init(&((*pQueue) -> pStack1));
 64     s_Init(&((*pQueue) -> pStack2));
 65 }
 66 
 67 void q_Push(Queue* pQueue,int n)
 68 {
 69     if(pQueue == NULL) return ;
 70 
 71     while(pQueue -> pStack2 -> count != 0)
 72     {
 73         s_Push(pQueue -> pStack1,s_Pop(pQueue -> pStack2));
 74     }
 75 
 76     s_Push(pQueue -> pStack1,n);
 77     pQueue -> count ++;
 78 }
 79 
 80 int q_Pop(Queue* pQueue)
 81 {
 82     if(pQueue -> pStack1 == NULL) return -1; 
 83     while(pQueue -> pStack1 -> count != 0)
 84     {
 85         int n = s_Pop(pQueue -> pStack1);
 86         s_Push(pQueue -> pStack2,n);
 87     }
 88 
 89     int n = s_Pop(pQueue -> pStack2);
 90     while(pQueue -> pStack2 -> count != 0)
 91     {
 92         int n = s_Pop(pQueue -> pStack2);
 93         s_Push(pQueue -> pStack1,n);
 94     }
 95     pQueue -> count --;
 96     return n;
 97 }
 98 
 99 int main()
100 {
101     Queue* pQueue = NULL;
102     q_Init(&pQueue);
103     q_Push(pQueue,10);
104     q_Push(pQueue,11);
105     q_Push(pQueue,12);
106     printf("%d\n",q_Pop(pQueue));
107     printf("%d\n",q_Pop(pQueue));
108     printf("%d\n",q_Pop(pQueue));
109     printf("%d\n",q_Pop(pQueue));
110     printf("%d\n",q_Pop(pQueue));
111     
112     return 0;
113 }

3.用两个队列实现栈的功能

①思想：定义一个新的栈的结构体里面有两个队列的指针

当进行入栈操作的时候如果两个队列都是空的放在哪个队列里面都可以

如果有一个是非空的那么就放在这个非空的队列里入栈成功

当进行出栈操作的时候假设元素都在队列1中（在队列2中同理）

先把队列1中的元素依次出队直到队列1中的元素只剩下一个那么队列1中剩下的这个元素就是要出栈的元素

把这个元素出队列即出栈成功

②代码：

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 
  4 typedef struct node
  5 {
  6     int num;
  7     struct node* pNext;
  8 }MyQueue;
  9 
 10 typedef struct node2
 11 {
 12     int count;
 13      MyQueue* pHead;
 14     MyQueue* pTail;
 15 }Queue;
 16 
 17 typedef struct node3
 18 {
 19     int count;
 20     Queue* pQueue1;
 21     Queue* pQueue2;
 22 }Stack;
 23 
 24 void q_Init(Queue** pQueue)
 25 {
 26     *pQueue = (Queue*)malloc(sizeof(Queue));
 27     (*pQueue) -> count = 0;
 28     (*pQueue) -> pHead = NULL;
 29     (*pQueue) -> pTail = NULL;
 30 }
 31 
 32 void s_Init(Stack** pStack)
 33 {
 34     *pStack = (Stack*)malloc(sizeof(Stack));
 35     (*pStack) -> count = 0;
 36     (*pStack) -> pQueue1 = NULL;
 37     (*pStack) -> pQueue2 = NULL;
 38 
 39     q_Init(&((*pStack) -> pQueue1));
 40     q_Init(&((*pStack) -> pQueue2)); 
 41 }
 42 
 43 void q_Push(Queue* pQueue,int n)
 44 {
 45     if(pQueue == NULL) return ;
 46     
 47     MyQueue* pMyQueue = (MyQueue*)malloc(sizeof(Queue));
 48     pMyQueue -> num = n;
 49     pMyQueue -> pNext = NULL;
 50 
 51     if(pQueue -> pHead == NULL)
 52     {
 53         pQueue -> pHead = pMyQueue;
 54         pQueue -> pTail = pMyQueue;
 55     }
 56     else
 57     {
 58         pQueue -> pTail -> pNext = pMyQueue;
 59         pQueue -> pTail = pMyQueue;
 60     }
 61     
 62     pQueue -> count ++;
 63 }
 64 
 65 int q_Pop(Queue* pQueue)
 66 {
 67     if(pQueue == NULL || pQueue -> count == 0) return -1;
 68     
 69     MyQueue* pDel = pQueue -> pHead;
 70     int n = pDel -> num;
 71     pQueue -> pHead = pQueue -> pHead -> pNext;
 72     
 73     if(pQueue -> pHead == pQueue -> pTail)
 74     {
 75         pQueue -> pTail = NULL;
 76     }
 77 
 78     free(pDel);
 79     pDel = NULL;
 80     
 81     pQueue -> count --;
 82     return n;
 83 }
 84 
 85 int q_IsEmpty(Queue* pQueue)
 86 {
 87     return pQueue -> count == 0? 1:0;
 88 }
 89 
 90 void s_Push(Stack* pStack,int n)
 91 {
 92     if(pStack == NULL || pStack -> pQueue1 == NULL || pStack -> pQueue2 == NULL) return;
 93     
 94     if(!q_IsEmpty(pStack -> pQueue1))
 95     {
 96         q_Push(pStack -> pQueue1,n);
 97     }
 98     else
 99     {
100         q_Push(pStack -> pQueue2,n);
101     }
102 
103     pStack -> count ++;
104 }
105 
106 int s_Pop(Stack* pStack)
107 {
108     if(pStack == NULL || pStack -> pQueue1 == NULL || pStack -> pQueue2 == NULL || pStack -> count == 0) return -1;
109     
110     int n;
111     if(!q_IsEmpty(pStack -> pQueue2))
112     {
113         while(pStack -> pQueue2 -> count > 1)
114         {
115             q_Push(pStack -> pQueue1,q_Pop(pStack -> pQueue2));
116         }
117         n = q_Pop(pStack -> pQueue2);
118     }    
119     else
120     {
121         while(pStack -> pQueue1 -> count > 1)
122         {
123             q_Push(pStack -> pQueue2,q_Pop(pStack -> pQueue1));
124         }
125         n = q_Pop(pStack -> pQueue1);
126     }
127     
128     pStack -> count --;
129     return n;
130 }
131 
132 int main()
133 {
134     Stack* pStack;
135     s_Init(&pStack);
136     s_Push(pStack,11);
137      s_Push(pStack,12);
138     s_Push(pStack,13);
139 
140     printf("%d\n",s_Pop(pStack));
141     printf("%d\n",s_Pop(pStack));
142     printf("%d\n",s_Pop(pStack));
143     printf("%d\n",s_Pop(pStack));
144     return 0;
145 }

转载于:https://www.cnblogs.com/Aaaaaalei0612/p/9767000.html

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