数据结构_队列

一、数据结构队列的实现

//
// Created by XuYiMing on 2020/2/21.
//

#include <iostream>

using namespace std;

#define MaxSize 100
typedef int ElementType;

//*****************顺序/循环队列******************
typedef struct {
    ElementType data[MaxSize];
    int front, rear;
} SqQueue;

void InitQueue(SqQueue &Q) {        //初始化
    Q.rear = Q.front;
}

bool isEmpty(SqQueue Q) {       //判空
    if (Q.front == Q.rear)
        return true;
    else
        return false;
}

bool EnQueue(SqQueue &Q, ElementType x) {       //入队
    if ((Q.rear + 1) % MaxSize == Q.front)
        return false;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MaxSize;
    return true;
}

bool DeQueue(SqQueue &Q, ElementType &x) {      //出队
    if (Q.rear == Q.front)
        return false;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}

//*******************链式存储队列****************
typedef struct LinkNode {
    ElementType data;
    struct LinkNode *next;
} LinkNode;

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

void InitLinkQueue(LinkQueue &Q) {
    Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));       //建立头结点
    Q.front->next = nullptr;        //初始化为空
}

bool IsLinkEmpty(LinkQueue Q) {     //判空
    if (Q.front == Q.rear)
        return true;
    else
        return false;
}

void EnLinkQueue(LinkQueue &Q, ElementType x) {         //入队
    LinkNode *s = (LinkNode *) malloc(sizeof(LinkNode));
    s->data = x;
    s->next = nullptr;
    Q.rear->next = s;
    Q.rear = s;
}

bool DeLinkQueue(LinkQueue &Q, ElementType &x) {
    if (Q.rear == Q.front)
        return false;
    LinkNode *p = Q.front->next;
    x = p->data;
    Q.front->next = p->next;
    if (Q.rear == p)
        Q.rear = Q.front;
    free(p);
    return true;
}

int main() {

    return 0;
}