Implementation of C language data structure linked list queue

Implementation of C language data structure linked list queues

1. Write it out front

A queue is a linear table that is the opposite of a stack and follows the first-in, first-out principle.

This code is the C language implementation code of pseudo-code in professor yan weimin's data structure.

The code not included in the breakdown code is as follows:

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

#define OK 1
#define ERROR 0

typedef int QElemtype;
typedef int status;

2. Code decomposition

2.1 structure definition of queues and nodes

typedef struct QNode // A structural definition of a node 
{
  QElemtype data;
  struct QNode *next;
}QNode,*QueuePtr;

typedef struct{   // Definition of the structure of a queue 
  QueuePtr head;
  QueuePtr rear;
}LinkQueue;

| note:

1. The node of the queue should first save the element, and then guide the location of the element, which is the basis and key of linear storage.

2. Two node Pointers are defined in the queue. The first head is used to represent the queue head, allowing the element to be removed. In contrast, rear is used to represent the end of the queue, allowing elements to be inserted.

3. Why is it so defined?

2.2 initialize and recycle the queue

status initQueue(LinkQueue* que) // Initialization queue 
{
  que->head=que->rear=(QueuePtr)malloc(sizeof(QNode));
  if(!que->head) // This code initializes the user-defined data types in the queue 
    return ERROR;
  return OK;
}
status destoryQueue(LinkQueue* que) // Recovery of the queue 
{
  while(que->head)
  {
    que->rear = que->head->next;
    free(que->head);
    que->head=que->rear;
  }
  return OK;
}

| note:

1. Initialization is as simple as allocating space for two important nodes in the queue.

2. Queue recycling is a clever idea

 The condition of circulation is    The queue head node of a queue  head  There are 
　　　　{
 here rear Play the role of temporary variables, constantly pointing head->next At the same time, release head . This process cleanly cleans up the queue that contains the header nodes. 
 
 　　 　}

2.3 add and remove elements

status enQueue(LinkQueue* que,QElemtype e)
{
  QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
  if(!p) // If space is not available, exit 
    return ERROR;
  p->data=e;
  p->next=NULL;

  que->rear->next = p;
  que->rear=p;
  return OK;
}

status delQueue(LinkQueue* que,QElemtype *t)
{
  if(que->rear==que->head)
    return ERROR; // The queue is empty 

  QueuePtr p = que->head->next;
  *t=p->data;

  que->head->next=p->next;
  if(que->rear==p) // The judgment is   Make sure that when you empty the queue, let rear The pointer goes back to its place. 
    que->rear=que->head;
  free(p);
  return OK;
}

| note:

1. Idea of adding elements: create a new node and assign a value to it (data, next). Have the tail of the queue connect to this node and update the tail node at the same time.

2. Idea of deleting elements: first determine whether the node is empty? The temporary node is then obtained from the queue header to the first node, head- > next, (our head node does not hold the element), gets its address, updates the first node value referred to by the header node to free the address space.

2.4 traverse the queue and test methods

status viewQueue(LinkQueue* que)
{
  if(que->rear == que->head)
    return ERROR;
  
  QueuePtr p =que->head->next;
  while(p)
  {
    printf("val:%d",p->data);
    p=p->next;
  }
  return OK;
}

int main(int argc, char **argv)
{
  LinkQueue myQueue;
  initQueue(&myQueue);
  for(int i=1;i<=5;i++)
    enQueue(&myQueue,i);
  viewQueue(&myQueue);
  
  QElemtype a;
  for(int i=0;i<5;i++)
  {
    delQueue(&myQueue,&a);
    printf("%d\n",a);
  }
  destoryQueue(&myQueue);
  printf("fuck !");  
  return 0;
}