- 队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
- 与栈相反，队列是一种先进先出（First In First Out, FIFO）的线性表。
-
与栈相同的是，队列也是一种重要的线性结构，实现一个队列同样需要顺序表或链表作为基础。
typedef struct QNode {
ElemType data;
struct QNode *next;
} QNode, *QueuePrt;
typedef struct {
QueuePrt front, rear; // 队头、尾指针
} LinkQueue;
-
我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。（注：头结点不是必要的，但为了方便操作，我们加上了。）
-
空队列时，front和rear都指向头结点。
- 创建一个队列要完成两个任务：一是在内存中创建一个头结点，二是将队列的头指针和尾指针都指向这个生成的头结点，因为此时是空队列。
initQueue(LinkQueue *q)
{
q->front=q->rear=(QueuePtr)malloc(sizeof(QNode));
if( !q->front )
exit(0);
q->front->next = NULL;
}
InsertQueue(LinkQueue *q, ElemType e)
{
QueuePtr p;
p = (QueuePtr)malloc(sizeof(QNode));
if( p == NULL )
exit(0);
p->data = e;
p->next = NULL;
q->rear->next = p;
q->rear = p;
}
- 出队列操作是将队列中的第一个元素移出，队头指针不发生改变，改变头结点的next指针即可。
-
出队列的操作过程如下：
- 如果原队列只有一个元素，那么我们就应该处理一下队尾指针。
DeleteQueue(LinkQueue *q, ELemType *e)
{
QueuePtr p;
if( q->front == q->rear )
return;
p = q->front->next;
*e = p->data;
q->front->next = p->next;
if( q->rear == p )
q->rear = q->front;
free(p);
}
- 由于链队列建立在内存的动态区，因此当一个队列不再有用时应当把它及时销毁掉，以免过多地占用内存空间。
DestroyQueue(LinkQueue *q)
{
while( q->front ) {
q->rear = q->front->next;
free( q->front );
q->front = q->rear;
}
}
-
入队列操作其实就是在队尾追加一个元素，不需要任何移动，时间复杂度为O(1)。出队列则不同，因为我们已经架设下标为0的位置是队列的队头，因此每次出队列操作所有元素都要向前移动。
- 解决假溢出的办法就是如果后面满了，就再从头开始，也就是头尾相接的循环。
- 循环队列它的容量是固定的，并且它的队头和队尾指针都可以随着元素入出队列而发生改变，这样循环队列逻辑上就好像是一个环形存储空间。
-
但要注意的是，在实际的内存当中，不可能有真正的环形存储区，我们只是用顺序表模拟出来的逻辑上的循环。
- 让front或rear指针不断加1，即时超出了地址范围，也会自动从头开始。我们可以采取取模运算处理：
- (rear+1) % QueueSize
- (front+1) % QueueSize
-
取模就是取余数的意思，他取到的值永远不会大于除数
定义一个循环队列
#define MAXSIZE 100
typedef struct
{
ElemType *base; // 用于存放内存分配基地址
// 这里你也可以用数组存放
int front;
int rear;
}
initQueue(cycleQueue *q)
{
q->base = (ElemType *) malloc (MAXSIZE * sizeof(ElemType));
if( !q->base )
exit(0);
q->front = q->rear = 0;
}
InsertQueue(cycleQueue *q, ElemType e)
{
if( (q->rear+1)%MAXSIZE == q->front )
return; // 队列已满
q->base[q->rear] = e;
q->rear = (q->rear+1) % MAXSIZE;
}
DeleteQueue(cycleQueue *q, ElemType *e)
{
if( q->front == q->rear )
return ; // 队列为空
*e = q->base[q->front];
q->front = (q->front+1) % MAXSIZE;
}
网友评论