数据结构-队

基于C/C++顺序队列和链式队列的构建与操作。

---

顺序队列

---

队的结构

#define MaxSize 10
typedef int ElemType;

//顺序队列结构
typedef struct SeqQueue{
    ElemType data[MaxSize];
    int front, rear; // 队列头和队列尾
}SeqQueue;

队的操作

初始化空队

//初始化空队列
SeqQueue *SeqQueue_Init()
{
    SeqQueue *Q = (SeqQueue *)malloc(sizeof(SeqQueue));//分配内存
    Q->rear = Q->front = 0;//初始化对手与队尾
    return Q;
}

是否空队

//是否空队
bool SeqQueue_Is_Empty(SeqQueue *Q)
{
    if (Q->front == Q->rear)//队首与队尾相同时为空队
        return true;
    return false;
}

入队

bool SeqQueue_Push(SeqQueue *Q, ElemType x)
{
    if ((Q->rear + 1) % MaxSize == Q->front) //判断是否队满
    {
        printf("The Queue has been full.\n");
        return false;
    }
    Q->data[Q->rear] = x;
    printf("Elem %d has been in the Queue.\n", Q->data[Q->rear]);
    Q->rear = (Q->rear + 1) % MaxSize;
    return true;
}

出队

//出队
bool SeqQueue_Pop(SeqQueue *Q)
{
    if (SeqQueue_Is_Empty(Q)) //如果空队
        return false;
    printf("Elem %d has been out of the Queue.\n", Q->data[Q->front]);
    Q->data[Q->front] = NULL; //清空队首元素，队首上移
    Q->front = (Q->front + 1) % MaxSize; //循环队列操作
    return true;
}

遍历打印

//循环打印
void SeqQueue_Print(SeqQueue *Q)
{
    for (int i = Q->front; (i + 1) % MaxSize != Q->rear; i++)//取余判断是否循环一遍
    {
        printf("%d ", Q->data[i]);
    }
    printf("\n");
}

···

---

### 链式队列

---

链式队列结构

typedef int ElemType;

//结点结构
typedef struct QNode{
    ElemType data;//数据域
    QNode *next;//指针域
} QNode;

//链式队列结构
typedef struct LinkedQueue{
    QNode *front, *rear; // 队列头和队列尾
}LinkedQueue;

链式队列操作

空队初始化

//初始化空队列
LinkedQueue* LinkedQueue_Init()
{
    LinkedQueue *Q = (LinkedQueue*)malloc(sizeof(LinkedQueue));
    Q->front = Q->rear = (QNode *)malloc(sizeof(QNode));//分配空间给两个指针域结点
    Q->rear->next = Q->front->next = NULL; //初始de后继指针均指向NULL
    return Q;
}

入队

//入队
bool LinkedQueue_Push(LinkedQueue *Q, ElemType x)
{
    //链式队列不用考虑满队
    QNode *r = (QNode*)malloc(sizeof(QNode));//新结点
    r->data = x;                              //插入元素
    r->next = NULL;                           //后继结点为空
    Q->rear->next = r;                        //Q的原队尾结点指向s
    Q->rear = r;                              //更新队尾指针
    printf("Elem %d has been in the Queue.\n", x);
    return true;
}

出队

//出队,需要注意头节点的问题
bool LinkedQueue_Pop(LinkedQueue *Q)
{
    if (LinkedQueue_Is_Empty(Q)) //如果空队
        return false;
    QNode *s=Q->front->next;//辅助结点,指向头结点的下一个
    printf("Elem %d has been out of the Queue.\n",s->data);//跳过头节点
    Q->front->next = s->next;
    // Q->front = Q->front->next; //队首后移动
    free(s);//释放原来的头结点后继
    return true;
}

是否非空

//是否空队
bool LinkedQueue_Is_Empty(LinkedQueue *Q)
{
    if (Q->front==Q->rear)
        return true;
    return false;
}

遍历打印

//循环打印
void LinkedQueue_Print(LinkedQueue *Q)
{
    while(Q->front->next)
    {
        printf("%d ", Q->front->next->data);
        Q->front = Q->front->next;
    }
    printf("\n");
}

···

---

### 测试源码

---

顺序队列源码，请点击这里获取



链式队列源码，请点击这里获取

---

随时补充

---