博客

链式队列为使用链表来实现队列的存储结构。它创建两个指针top与rear分别指向链表头与链表尾部。

下面是一个头节点的示意图：

此时队列中未存储数据，top与rear指针同时指向头节点。

添加一个新节点示意图：

1. rear->next指向新添加的节点node

2. 新添加的节点node成为新的rear节点

删除一个元素示意图如下：

完整代码如下：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define OK 0
#define ERROR -1
#define MALLOC_ERROR -2
#define NULLPTR -3
#define RetStatus int


typedef int QElemType;
// node
typedef struct QNode
{
  QElemType data;
  struct QNode *next; 
}QNode, *QNodePtr;

typedef struct 
{
  // top and rear pointer
  QNodePtr top, rear; 
} LinkQueue;

// create LinkQueue
RetStatus CreateQueue(LinkQueue *Q)
{
  Q->top = Q->rear = (QNode *)malloc(sizeof(QNode));

  if (Q->top == NULL)
  {
    return MALLOC_ERROR;
    /* code */
  }
  
  //b. init head node
  Q->top->next = NULL;

  return OK;
}

// enqueue 尾插法入队
RetStatus EnQueueRear(LinkQueue *Q, QElemType data)
{
  //a. get element with node
  QNode *enElement = (QNode *)malloc(sizeof(QNode));

  if (enElement == NULL)
  {
     return MALLOC_ERROR;
  }
  
  enElement->data = data;
  enElement->next = NULL;

  //b. get relation with rear node
  Q->rear->next = enElement;

  //c. point to new node
  Q->rear = enElement;

  // return new rear
  return OK;
}

// enqueue 头插法入队
RetStatus EnQueueTop(LinkQueue *Q, QElemType data)
{
  //a. get element with node
  QNode *enElement = (QNode *)malloc(sizeof(QNode));
  if (enElement == NULL)
  {
    return MALLOC_ERROR;
  }
  
  enElement->data = data;
  enElement->next = NULL;

  //b. get relation with rear node
  enElement->next = Q->top->next;
  
  //c. point to new node
  Q->top->next = enElement;

  return OK;
}


// delete Queue
RetStatus PrintQueue(LinkQueue *Q)
{
  if (Q->top->next == NULL)
  {
    printf("Queue is empty!\n");;
    return NULLPTR;
  }

  QNode *p = Q->top->next;
  while (p)
  {
    printf("%d ", p->data);
    p = p->next;
  }
  printf("\n");
  return OK;
}

RetStatus DeQueue(LinkQueue *Q)
{
  if (Q->top->next == NULL)
  {
    printf("Queue is empty!\n");
    return NULLPTR;
  }
  
  QNode *p = Q->top->next;
  Q->top->next = p->next;
 // printf("del:%d ", p->data);
  //printf("0x%x ", p);
  if (Q->rear == p)
  {
      Q->rear = Q->top;
  }
  free(p); 
  return OK;
}

int main(void)
{
  LinkQueue Q = {0};

  // create Link Node
  RetStatus ret = CreateQueue(&Q);

  // add node
  /*
  ret = EnQueueRear(&Q, 1);
  ret = EnQueueRear(&Q, 2);
  ret = EnQueueRear(&Q, 3);
  ret = EnQueueRear(&Q, 4);
  ret = EnQueueRear(&Q, 5);
  */
  ret = EnQueueTop(&Q, 6);
  ret = EnQueueTop(&Q, 7);
  ret = EnQueueTop(&Q, 8);
  ret = EnQueueTop(&Q, 9);
  ret = EnQueueTop(&Q, 10);
  // delete node
  ret = PrintQueue(&Q);
  ret = DeQueue(&Q); // 删头
  //ret = DeQueue(&Q);

  ret = PrintQueue(&Q);

  return 0;
}

头插法输出：

尾插法输出：