12、数据结构——栈与队列——队列的链式实现（三）

结构体定义

1
2
3
4
5
6
7
8
typedef struct LinkNode { // 链式队列结点定义
    ElemType data[N];
    struct LinkNode *next;
}LinkNode;

typedef struct { // 链式队列
    LinkNode *front, *rear; // 队头、队尾指针
}LinkQueue;

初始化(带头结点)

1
2
3
4
5
6
7
8
void InitQueue(LinkNode &Q) {
    Q.front = Q.rear = (LinkNode *)malloc(sizeof LinkNode);
    Q.front->next = NULL;
}

bool IsEmpty(LinkQueue Q)  {
    return Q.front == Q.rear;
}

初始化(不带头结点)

1
2
3
4
5
6
7
8
void InitQueue(LinkNode &Q) {
	Q.front = NULL;
    Q.rear = NULL;
}

bool IsEmpty(LinkQueue Q)  {
    return Q.front == NULL;
}

入队(带头结点)

1
2
3
4
5
6
7
void EnQueue(LinkQueue &Q, ElemType x) {
    LinkNode *s = (LinkNode *)malloc (sizeof LinkNode);
    s -> data = x;
    s -> next = NULL;
    Q.rear -> next = s;
    Q.rear = s;
}

入队(不带头结点)

1
2
3
4
5
6
7
8
9
10
11
12
void EnQueue(LinkQueue &Q, ElemType x) {
    LinkNode *s = (LinkNode *)malloc (sizeof LinkNode);
    s -> data = x;
    s -> next = NULL;
    if (Q.front == NULL) {
        Q.front = s;
        Q.rear = s;
    } else {
        Q.rear -> next = s;
        Q.rear = s;
    } 
}

出队(带头结点)

1
2
3
4
5
6
7
8
9
bool DeQueue(LinkQueue &Q, ElemType &k)}{ 
    if (Q.front == Q.rear) 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;
}

出队(不带头结点)

1
2
3
4
5
6
7
8
9
10
11
12
bool DeQueue(LinkQueue &Q, ElemType &x) {
    if (Q.front == NULL) return false;
    LinkNode *p = Q.front;
    x = p -> data;
    Q.front = p -> next;
    if (Q.rear == p) {
        Q.front = NULL;
        Q.rear = NULL;
    }
    free(p);
    return true;
}

下一节内容是：13、栈与队列——双端队列！！！

一定要把本节内容看懂再往下看，不然会非常痛苦的哦o(╥﹏╥)oo(╥﹏╥)oo(╥﹏╥)o……..