队列

队列与堆栈不同,队列是一边进,另一边出的表,如下图所示:
queue1

队列的主要操作也比较少,主要的有入队,出队,检查队列是否为空,

队列一般会有两个标志位,即Front和Rear,表示对头和队尾,通过对这两个标志位进行操作,可以对队列进行适当的操作。
queue2

数组形式声明与实现

1
2
3
4
5
6
7
8
9
10
11
struct QueueModel
{
int Capacity;
int Front;
int Rear;
int Size;
ElementType *Array;
};

typedef struct QueueModel *Queue;
typedef int ElementType;

在这个声明中一个队列中有容量参数,2个标志位,一个大小参数,还有一个数组用来存储数据。

判断队列为空

1
2
3
4
int IsEmpty(Queue Q)
{
return Q->size==0;
}

通过对size的控制,来表示队列为空或非空。入队一个节点,则size+1,出队一个节点,则size-1.

队列设置为空

1
2
3
4
5
6
void MakeEmpty(Queue Q)
{
Q->Size = 0;
Q->Front = 1;
Q->Rear = 0;
}

入队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void Enqueue(ELementType X,Queue Q)
{
if(IsFull(Q))
Error("The Queue is Full!!");
else
{
Q->Size++;
Q->Rear = Succ(Q->Rear,Q);
Q->Array[Q->Rear] = X;
}
}

int IsFull(Queue Q)
{
return Q->Size==Q->Capacity;
}

static int Succ(int value,Queue Q)
{
if(++value==Q->Capacity)
value=0;
return value;
}

出队

1
2
3
4
5
6
7
8
9
10
11
12
13
ElementType DeQueue(Queue Q)
{
ElementType tmp;
if(IsEmpty(Q))
Error("The Queue is Empty!!");
else
{
tmp = Q->Array[Q->Front];
Q->Size--;
Q->Front = Succ(Q->Front,Q);
}
return tmp;
}