Home>

How are queues defined in a programming language?We share our experience with you.

Definition of the queue

Queues are restricted to insert operations at one end.The delete operation of the node is fixed on the linear table at the other end.

The queue is like a pipe with open ends.The end allowed to be inserted is called the team head,The end allowed to be deleted is called the tail of the line.The head of the team and the tail of the team are indicated by a "pointer", which is called the head of the team and the tail of the team.A queue without any nodes is called an "empty queue". The characteristic of a queue is that the queue's queuing order and dequeuing order are determined according to the queue entry time.That is, the advanced team will go out first.Therefore, the queue is also called FIFO.Referred to as fifo (first in first out) table.

step

A queue is a data structure that stores elements that have not yet been processed but need to be processed in a certain order.

A queue is a linear table of first in first out (fifo).The characteristic is that the elements of the advanced team leave the team first.

Queues allow inserts on only one end of the table,And delete the element at the other end.

The tail of the queue is the end of the queue that is allowed to be inserted;The head of the queue is the end of the queue that is allowed to be deleted.

The sequence table q [m] is generally used to store the elements in the queue.m is the maximum number of elements the queue can store.

The front team leader pointer points to the location where the team leader element is stored;The rear tail pointer points to the next position of the tail element.

Sequential queues and their operations

Sequential storage structure

A queue stored by a sequential storage structure is called a sequential queue.As with the sequence table,Store in a one-dimensional array.The head is at the low-order end of the array,The tail of the team is set at the bottom of the high.The head and tail pointer values ​​are the indices of the array elements.The opposite pointer always points to the previous node position of the opposite node,The initial value is 0. The tail pointer is pointing to the tail node position,The initial value is also 0.

Queue initial conditions:team head pointer=team tail pointer=0

Queue full condition:tail pointer=m (set the current capacity of the queue to m)

Queue empty condition:team head pointer=team tail pointer

Structure is defined in queuecs.c file

#define dt char
#define m 100
typedef struct {
  dt data [m];
  int front, rear;
} sequeue;

