“This is the first 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 of circular queues

A queue is a first-in, first-out (FIFO) storage structure. 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.

Why must a static queue be a circular queue?

When an element is deleted, the front pointer moves back one bit, and when an element is inserted, the rear pointer moves back one bit. If rear moves to the last position, the data field is not full at this time, but the queue overflows when the element is inserted again. This phenomenon is called “false overflow”. To solve this problem, we introduced circular queues. Circular queue of thinking is very simple, is given we queue size range, on the basis of the original queue, as long as the rear of the queue is full, we are from the front of the queue to insert, in order to achieve the effect of repeated use of space, as a result of the design of circular queue thinking more like a ring, so called circular queue, but it is a single linear.

The structure of circular queues

Circular queue stored data,front,reat,maxsize four elements: where,data represents a data field, which can store any type of elements; Maxsize indicates the maximum capacity of the circular queue, which is also the array length of data. It represents the total operational space of the queue. If 5 is set, the maximum valid data of the queue is 4. Front and rear both start at zero,front is the head pointer,front is the first element in the queue,rear is the tail pointer,rear is the element next to the last element in the queue.

Front = (front + 1) % maxsize; front = (front + 1) % maxsize;

Rear = (rear + 1) % maxsize;

= rear (front == rear);

4) Determine the queue is full: two ways

① (rear + 1) % maxsize == front

② Add a flag parameter, which is 0 when it is deleted and 1 when it is added. If front == rear, the queue is full

Complete code for circular queue

@interface CircleQueue: NSObject - (instanceType)initWithMaxSize:(int)maxSize; / / team full - (BOOL) isFull; / / team empty - (BOOL) isEmpty; / / team - (int) the enqueue (NSObject *) e; / / a team - to dequeue (NSObject *); // View the header element -(NSObject*)getFront; // Count the number of valid data in the queue -(int)getTotalCount; // Show more than one element -(void)showQueue; @endCopy the code
// circlequeue.m file #import "circlequeue.h" @interface CircleQueue() /** Simulate queue with array */ @property (nonatomic,strong) NSMutableArray * data; /** Max */ @property (nonatomic,assign) int maxSize; */ @property (nonatomic,assign) int front; */ @property (nonatomic,assign) int front; /* @property (nonatomic,assign) int rear; /* @property (nonatomic,assign) int rear; @end @implementation CircleQueue - (instancetype)initWithMaxSize:(int)maxSize { self = [super init]; if (self) { self.maxSize = maxSize; self.front = 0; self.rear = 0; // Initialize the array self.data = [[NSMutableArray alloc]initWithCapacity:maxSize]; for (int i = 0; i<maxSize; i++) { [self.data addObject:[NSObject new]]; } } return self; } -(BOOL)isFull{ return (self.rear+1)%self.maxSize == self.front; } -(BOOL)isEmpty{ return self.front == self.rear; } -(int)enqueue:(NSObject*)e{if ([self isFull]) {NSLog(@" queue isFull, cannot join "); return -1; } self.data[self.rear] = e; self.rear = (self.rear+1)%self.maxSize; NSLog(@" Insert successful "); return 0; } -(NSObject*)dequeue{if ([self isEmpty]) {NSLog(@" queue isEmpty, cannot be deleted "); return NULL; } NSObject*ob = [self.data objectAtIndex:self.front]; self.front = (self.front+1)%self.maxSize; return ob; } -(NSObject*)getFront{ return [self.data objectAtIndex:self.front]; } -(int)getTotalCount{ return (self.rear-self.front + self.maxSize)%self.maxSize; } -(void)showQueue{printf(" print all elements \n"); If ([self isEmpty]) {printf(" queue isEmpty \n"); return; } int count = [self getTotalCount]; for (int i = self.front; i<self.front + count; I++) {NSLog (@ the first element: % d % @ "\ t", I % self. The maxSize, the self. The data [I % self. The maxSize]); } } @endCopy the code
CircleQueue*queue = [[CircleQueue alloc]initWithMaxSize:5]; CircleQueue*queue = [[CircleQueue alloc]initWithMaxSize:5]; // Add data [queue enqueue:@"a"]; [queue enqueue:@"b"]; [queue enqueue:@"c"]; [queue enqueue:@"d"]; [queue enqueue:@"z"]; Printf (" %d elements \n",[queue getTotalCount]); // Print all elements [queue showQueue]; NSObject*front = [queue getFront]; Printf (" header element is: % s \ n ", the front. The description. UTF8String); NSObject* STR = [queue dequeue]; Printf (" delete elements is: % s \ n ", STR) description. UTF8String); // Print all elements [queue showQueue]; // Delete data [queue dequeue]; [queue dequeue]; Printf (" %d elements \n",[queue getTotalCount]); [queue enqueue:@"e"]; [queue enqueue:@"f"]; [queue enqueue:@"g"]; [queue enqueue:@"h"]; // Print all elements [queue showQueue]; // Delete data [queue dequeue]; [queue dequeue]; // Print all elements [queue showQueue]; }Copy the code

2) Dynamic Queue of Queues (Single Linked list implementation)

Pay attention to my

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