队列

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;
  
}

---