第五章：队列

# 第五章：队列

# 概念

只允许在一端进行插入，在另一端进行删除的线性表
重要术语：队头、队尾、空队列
特点：先进先出（FIFO）

# 顺序队列（不带头结点）

# 定义

#define MaxSize 10

/* 结点的结构体 */
typedef struct
{
  int data[MaxSize]; // 静态数组存放队中元素
  int front, rear;  // 队头指针（从0开始）和队尾指针（指向即将被插入的元素下标）
} SqQueue;

1
2
3
4
5
6
7
8

# 初始化

/* 初始化操作 */
void InitQueue(SqQueue *Q)
{
  Q->front = 0;
  Q->rear = 0;
}

1
2
3
4
5
6

# 是否为空

/* 是否为空 */
bool QueueEmpty(SqQueue Q)
{
  // 判断队头和队尾是否相等
  return Q.rear == Q.front;
}

1
2
3
4
5
6

# 入队

/* 入队 */
bool EnQueue(SqQueue *Q, int x)
{
  if((Q->rear+1) % MaxSize == Q->front) // 队列已满
    return false;
  Q->data[Q->rear] = x; // 存放数据
  // 循环队列，当队尾指针为MaxSize-1时，那下一次移动队尾指针变成0
  Q->rear = (Q->rear + 1) % MaxSize;
  return true;
}

1
2
3
4
5
6
7
8
9
10

# 出队

/* 出队 */
bool OutQueue(SqQueue *Q, int *x)
{
  if(QueueEmpty(*Q))  // 空队
    return false;
  *x = Q->data[Q->front];
  Q->front = (Q->front + 1) % MaxSize;
  return true;
}

1
2
3
4
5
6
7
8
9

# 获取长度

/* 获取队列元素个数 */
int GetQueueLength(SqQueue *Q)
{
  return (Q->rear + MaxSize - Q->front) % MaxSize;
}

1
2
3
4
5

# 打印

/* 打印 */
void TravelQueue(SqQueue Q)
{
  int j = 0;;
  printf("打印：\n");
  while (j < Q.rear)
  {
    printf("%d --- %d\n", j, Q.data[j]);
    j++;
  }
}

1
2
3
4
5
6
7
8
9
10
11

# 链式队列（带头结点）

# 定义

/* 结点的结构体 */
struct LinkNode
{
  int data;
  struct LinkNode *next;
};
typedef struct LinkNode LinkNode;
struct LinkQueue
{
  LinkNode *fornt, *rear;
};
typedef struct LinkQueue LinkQueue;

1
2
3
4
5
6
7
8
9
10
11
12

# 初始化

/* 初始化操作 */
void InitQueue(LinkQueue *Q)
{
  Q->fornt = Q->rear = (LinkNode *)malloc(sizeof(LinkNode));
  Q->fornt->next = NULL;
}

1
2
3
4
5
6

# 是否为空

/* 是否为空 */
bool QueueEmpty(LinkQueue Q)
{
  return Q.fornt == Q.rear;
}

1
2
3
4
5

# 入队

/* 入队（带头结点） */
bool EnQueue(LinkQueue *Q, int x)
{
  LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
  p->data = x;
  p->next = NULL;
  Q->rear->next = p;
  Q->rear = p;
  return true;
}

1
2
3
4
5
6
7
8
9
10

# 出队

/* 出队（带头结点） */
bool OutQueue(LinkQueue *Q, int *x)
{
  if(Q->fornt == Q->rear)  // 空队
    return false;
  LinkNode *p = (*Q).fornt->next;
  x = p->data;
  if(Q->rear == p)  // 最后一个结点出队情况
    Q->rear = Q->fornt; // 表尾指针指向头结点
  free(p);
  return true;
}

1
2
3
4
5
6
7
8
9
10
11
12

# 链式队列（不带头结点）

# 定义

同带头结点的定义

# 初始化

/* 初始化操作（不带头结点） */
void InitQueue2(LinkQueue *Q)
{
  Q->fornt = Q->rear = NULL;
}

1
2
3
4
5

# 入队

/* 入队（不带头结点） */
bool EnQueue2(LinkQueue *Q, int x)
{
  LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
  p->data = x;
  p->next = NULL;
  if(Q->fornt == NULL)
  {
    Q->fornt = p;
    Q->rear = p;
  }
  else
  {
    Q->rear->next = p;
    Q->rear = p;
  }
  return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 出队

/* 出队（不带头结点） */
bool OutQueue2(LinkQueue *Q, int *x)
{
  if(Q->fornt == NULL)  // 空队
    return false;
  LinkNode *p = (*Q).fornt;
  x = p->data;
  Q->fornt = p->next;
  if(Q->rear == p)  // 最后一个结点出队情况
    Q->fornt = Q->rear = NULL;
  free(p);
  return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

#数据结构 #考研

上次更新: 2020/11/05, 15:11:00

← 第四章：栈第六章：串→