队列

队列（Queue）是另外一种限定性的线性表，它只允许在表的一端插入元素，而在另外一端删除元素，所有队列具有先进先出（First In First Out,FIFO）的特性。这和我们日常生活的排队一样。在队列中，允许插入的一端称为队尾（Rear）,允许删除的一端称为队头（Front）。

链队列

定义一个结点

LinkQueue.h

#ifndef _LINKQUEUE_H_
#define _LINKQUEUE_H_
typedef struct Node
{
    int data;   //数据域 
    Node *next;   //指针域 
}Node,*LinkQueueNode; 
typedef struct Queue
{
    LinkQueueNode front;
    LinkQueueNode rear;
}*LinkQueue;
LinkQueue InitQueue(LinkQueue);
bool IsEmpty(LinkQueue);
bool EnterQueue(LinkQueue,int*);
bool DeleteQueue(LinkQueue,int*);
bool GetHead(LinkQueue,int*);
void ClearQueue(LinkQueue);
#endif

实现相应的方法

LinkQueue.cpp

#include <stdio.h>
#include "LinkQueue.h"
#include <malloc.h>
LinkQueue InitQueue(LinkQueue Q)
{
    Q = (LinkQueue)malloc(sizeof(Queue));
    Q->front = (LinkQueueNode)malloc(sizeof(Node));
    printf("InitQueue success!1!\n");
    if(Q->front!=NULL)
    {
        Q->rear = Q->front;
        Q->front->next = NULL;
    }
    printf("InitQueue success!!\n");
    return Q;
}
bool IsEmpty(LinkQueue Q)
{
    if(Q->front->next == NULL)
    {
        return true;
    }else{
        return false;
    } 
}
bool EnterQueue(LinkQueue Q,int x)
{
    LinkQueueNode node;
    node = (LinkQueueNode)malloc(sizeof(LinkQueueNode));
    if(node != NULL)
    {
        node->data = x;
        node->next = NULL;
        Q->rear->next = node;
        Q->rear= node;
        printf("Enter Queue Success!!\n") ;
        return true;
    }else{
        printf("Enter Queue Failed!!\n") ;
        return false;
    }
}
bool DeleteQueue(LinkQueue Q,int *x)
{
    LinkQueueNode p;
    if(Q->front == Q->rear)
         return false;
    p = Q->front->next;
    Q->front->next = p->next;
    if(Q->rear == p){
        Q->rear = Q->front;
    }
    
    *x = p->data;
    free(p);
    return true;
}
bool GetHead(LinkQueue Q,int *x)
{
    if(Q->front == Q->rear)
    {
        return false;
    }else{
        LinkQueueNode node = Q->front->next;
        *x = node->data; 
        return true;
    }
}
void ClearQueue(LinkQueue Q)
{
    LinkQueueNode p,q;
    p = Q->front->next;
    while(p != NULL)
    {
        q = p->next;
        free(p);
        p = q;
    }
    printf("clear cpmplete!!\n");
     
}

运行

LinkQueueMain.cpp

#include <stdio.h>
#include "LinkQueue.cpp"
int main(void)
{
    LinkQueue Q;
    Q = InitQueue(Q);
    if(IsEmpty(Q)){
        printf("队列为空\n");
    }else{
        printf("队列不为空"); 
    }
    EnterQueue(Q,11);
    if(IsEmpty(Q)){
        printf("队列为空\n");
    }else{
        printf("队列不为空"); 
    }
    
    int value;
    GetHead(Q,&value);
    printf("队列头部的数字为%d\n",value);
    DeleteQueue(Q,&value);
    printf("出队列的数字为%d\n",value);
    if(IsEmpty(Q)){
        printf("队列为空\n");
    }else{
        printf("队列不为空"); 
    }
    ClearQueue(Q); 
}

运行结果：

InitQueue success!1!
InitQueue success!!
队列为空
Enter Queue Success!!
队列不为空队列头部的数字为11
出队列的数字为11
队列为空
clear cpmplete!!

--------------------------------
Process exited with return value 0
Press any key to continue . . .