Written with StackEdit中文版.

单链队列

简介

和栈相反，队列是一种先进先出的线性表，其只允许在表的一端进行插入元素，而在另一端删除元素。

在队列中，允许插入的一端叫做队尾，允许删除的一端叫做队头。

队列的两种存储表示:

  • 链队列 用链表表示的队列，这里只实现单链表队列.
  • 循环队列 队列的顺序表示和实现，在【循环队列】文章中实现.

声明与定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
typedef int QElemType;
typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -1

//单链队列——队列的链式存储结构
typedef struct QNode{
  QElemType data;
  struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
  QueuePtr front; //队头指针
  QueuePtr rear; //队尾指针
}LinkQueue;

//构造一个空队列Q
Status InitQueue(LinkQueue *Q); 
//销毁队列Q，Q不再存在
Status DestroyQueue(LinkQueue* Q); 
//判断队列Q是否为空队列，为空返回TRUE，否则FALSE
Status QueueEmpty(LinkQueue Q); 
//返回队列Q的元素个数
int QueueLength(LinkQueue Q);   
//用e返回Q的队头元素
Status GetHead(LinkQueue Q, QElemType *e);
//插入e为Q的新的队头元素
Status EnQueue(LinkQueue *Q, QElemType e); 
//删除Q的队头元素，并用e返回其值
Status DeQueue(LinkQueue* Q, QElemType* e); 
//遍历队列Q中的所有元素
Status QueueTraverse(LinkQueue Q);

相关方法实现

InitQueue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Status InitQueue(LinkQueue *Q){
  Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
  if (!Q->front){
    printf("存储分配失败!\n");
    exit(OVERFLOW);
  }
  Q->front->next = NULL;//初始化时队头和队尾指针的next都指向空
  return OK;
}//InitQueue
```  
  
#### DestroyQueue
```c
Status DestroyQueue(LinkQueue* Q) {
  while (Q->front) {
    Q->rear = Q->front->next;
    free(Q->front);
    Q->front = Q->rear;
  }
  return OK;
}

QueueEmpty

1
2
3
Status QueueEmpty(LinkQueue Q) {
  return Q.front == Q.rear && Q.rear == NULL;
}

QueueLength

1
2
3
4
5
6
7
8
9
int QueueLength(LinkQueue Q) {
  int count = 0;
  QueuePtr temp = Q.front;
  while (temp != Q.rear) {
    temp = temp->next;
    count++;
  }
  return count;
}

GetHead

1
2
3
4
5
6
7
8
Status GetHead(LinkQueue Q, QElemType* e) {
  if (QueueEmpty(Q)){
    printf("队列为空!\n");
    return ERROR;
  }
  *e = Q.front->data;
  return OK;
}

EnQueue

1
2
3
4
5
6
7
8
9
10
11
12
Status EnQueue(LinkQueue* Q, QElemType e){
  QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
  if (!p){
    printf("入队存储分配失败!\n");
    exit(OVERFLOW);
  }
  p->data = e; 
  p->next = NULL;
  Q->rear->next = p;//原来的指向空指针改为指向新入队的结点
  Q->rear = p;//p为新的队尾
  return OK;
}

DeQueue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Status DeQueue(LinkQueue* Q, QElemType* e){
  //若队列不空，则删除Q的队头元素，用e返回其值，并返回1
  //返回失败则为ERROR
  if (QueueEmpty(*Q)){
    printf("队列为空！\n");
    return ERROR;
  }
  QueuePtr p = Q->front->next;//赋值队头
  *e = p->data;
  Q->front->next = p->next;//队头改变
  if (Q->rear == p)Q->rear = Q->front;//队列空了
  free(p);
  return OK;
}

QueueTraverse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Status QueueTraverse(LinkQueue Q) {
  if (QueueEmpty(Q)) {
    printf("队列为空！\n");
    return ERROR;
  }
  printf("开始遍历队列元素: ");
  QueuePtr temp = Q.front;
  temp = temp->next;
  while (temp) {
    printf("%d ", temp->data);
    temp = temp->next;
  }
  printf("遍历结束！\n");
  return OK;
}

方法测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int main(void){
  LinkQueue MyQueue;
  QElemType e;
  int size;

  InitQueue(&MyQueue);
  printf("输入需要入队的元素个数: ");
  scanf_s("%d", &size);
  printf("输入%d个元素入队\n", size);
  for (int i = 0; i < size; i++){
    scanf_s("%d", &e);
    EnQueue(&MyQueue, e);
    printf("已入队%d个元素\n", i + 1);
  }
  QueueTraverse(MyQueue);
  printf("队列有%d个元素\n", QueueLength(MyQueue));

  printf("需要出队几个元素: ");
  scanf_s("%d", &size);
  if (size > QueueLength(MyQueue)) {
    size = QueueLength(MyQueue);
  }
  for (int i = 0; i < size; i++){
    DeQueue(&MyQueue,&e);
    printf("第%d次, 出队元素为:%d \n",i + 1, e);
  }

  return 0;
}