队列数据结构实现

  1 #include <iostream>
  2 #include<fstream>
  3 using namespace std;
  4 
  5 //顾客信息
  6 struct Inform
  7 {
  8     int Arrival;
  9     int Typed;
 10     int HandleTime;
 11     int RestTime;
 12 };
 13 
 14 //链式存储
 15 struct Comsumer
 16 {
 17     Inform data;
 18     Comsumer* next;
 19 };
 20 
 21 //队列
 22 struct Queue
 23 {
 24     Comsumer* front;
 25     Comsumer* rear;
 26     int QueueSize;
 27 };
 28 
 29 //初始化
 30 void InitQueue(Queue* Q)
 31 {
 32     Q->front = Q->rear = (Comsumer*)malloc(sizeof(Comsumer));
 33     if (Q->front == NULL) exit(OVERFLOW);
 34     Q->front->next = NULL;
 35     Q->QueueSize = 0;
 36 }
 37 
 38 //入队
 39 void EnQueue(Queue* Q,Inform* e)
 40 {
 41     Comsumer* s = (Comsumer*)malloc(sizeof(Comsumer));
 42     if (s == NULL) exit(OVERFLOW);
 43 
 44     s->data.Arrival = e->Arrival;
 45     s->data.HandleTime = e->HandleTime;
 46     s->data.RestTime = e->RestTime;
 47     s->data.Typed = e->Typed;
 48 
 49     Q->rear->next = s;
 50     Q->rear = s;
 51     Q->rear->next = NULL;
 52     Q->QueueSize++;
 53 }
 54 
 55 //出队
 56 void DeQueue(Queue* Q)
 57 {
 58     if (Q->front == Q->rear) return;
 59 
 60     Comsumer* p = Q->front->next;
 61     Q->front->next = p->next;
 62     if (Q->rear == p) Q->rear = Q->front;
 63     free(p);
 64     Q->QueueSize--;
 65 }
 66 
 67 //判断队列是否为空
 68 bool IsEmpty(Queue* Q)
 69 {
 70     if (Q->front == Q->rear) return true;
 71 
 72     return false;
 73 }
 74 
 75 //更新每个队列
 76 void UpdateQueue(Queue* q, int NowTime)
 77 {
 78     Comsumer* p = q->front->next;
 79     if (p != NULL)
 80     {
 81         p->data.RestTime=p->data.RestTime-NowTime;
 82         if (p->data.RestTime <= 0)
 83             DeQueue(q);
 84     }
 85 }
 86 
 87 //选择某个队加入
 88 void QueueSelect(Inform*p,Queue*A,Queue*B,Queue*C)
 89 {
 90     if (p->Typed == 1)
 91     {
 92         if (A->QueueSize <= C->QueueSize)
 93             EnQueue(A, p);
 94         else if (A->QueueSize > C->QueueSize)
 95             EnQueue(C, p);
 96     }
 97     else if (p->Typed == 2)
 98     {
 99         if (B->QueueSize <= C->QueueSize)
100             EnQueue(B, p);
101         else if (B->QueueSize > C->QueueSize)
102             EnQueue(C, p);
103     }
104 }
105 
106 //末尾出队
107 void eQueue(Queue* Q)
108 {
109     Comsumer* p = Q->front->next;
110     while (p->next->next != NULL)
111     {
112         p = p->next;
113     }
114     Q->rear = p;
115 }
116 
117 //根据其他的调整队伍
118 void UpdateSelect(Queue*A, Queue* B, Queue* C)
119 {
120     //C的人数比A少两个就要找A队尾去C
121     if (A->QueueSize - C->QueueSize >= 2)
122     {
123         Inform* temp = (Inform*)malloc(sizeof(Inform));
124         temp->Arrival = A->rear->data.Arrival;
125         temp->HandleTime = A->rear->data.HandleTime;
126         temp->RestTime = A->rear->data.RestTime;
127         temp->Typed = A->rear->data.Typed;
128         EnQueue(C, temp);
129         eQueue(A);
130     }
131     //C的人数比B少两个就要找B队尾去C
132     else if (B->QueueSize - C->QueueSize >= 2)
133     {
134         Inform* temp = (Inform*)malloc(sizeof(Inform));
135         temp->Arrival = B->rear->data.Arrival;
136         temp->HandleTime =B->rear->data.HandleTime;
137         temp->RestTime = B->rear->data.RestTime;
138         temp->Typed = B->rear->data.Typed;
139         EnQueue(C, temp);
140         eQueue(B);
141     }
142 }
143 
144 int main()
145 {
146     fstream fp;
147     fp.open("text2.txt", ios::in);
148 
149     int N;
150     fp >> N;//读取窗口数
151 
152     Queue* A=(Queue*)malloc(sizeof(Queue));
153     Queue* B = (Queue*)malloc(sizeof(Queue));
154     Queue* C = (Queue*)malloc(sizeof(Queue));
155     InitQueue(A);
156     InitQueue(B);
157     InitQueue(C);
158 
159     int MaxTime=0;
160     while (!fp.eof())
161     {
162         //每次读一个进队
163         Inform* temp=(Inform*)malloc(sizeof(Inform));
164         fp >> temp->Arrival >> temp->Typed >> temp->HandleTime;
165         temp->RestTime = temp->HandleTime;//刚来还有的办理时间就是办理时间
166         int NowTime = temp->Arrival-MaxTime;
167         MaxTime = temp->Arrival;
168 
169         //更新三个队列
170         UpdateQueue(A, NowTime);
171         UpdateQueue(B, NowTime);
172         UpdateQueue(C, NowTime);
173 
174         //新元素入队
175         QueueSelect(temp, A, B, C);
176     }
177 
178     //三个都不为空继续更新并出队
179     while (IsEmpty(A) != true || IsEmpty(B) != true || IsEmpty(C) != true)
180     {
181         //时间增加
182         MaxTime++;
183         //更新三个队列
184         UpdateQueue(A, 1);
185         UpdateQueue(B, 1);
186         UpdateQueue(C, 1);
187 
188         UpdateSelect(A, B, C);
189     }
190     cout << MaxTime;
191 }

链式队列