Shulou(Shulou.com)06/02 Report--

This article mainly explains "how to design the front, middle and back queues in C language". The content in the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought. Let's study and learn how C language designs the front, middle and back queues.

Basic concept of queue

Queue is the most common concept, and queues are often needed in daily life. if you look at the queue carefully, you will find that the queue is a kind of logical structure and a special linear table. The special features are:

Linear tables can only be operated on fixed ends

As long as the above conditions are met, this special linear table will present a "first-in, first-out" logic, which is called a queue.

Since it is agreed that operations can only be performed at both ends of the linear table, a special name is given to the insertion and deletion of the queue, a special linear table:

Line header: you can delete one end of a node

End of line: can be inserted into one end of the node

Queuing: after the node is inserted at the end of the queue, the function name is usually enQueue ()

Queuing: the queue head node is removed from the queue, and the function name is usually outQueue ()

Take the head of the line: get the element of the head of the line, but do not leave the team. The function name is usually front ().

This topic is the basic queue structure in the manual data structure, there are two commonly used, one is realized by linked list, the other is implemented by array.

1. If the array implements typedef struct {int value [1000]; int len;} FrontMiddleBackQueue; FrontMiddleBackQueue* frontMiddleBackQueueCreate () {FrontMiddleBackQueue* queue = (FrontMiddleBackQueue*) malloc (sizeof (FrontMiddleBackQueue)); memset (queue,0,sizeof (FrontMiddleBackQueue)); return queue;} void insert (FrontMiddleBackQueue* obj, int pos, int val) {/ / insert val at the pos position, the number after the pos (starting from 0) position is moved back one position, and the queue length is increased by 1 int I = 0 For (iTunobj-> len; I > pos; iMurray -) {obj- > value [I] = obj- > value [I-1];} obj- > value [pos] = val; obj- > len++;} int pop (FrontMiddleBackQueue* obj, int pos) {/ / pop up the val of the pos position, then pos (starting from 0) moves forward uniformly, and the queue length is reduced by one if (obj- > len = 0) return-1 Int I = 0; int popval = obj- > value [pos]; / / save the number of pos locations first, otherwise the following shift operation overrides the value of pos locations for (iposs; ilen-1; ipositions +) {obj- > value [I] = obj- > value [iTunes 1];} obj- > len--; return popval;} void frontMiddleBackQueuePushFront (FrontMiddleBackQueue* obj, int val) {insert (obj,0,val) } void frontMiddleBackQueuePushMiddle (FrontMiddleBackQueue* obj, int val) {insert (obj,obj- > len/2,val);} void frontMiddleBackQueuePushBack (FrontMiddleBackQueue* obj, int val) {insert (obj,obj- > len,val);} int frontMiddleBackQueuePopFront (FrontMiddleBackQueue* obj) {return pop (obj,0);} int frontMiddleBackQueuePopMiddle (FrontMiddleBackQueue* obj) {return pop (obj, (obj- > len-1) / 2);} int frontMiddleBackQueuePopBack (FrontMiddleBackQueue* obj) {return pop (obj,obj- > len-1) } void frontMiddleBackQueueFree (FrontMiddleBackQueue* obj) {free (obj);} / * * Your FrontMiddleBackQueue struct will be instantiated and called as such: * FrontMiddleBackQueue* obj = frontMiddleBackQueueCreate (); * frontMiddleBackQueuePushFront (obj, val); * frontMiddleBackQueuePushMiddle (obj, val); * frontMiddleBackQueuePushBack (obj, val); * int param_4 = frontMiddleBackQueuePopFront (obj); * int param_5 = frontMiddleBackQueuePopMiddle (obj); * int param_6 = frontMiddleBackQueuePopBack (obj); * frontMiddleBackQueueFree (obj); * /

Running result

2, linked list implementation

1. The linked list structure is designed. The linked list maintains a head node and a tail node, the head node is always at the front and the data of the head node stores the number of nodes of the whole queue, and the tail node is always the last node.

2. Design insert node function and delete node function. Push and pop operations only need to pass different parameters according to different scenarios to complete the unified operation.

Typedef struct tag_Node {int data; struct tag_Node* next, * prev;} Node; typedef struct {Node* front; Node* rear;} FrontMiddleBackQueue; FrontMiddleBackQueue* frontMiddleBackQueueCreate () {FrontMiddleBackQueue* que = (FrontMiddleBackQueue*) malloc (sizeof (FrontMiddleBackQueue)); que- > front = (Node*) malloc (sizeof (Node)); que- > rear = (Node*) malloc (sizeof (Node)); que- > front- > data = 0; que- > front- > next = NULL Que- > rear- > data = 0; que- > rear- > next = NULL; que- > front- > next = que- > rear; que- > rear- > prev = que- > front; return que;} void AddNode (FrontMiddleBackQueue* obj, Node* cur, int val) {Node* addNode = (Node*) malloc (sizeof (Node)); addNode- > data = val; addNode- > prev = cur- > prev; addNode- > next = cur; cur- > prev- > next = addNode; cur- > prev = prev Obj- > front- > data++; return;} Node* GetMiddleNode (FrontMiddleBackQueue* obj, bool isAdd) {Node* tmp = obj- > front- > next; int len = isAdd? (obj- > front- > data / 2): (obj- > front- > data-1) / 2); for (int I = 0; I

Next;} return tmp;} void frontMiddleBackQueuePushFront (FrontMiddleBackQueue* obj, int val) {AddNode (obj, obj- > front- > next, val); return;} void frontMiddleBackQueuePushMiddle (FrontMiddleBackQueue* obj, int val) {AddNode (obj, GetMiddleNode (obj, true), val); return;} void frontMiddleBackQueuePushBack (FrontMiddleBackQueue* obj, int val) {AddNode (obj, obj- > rear, val); return } int RemoveNode (FrontMiddleBackQueue* obj, Node* cur) {if (obj- > front- > data = = 0) {return-1;} cur- > next- > prev = cur- > prev; cur- > prev- > next = cur- > next; obj- > front- > data--; int item = cur- > data; free (cur); return item;} int frontMiddleBackQueuePopFront (FrontMiddleBackQueue* obj) {return RemoveNode (obj, obj- > front- > next) } int frontMiddleBackQueuePopMiddle (FrontMiddleBackQueue* obj) {return RemoveNode (obj, GetMiddleNode (obj, false));} int frontMiddleBackQueuePopBack (FrontMiddleBackQueue* obj) {return RemoveNode (obj, obj- > rear- > prev);} void frontMiddleBackQueueFree (FrontMiddleBackQueue* obj) {while (RemoveNode (obj, obj- > front- > next)! =-1); free (obj- > front); free (obj- > rear); free (obj); return Your FrontMiddleBackQueue struct will be instantiated and called as such: * FrontMiddleBackQueue* obj = frontMiddleBackQueueCreate (); * frontMiddleBackQueuePushFront (obj, val); * frontMiddleBackQueuePushMiddle (obj, val); * frontMiddleBackQueuePushBack (obj, val); * int param_4 = frontMiddleBackQueuePopFront (obj); * int param_5 = frontMiddleBackQueuePopMiddle (obj); * int param_6 = frontMiddleBackQueuePopBack (obj); * frontMiddleBackQueueFree (obj); * /

Running result:

Thank you for your reading. the above is the content of "how to design the front, middle and rear queues in C language". After the study of this article, I believe you have a deeper understanding of how to design the front, middle and rear queues in C language. the specific use of the situation also needs to be verified by practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.