data [m] is also an array for a queue,front is the team head pointer,rear is the tail pointer.(Note:front and rear are integer types,(Not pointer type), when front=rear=0, it is the initial queue.Because the index of the first element of an array in C is 0 instead of 1;it is agreed here that the array element data [0] is idle.

Operations on a sequential queue

(1) Create a queue

Initialize the queue,Team leader and team pointer=0.

Write method declaration in queuecontrol.h

/*
 Create a queue
 * /
sequeue initqueue ();

Implement this method in queuecontrol.c

#include "queuecontrol.h"
/*
 Create a queue
 * /
sequeue initqueue () {
  sequeue q;
  //1. Initialize the queue,Team Head Pointer=Team End Pointer=0
  q.front=q.rear=0;
  return q;
}

(2) Insert

Write method declaration in queuecontrol.h

/*
 insert
 * /
sequeue inqueue (sequeue q, dt x);

Implement this method in queuecontrol.c

#include "queuecontrol.h"
sequeue inqueue (sequeue q, dt x) {
  //1. Judge the queue is overflow,Is the tail pointer equal to the maximum application space
  if (q.rear == m) {
    printf ("up overflow \ n");
  } else {
     //2. Insert node from the end of the team
    q.rear ++;
    q.data [q.rear]=x;
    printf ("in success \ n");
  }
  return q;
}

(3) Delete

Write method declaration in queuecontrol.h

/*
 delete
 * /
sequeue outqueue (sequeue q);
/*
 Print queue element
 * /
void printqueue (sequeue q);

Implement this method in queuecontrol.c

#include "queuecontrol.h"
sequeue outqueue (sequeue q) {
  //1. First determine if it is an empty queue
  if (q.front == q.rear) {
    printf ("queue is empty \ n");
  } else {
    //2. Delete the node is deleted from the head of the team
    q.front ++;
     printf ("out success \ n");
  }
  return q;
}
/*
 Print queue element
 * /
void printqueue (sequeue q) {
  //1. Print data from the head of the team
  sequeue temp=q;
  printf ("queue={");
  while (temp.front<temp.rear) {
     temp.front ++;
    if (temp.front == q.front + 1) {
      printf ("%c", temp.data [temp.front]);
    } else {
      printf (",%c", temp.data [temp.front]);
    }
  }
  printf ("} \ n");
}

The main method (int main (int argc, const char * argv []) ()) in main.c calls this method,And make judgments

#include "queuecontrol.h"
int main (int argc, const char * argv []) {
  //Initialize the sequential queue
  sequeue queue=initqueue ();
  printqueue (queue);
  //insert
  queue=inqueue (queue, "a");
  queue=inqueue (queue, "b");
  queue=inqueue (queue, "c");
  queue=inqueue (queue, "d");
  printqueue (queue);
  //delete
  queue=outqueue (queue);
  printqueue (queue);
  return 0;
}

Print results:

queue=(}

in success

in success

in success

in success

queue=(a, b, c, d)

out success

queue=(b, c, d)

program ended with exit code:0

From the print results of the insert queue and delete queue operations,The characteristics of the queue are indeed:first in, first out.

Circular queues and their operations

Storage structure of circular queue

According to the operation and description of the sequential queue,Team tail pointer=m means the team is full,Can no longer insert nodes,When the head of the team is equal to the tail of the team, it means air.But when both the tail pointer and the tail pointer are equal to m, then it means air,Then you cannot insert other nodes,But at this time, the nodes between 0-m are already idle.In this way, many idle nodes cannot be used.Waste of storage space.

A circular queue is a circular ring that connects the head and tail of a sequential queue.Logically, node 1 is treated as the successor node of node m.

Initial condition of circular queue:team head pointer=team tail pointer=0

Circulation queue team full condition:mod (end-of-team pointer +1, m)=head-of-team pointer

Circular queue empty condition:team head pointer=team tail pointer

Team head pointer advance calculation:team head pointer=mod (team head pointer +1, m)

Trailer pointer advance calculation:Trailer pointer=mod (tail pointer +1, m)

Structure is defined in queuecyclecs.c file

#define cdt char
#define cm 5
typedef struct {
  cdt data [cm];
  int front, rear;
} secyclequeue;

Operations on a circular queue

(1) Create a circular queue

Initialize the queue,Team leader and team pointer=0.

Write method declaration in queuecycylecontrol.h

#include "queuecyclecs.c"
/*
 Create a circular queue
 * /
secyclequeue initcyclequeue ();

Implement this method in queuecycylecontrol.c

#include "queuecyclecontrol.h"
/*
 Create a circular queue
 * /
secyclequeue initcyclequeue () {
  secyclequeue q;
  //Team head pointer=team tail pointer=0;
  q.front=q.rear=0;
  return q;
}

(2) Insert

Write method declaration in queuecycylecontrol.h

#include "queuecyclecs.c"
/*
 Circular queue insertion
 * /
secyclequeue incyclequeue (secyclequeue q, char x);

Implement this method in queuecycylecontrol.c

#include "queuecyclecontrol.h"
secyclequeue incyclequeue (secyclequeue q, cdt x) {
  //1. Determine whether the circular queue is full,mod (tail pointer +1, m)=team head pointer
  if ((q.rear + 1)%cm == q.front) {
    printf ("queue is full! \ n");
  } else {
    //2. Insert at the end of the team,Calculating the tail pointer
    q.rear=(q.rear + 1)%cm;
    //3. Set the value of the inserted node
    q.data [q.rear]=x;
    printf ("in cycle queue success! \ n");
  }
  return q;
}

(3) Delete

Write method declaration in queuecycylecontrol.h

#include "queuecyclecs.c"
/*
 Circular queue deletion
 * /
secyclequeue outcyclequeue (secyclequeue q);
/*
 Print circular queue
 * /
void printcyclequeue (secyclequeue q);

Implement this method in queuecycylecontrol.c

#include "queuecyclecontrol.h"
secyclequeue outcyclequeue (secyclequeue q) {
  //1. Determine if the circular queue is empty
  if (q.front == q.rear) {
    printf ("cycle queue is empty! \ n");
  } else {
    //2. Delete the node from the head of the team,Calculate the team head pointer:team head pointer=mod (team head pointer +1, m)
    q.front=(q.front + 1)%cm;
    printf ("out cycle queue success! \ n");
  }
  return q;
}
/*
 Print circular queue
 * /
void printcyclequeue (secyclequeue q) {
  //m=5;
  //1. Print data from the head of the team
  secyclequeue temp=q;
  printf ("queue={");
  //2. The condition of judgment is,Team leader pointer!=Team leader pointer
  while (temp.front!=temp.rear) {
    temp.front=(temp.front + 1)%cm;
    if (temp.front == ((q.front + 1)%cm)) {
      printf ("%c", temp.data [temp.front]);
    } else {
      printf (",%c", temp.data [temp.front]);
    }
  }
  printf ("} \ n");
}

The main method (int main (int argc, const char * argv []) ()) in main.c calls this method,And make judgments

#include "queuecyclecontrol.h"
int main (int argc, const char * argv []) {
  //Create a circular queue
  secyclequeue cq=initcyclequeue ();
  //Insert data 5 nodes, but the maximum is 5, one is idle,The last one can't be added,  cq=incyclequeue (cq, "a");
  cq=incyclequeue (cq, "b");
  cq=incyclequeue (cq, "c");
  cq=incyclequeue (cq, "d");
  cq=incyclequeue (cq, "e");
  printcyclequeue (cq);
  //Delete nodes-three nodes
  cq=outcyclequeue (cq);
  cq=outcyclequeue (cq);
  cq=outcyclequeue (cq);
  printcyclequeue (cq);
  //Insert-two nodes
  cq=incyclequeue (cq, "e");
  cq=incyclequeue (cq, "f");
  printcyclequeue (cq);
  //delete nodes-delete four nodes,Now it is three nodes,The last one cannot be deleted
  cq=outcyclequeue (cq);
  cq=outcyclequeue (cq);
  cq=outcyclequeue (cq);
  cq=outcyclequeue (cq);
  printcyclequeue (cq);
  return 0;
}

Print results:

in cycle queue success!

in cycle queue success!

in cycle queue success!

in cycle queue success!

queue is full!

queue=(a, b, c, d)

out cycle queue success!

out cycle queue success!

out cycle queue success!

queue=(d)

in cycle queue success!

in cycle queue success!

queue=(d, e, f)

out cycle queue success!

out cycle queue success!

out cycle queue success!

cycle queue is empty!

queue=(}

program ended with exit code:0

Chain queues and their operations

The chain storage structure of the queue

The queue stored by the chain storage structure is called a chain queue.The team head pointer points to the head node of the chain queue,If the pointer field of the head node is empty,Is an empty queue;If not empty,A pointer to the first node of the team.

The chain queue has a team head pointer,Its value points to the head node of the queue.It also uniquely marks a chain team.Set a tail pointer to insert nodes.Both the head and tail pointers are pointer variables.

The chain queue has no capacity limit,So within the available storage space,Generally no overflow problem occurs,There are also no false overflow issues such as sequential queues.

Structure defined in queuelinkcs.c

#define ldt char
//node type
typedef struct llnode {
  ldt data;
  struct llnode * next;
} linknode;
//chain queue structure
typedef struct {
  linknode * front, * rear;
} linkqueue;

Operations on the chain queue

(1) Create a chain queue

Write method declaration in queuelinkcontrol.h

#include<stdio.h>
#include "queuelinkcs.c"
/*
 Create a chain team
 * /
linkqueue * initlinkqueue (linkqueue * lq);

Implement this method in queuelinkcontrol.c

#include "queuelinkcontrol.h"
#include<stdlib.h>
/*
 Create a chain team
 * /
linkqueue * initlinkqueue (linkqueue * lq) {
  //Set the team head pointer
  lq->front=(linknode *) malloc (sizeof (linknode));
  lq->front->data="#";//Set the team head pointer,Pointer field
  lq->front->next=null;
  //Initial condition:the team pointer and the team pointer are consistent
  lq->rear=lq->front;
  return lq;
}

(2) Insert

Write method declaration in queuelinkcontrol.h

/*
 Chain team insertion:tail of the team
 * /
linkqueue * inlinkqueue (linkqueue * lq, ldt x);

Implement this method in queuelinkcontrol.c

(3) Delete

Write method declaration in queuelinkcontrol.h

/*
 Chain team deletion:Team leader
 * /
linkqueue * outlinkqueue (linkqueue * lq);
/*
 Print linked list nodes
 * /
void printlinkqueue (linkqueue * lq);

Implement this method in queuelinkcontrol.c

#include "queuelinkcontrol.h"
#include<stdlib.h>
linkqueue * outlinkqueue (linkqueue * lq) {
  if (lq == null || lq->rear == lq->front) {
    printf ("lq is empty! \ n");
    return lq;
  }
  //1. Get the first node
  linknode * frontnextnode;
  frontnextnode=lq->front-&n;next;
  //2. Store the value of the next pointer field of the first node in the next field of the head node
  lq->front->next=frontnextnode->next;
  //3. If the tail node is equal to the value of the next pointer field of the first node,Then the representation is an empty stack,According to the structure of the empty chain queue,Need to modify the tail pointer,Point to the head node.
  if (lq->rear == frontnextnode) {
    lq->rear=lq->front;
  }
  //4. Release the deleted nodes
  free (frontnextnode);
  printf ("out link queue success! \ n");
  return lq;
}
/*
 Print linked list nodes
 * /
void printlinkqueue (linkqueue * q) {
  //Instantiate a lq, in order not to change the original chain q
  linkqueue * lq;
  lq=(linkqueue *) malloc (sizeof (linkqueue));
  lq->front=q->front;
  lq->rear=q->rear;
  printf ("queue={");
  //1. Judge is not an empty linked list
  if (lq!=null&&lq-&rear!=lq-&front;front) {
    int flag=0;
    do {
      //2. Output data
      if (flag == 0) {
        printf ("%c", lq->front->data);
        flag=1;
      } else {
        printf (",%c", lq->front->data);
      }
      //3. The chain head pointer moves backward
      lq->front=lq->front->next;
    } while (lq->front!=lq->rear);
   printf (",%c", lq->front->data);
  }
  printf ("} \ n");
}

The main method (int main (int argc, const char * argv []) ()) in main.c calls this method,And make judgments

#include "queuelinkcontrol.h"
int main (int argc, const char * argv []) {
  //Create a chain queue
  linkqueue * lq=(linkqueue *) malloc (sizeof (linkqueue));
  lq=initlinkqueue (lq);
  //Insert nodes to the chain team
  lq=inlinkqueue (lq, "a");
  lq=inlinkqueue (lq, "b");
  lq=inlinkqueue (lq, "c");
  lq=inlinkqueue (lq, "d");
  printlinkqueue (lq);
  //delete nodes--from the head of the team
  lq=outlinkqueue (lq);
  lq=outlinkqueue (lq);
  printlinkqueue (lq);
  return 0;
}

Print results:

in link queue success!

in link queue success!

in link queue success!

in link queue success!

queue=(#, a, b, c, d)

out link queue success!

out link queue success!

queue=(#, c, d)

program ended with exit code:0

c
  • Previous Notes on using vue to develop mobile management background
  • Next Example of pcntl_fork method for creating child processes in PHP