“This is the second day of my participation in the August More Text Challenge. For details, see: August More Text Challenge.”

Follow me for more updates

Data structure and algorithm (I): time complexity and space complexity

Data structure and algorithm (2): stack

Data structure and algorithm (3): queue

Data structure and algorithm (4): single linked list

Data structure and algorithm (5): two-way linked list

Data structure and algorithm (6): hash table

Data Structures and algorithms (7): trees

Data Structure and algorithm (8): sorting algorithm

Data Structures and algorithms (9): classical algorithm interview questions

Introduction to dynamic queues

A queue is a restricted linear table like a stack. A queue is a first-in, first-out (FIFO) storage structure. A stack is a last-in, first-out (FIFO) data structure. The stack can only add or delete elements at the same position, and the queue can only be deleted at the front of the table, while the queue can be inserted at the rear of the table. We call them the queue head and queue tail respectively.

Queues are classified into dynamic queues and static queues. Dynamic queue with linked list implementation, dynamic queue is easy to implement. Static queues are implemented with arrays, and static queues generally must be circular queues. Linked list is used to implement a queue, respectively in the header and footer for the team and the team, of course also can head out of the team, team list end, two ways can ensure fifo features, list don’t have to consider the maximum capacity of the queue, only need to consider whether the list is empty, and the array is used to implement the queue needs to determine whether the queue is empty and whether the queue is full.

Let’s take a look at implementing a queue with a single linked list. In this article, we choose to queue at the top and queue at the bottom

Dynamic queue structure

Initialize the queue and return the head node of an empty linked list. Use length to record the length of the queue. When entering the queue, length+1, when exiting the queue, length-1;

  1. NULL: This method passes the header node returned by initialization. If header.next == NULL, the queue is empty

  2. New: LinkNode*new = [LinkNode new]; LinkNode*new = [LinkNode new]; new.data = data; Next = header.next; header.next = new; And make length++;

  3. Queue out: This method passes in the header that was originally returned, evaluates for null, and then uses a while loop to find the penultimate element, as follows :while (current-nex.next! = NULL) {current = current.next; }, and then empty the next node from the penultimate node,current.next = NULL;

  4. Look at the first element of the queue: This method passes the list’s head, header, and returns header.next. Data if not null

  5. Output all elements of the queue: If the while loop is in reverse order, if you want to output in positive order of insertion, there are a number of scenarios:

For example, we can use an array, using a while loop to add each element to a new array, and then output the array in reverse order.

Solution 2: Use the while loop to add elements in reverse order to a new queue, and then output the new queue in reverse order, reverse + reverse = positive

Dynamic queue complete code

// linkqueue. h file @class LinkNode; @interface LinkQueue: NSObject /** Queue length */ @property (nonatomic,assign) int length; -(LinkNode*)createQueue; / / team empty - (BOOL) isEmpty (LinkNode *) header; // enqueue -(void)enqueue:(NSString*)data header:(LinkNode*)header; / / a team - (nsstrings *) to dequeue (LinkNode *) header; // Check the header element -(NSString*)getFront (LinkNode*)header; // display multiple elements -(void)showQueue:(LinkNode*)header; @end @interface LinkNode: NSObject /** The actual data stored. The data can be any type */ @Property (nonatomic,strong) NSString * data; /**next pointer to the next element */ @property (nonatomic,strong) LinkNode *next; @endCopy the code
Linkqueue. m file @implementation LinkQueue // initialize, return an empty list with header nodes -(LinkNode*)createQueue{LinkNode*header = [LinkNode new]; header.next = NULL; return header; } // team empty -(BOOL)isEmpty:(LinkNode*)header{return header.next == NULL; -(void)enqueue:(NSString*)data header:(LinkNode*)header{LinkNode*new = [LinkNode new]; new.data = data; new.next = header.next; header.next = new; self.length++; } -(NSString*)dequeue:(LinkNode*)header{if ([self isEmpty:header]) {printf(" queue isEmpty \n"); return NULL; } LinkNode*current = header; while (current.next.next ! = NULL) {// Find the penultimate node current = current.next; } LinkNode*node = current.next; current.next = NULL; self.length--; return node.data; } // look at the header element -(NSString*)getFront (LinkNode*)header{if ([self isEmpty:header]) {printf(" queue isEmpty \n"); return NULL; } return header.next.data; } -(void)showQueue:(LinkNode*)header{if ([self isEmpty:header]) {printf(" queue isEmpty \n"); return; } NSMutableArray<NSString*>*arr = [NSMutableArray array]; LinkNode*current = header; while (current.next ! = NULL) { current = current.next; [arr addObject:current.data]; } for (int i = (int)arr.count - 1; i>=0; i--) { printf("%s-->",arr[i].UTF8String); } printf("\n"); } // Output all elements in order // Use the while loop to add elements in reverse order to a new queue, then output the new queue in reverse order, reverse + reverse = positive order -(void)showQueue2:(LinkNode*)header{if ([self isEmpty:header]) {printf(" queue is empty \n"); return; } LinkQueue*queue = [LinkQueue new]; LinkNode*header_new = [queue createQueue]; LinkNode*current = header; while (current.next ! = NULL) { current = current.next; [queue enqueue:current.data header:header_new]; } LinkNode*current_new = header_new; while (current_new.next ! = NULL) { current_new = current_new.next; printf("%s-->",current_new.data.UTF8String); } printf("\n"); /* -(void)showQueue3:(LinkNode*)header{if ([self isEmpty:header]) {printf(" queue isEmpty \n"); return; } LinkNode*current = header; while (current.next ! = NULL) { current = current.next; printf("%s-->",current.data.UTF8String); } printf("\n"); } */ @end @implementation LinkNode @endCopy the code
-(void)LinkQueueCase{LinkQueue*queue = [LinkQueue new]; LinkNode*header = [queue createQueue]; // Print the queue [queue showQueue:header]; [queue enqueue:@"a" header:header]; [queue enqueue:@"b" header:header]; // Print the queue [queue showQueue:header]; NSString*data1 = [queue dequeue:header]; Printf (" outqueue :%s \n", data1.utf8string); // Print the queue [queue showQueue:header]; NSString*data2 = [queue dequeue:header]; NSString*data2 = [queue dequeue:header]; Printf (" outqueue :%s \n", data2.utf8string); NSString*data3 = [queue dequeue:header]; NSString*data3 = [queue dequeue:header]; Printf (" outqueue :%s \n", data3.utf8string); // Print the queue [queue showQueue:header]; }Copy the code

1) Circular queue of queues

Pay attention to my

If you think I wrote a good, please point to follow me your support is my more the biggest motivation!