This is the 13th day of my participation in Gwen Challenge

The queue

Only inserts are allowed on one end of the table and deletes on the other.

Head: The head of an end team that is allowed to be deleted

End of line: The end at which penetration is permitted

Common operation: initialize the queue to read the correct element

The sequential representation of queues

The team head pointer points to the team head element, and the team tail pointer points to the next location of the team tail element

#define MaxSzie 50
typedef struct{
    Elemtype data[MaxSize];
    int front ,rear;
}SqQueue;
Copy the code
  • Initial status: Q.front == q.ear == 0
  • Enter the team operation: when the team is not satisfied, first send the value to the end of the team element, and then add 1 to the end of the team pointer
  • Exit operation: when the team is not empty, take the value of the team head element first, and then add 1 to the team head pointer

Circular queue

  • Initial: q.front = q.ear = 0
  • Q.front = (q.front + 1) %MaxSize
  • Q.ear = (q.ear + 1)%MaxSize
  • Queue length: (q.ear + MaxSize – q.fold) % MaxSize

Add a data member to the type that represents the number of elements of the element

  • Queue empty condition: q.ise == 0
  • Q.size == MaxSize

Both have q.ear == q.front

Add a tag data member to the type. If tag==0, q.fold == q.ear will be empty due to deletion. Tag == 1 if q.front == q.ear queue full due to insertion

/ / initialization
void InitQueue(SqQueue &Q){
    Q.rear = Q.front = Q;
}
// Determine whether the queue is empty
bool isEmpty(SqQueue Q){
    if(Q.rear == Q.front) return true;
    return false; 
}
/ / team
bool EnQueue(SqQueue &s,Elemtype x){
    if((Q.rear+1)%MaxSize ==Q.front)return false;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1)%MaxSize;
    return true;
}
/ / out of the team
bool DeQueue(SqQueue &s,Elemtype x){
    if(Q.rear == Q.front)return false;
    // The team in question cannot be used when it is full
    x= Q.data[Q.front];
    Q.front = (Q.front+1)%MaxSize;
    return true;
    }
Copy the code

Chain storage of queues

Chaining is especially useful when there are a large number of data elements

A singly linked list with both a header and a tail pointer

typedef struct{
    Elemtype data;
    struct LinkeNode *next;
}LinkNode;
typedef struct{
    LinkNode *front,*rear;
}LinkQueue;
Copy the code

whenQ.front ==NULLandQ.rear ==NULL, the chain queue is empty

  • When leaving a queue, first determine whether the queue is empty, if not, take out the queue head element, and let q.front point to the next node
    • If this node is the last one, q.front Q is set,rear is NULL
  • To join the queue, create a new node to insert and point q.ear to the new node
    • If the old queue is empty, let Q,front point to the new node

Very trouble! , add a header

/ / initialization
void InitQueue(LinkQueue &Q){
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q.front -> next = NULL;
}
// Determine whether the queue is empty
bool IsEmpty(LinkQueue Q){
    if(Q.front == Q.rear) return true;
    return false;
}
/ / team
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = null;
    Q.rear->next = s;
    Q.rear = s;
}
/ / out of the team
bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front == Q.rear)return false;
    LinkNode *p=Q.front->next;
    x = p->data;
    Q.front->next =p->next;
    if(Q.rear == p)Q.rear = Q,front;
    free(p);
    return true; 
}
Copy the code

deque

Both ends can join and leave the team

Output constrained dual-ended queues: allow insertion and deletion at one end and only insertion at the other