队列
2018-09-11 本文已影响33人
qianranow
0. 顺序存储结构
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20
typedef struct Node {
int Data[MAXSIZE];
int front;
int rear;
}QNode, *Queue;
Queue CreateQueue(int MaxSize) {
Queue Q;
Q = (Queue)malloc(sizeof(QNode));
Q -> front = 0;
Q -> rear = 0;
return Q;
}
void AddQ(Queue PtrQ, int item) {
if ((PtrQ -> rear + 1) % MAXSIZE == PtrQ -> front) {
printf("队列满");
return;
}
PtrQ -> rear = (PtrQ -> rear + 1) % MAXSIZE;
PtrQ -> Data[PtrQ -> rear] = item;
}
int DeleteQ(Queue PtrQ) {
if (PtrQ -> front == PtrQ -> rear) {
printf("队列空");
return -2;
} else {
PtrQ -> front = (PtrQ -> front + 1) % MAXSIZE;
return PtrQ -> Data[PtrQ -> front];
}
}
int Length(Queue Q) {
return (Q -> rear - Q -> front + MAXSIZE) % MAXSIZE;
}
1. 链式存储结构
#include <stdio.h>
#include <stdlib.h>
struct Node {
int Data;
struct Node *Next;
};
struct QNode {
struct Node *front;
struct Node *rear;
};
typedef struct QNode * Queue;
// 创建空队列
Queue CreateQueue() {
Queue Q;
Q = (Queue)malloc(sizeof(struct QNode));
Q -> front = NULL;
Q -> rear = NULL;
return Q;
}
void AddQ(Queue PtrQ, int item) {
struct Node *TmpCell = (struct Node *)malloc(sizeof(struct Node));
TmpCell -> Data = item;
TmpCell -> Next = NULL;
if (PtrQ -> front == NULL) { // 队列为空，进第一个元素
PtrQ -> rear = PtrQ -> front = TmpCell;
} else {
PtrQ -> rear -> Next = TmpCell;
PtrQ -> rear = TmpCell;
}
}
int DeleteQ(Queue PtrQ) {
struct Node *FrontCell;
int FrontItem;
if (PtrQ -> front == NULL) {
printf("队列空");
return -2;
}
FrontCell = PtrQ -> front;
if (PtrQ -> front == PtrQ ->rear) { // 队列只有一个元素
PtrQ -> front = PtrQ -> rear = NULL;
} else {
PtrQ -> front = FrontCell -> Next;
}
FrontItem = FrontCell -> Data;
free(FrontCell);
return FrontItem;
}
