队列

循环队列

结构体定义

#include <iostream>
#define MaxSize 50
using namespace std;

typedef struct {
    int data[MaxSize];
    int front, rear;
}SqQueue;

初始化

void init(SqQueue& Q) {
    Q.rear = Q.front = 0;
}

判空

bool isEmpty(SqQueue q) {
    if (q.front==q.rear) {
        return true;
    }
    return false;
}

入队

bool EnQueue(SqQueue &Q,int data) {
    //队满
    if ((Q.rear+1)%MaxSize==Q.front) {
        return false;
    }
    Q.data[Q.rear] = data;
    //1%50 = 1、2%50=2、3%50=3....50%50=0，用这种方式就可以构造一个完整递进闭环
    Q.rear = (Q.rear + 1) %MaxSize;
    return true;
}

出队

bool DeQueue(SqQueue &Q) {
    if (Q.rear==Q.front) {
        return false;
    }
    int x = Q.data[Q.front];
    cout << "出队：" << x << endl;
    //头指针后移
    Q.front = (Q.front + 1) % MaxSize;
    return true;

}

测试

int main()
{
    SqQueue Q;
    init(Q);
    EnQueue(Q, 1);
    EnQueue(Q, 2);
    EnQueue(Q, 3);
    EnQueue(Q, 4);
    
    DeQueue(Q);
    DeQueue(Q);
    DeQueue(Q);
    DeQueue(Q);
}

链式队列

结构体定义

#include <iostream>
using namespace std;

typedef struct LinkNode {
    int data;
    struct LinkNode *next;
}LinkNode;

typedef struct {
    LinkNode* front, * rear;
}LinkedQueue;

初始化

void init(LinkedQueue & Q) {
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));//建立头结点
    Q.front->next = NULL;
}

判空

bool isEmpty(LinkedQueue Q) {
    if (Q.front==Q.rear) {
        return true;
    }
    return false;
}

入队

void EnQueue(LinkedQueue &Q,int data) {
    LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
    s->data = data;
    s->next = NULL;
    Q.rear->next = s;
    Q.rear = s;
   
}

出队

bool DeQueue(LinkedQueue & Q) {
    if (Q.front==Q.rear) {
        return false;
    }
    LinkNode *p = Q.front->next;
    int x = p->data;
    cout << "出队：" <<x<< endl;
    if (Q.rear==p) {
        Q.rear = Q.front;
    }
    free(p);
    return true;
}

测试

int main()
{
    LinkedQueue Q;
    init(Q);
    EnQueue(Q, 1);
    EnQueue(Q, 2);
    EnQueue(Q, 3);
    EnQueue(Q, 4);
    DeQueue(Q);
    DeQueue(Q);
    DeQueue(Q);
    DeQueue(Q);
}