Several simple queue C language implementation

Recently, I have written a lot of stack problems, and I think a lot about stack, so I may need more time to digest and sort them out. Today, I will simply summarize the queue.

The queue here refers to a simple queue implementation, about the use of the queue (use mostly priority queue) table, wait to learn the following priority queue (heap) ** after the expansion.

Linked list or array?

This problem is similar to the previous stack. We can implement it with linked lists, and their common operations (push,pop) will all have the same O(1) time complexity. The only disadvantage of implementing as an array is that the stack size often needs to be estimated in advance. If it can’t be accurately estimated, we will build a large stack space, but often there won’t be many elements in the stack. For most problems, the space complexity is only N, or n/2, so we usually use arrays.

In general, dequeueing and enqueueing tend to be balanced, and the size of the queue tends to be small, and the size of the queue usually does not want to be large. So if you have a list, what you need is the initial two list nodes are front,rear, and the implementation of the list is straightforward.

The teamWhen they arerear->nextPoint to the new node
Out of the teamletfront = front->next
judgeTeam is emptyThe inspectionfront->nextWhether it isnull
Full teams are generally not considered

Using arrays as containers to implement queues, especially the usual circular queue (which makes full use of queue space), is a bit more complicated than a linked list.

Complex points:

There are a lot of ways to tell if a line is empty
There are many ways to judge a full line
Front/rear mobile
The issue of cross-border access

Take a look at my array implementation for the loop queue:

622. Design Circular Queue

typedef struct {
    int* array;
    int front;
    int rear;
    int cnt;
    int size;
} MyQueue;

MyQueue* myQueueCreate(int maxSize){
	MyQueue* mq = (MyQueue*)malloc(sizeof(MyQueue));
	mq->array = (int*)malloc((maxSize + 1) * sizeof(int));
	mq->front = 0;
	mq->rear = 1;
	mq->cnt = 0;
	mq->size = maxSize + 1;
	return mq;
}

int isFull(MyQueue* mq){
	return mq->cnt == mq->size - 1;
}

int isEmpty(MyQueue* mq){
	return mq->cnt == 0;
}

int enqueue(MyQueue* mq, int val){
	if(isFull(mq))
		return 0;
	mq->array[mq->rear] = val;
	mq->rear = (mq->rear + 1) % mq->size;
	mq->cnt++;
	return 1;
}

int dequeue(MyQueue* mq){
	if(isEmpty(mq))
		return 0;
	mq->front = (mq->front + 1) % mq->size;
	mq->cnt--;
	return 1;
}

int getFront(MyQueue* mq){
	if(isEmpty(mq))
		return - 1;
	int index = (mq->front + 1) % mq->size;
	return mq->array[index];
}

int getRear(MyQueue* mq){
	if(isEmpty(mq))
		return - 1;
	int index = (mq->rear - 1 + mq->size) % mq->size;
	return mq->array[index];
}

void printQueue(MyQueue* mq){
	int len = (mq->rear - mq->front - 1 + mq->size) % mq->size;
	int start = (mq->front + 1) % mq->size;
	
	printf("\n----detail----\n");
	for (int i = 0; i < len; ++i)
	{
		int index = (start + i) % mq->size;
		printf("%d-", mq->array[index]);
	}
	printf("end\nfront:%d\n", getFront(mq));
	printf("rear:%d\n", getRear(mq));
	printf("cnt:%d\n", mq->cnt);
	printf("size:%d\n", mq->size- 1);
	printf("isEmpty:%d\n", isEmpty(mq));
	printf("isFull:%d\n", isFull(mq));
	printf("--------------\n");
}

void freeMyQueue(MyQueue* mq){
	free(mq->array);
	free(mq);
}
Copy the code

It is worth noting:

The addition of the CNT field makes the empty/full test simple, straightforward and efficient, and you can see later that the condition is much more difficult to understand after removing this field.
Whenever we encounter Rear-1 /front-1, we add a size to it, which is an effective way to prevent access to negative labels from crossing boundaries
The loop 2 font for the loop queue now has the % symbol
The initial distance between front and rear is 1, so the ratio of memory allocation is k + 1
Array [front+1] and array[rear-1]
Check team full and team empty respectively, cnt++
On joining, assign to the current rear, which moves to the right one position (consider loops)
When you exit the queue, you don’t need to change the value of front, just move it one position to the right (consider loops)
Without CNT, the conditions for judging empty and full teams are as follows

int isFull(MyQueue* mq){
	return ((mq->rear + 1)) % mq->size == mq->front;
}	

int isEmpty(MyQueue* mq){
	return ((mq->front + 1) % mq->size) == mq->rear;
}

Copy the code

Leetcode has a problem that uses a stack to implement a queue, which is quite interesting and straightforward. When exiting a stack, another stack is used to help adjust the order.

232. Implement Queue using Stacks

typedef struct {
	//stack s2 is for auxiliary
    int* s1;
    int t1;
    int* s2;
    int t2;
    int front;
} MyQueue;

/** Initialize your data structure here. */
MyQueue* myQueueCreate(int maxSize) {
	MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));
	queue->s1 = (int*)malloc(maxSize * sizeof(int));
	queue->s2 = (int*)malloc(maxSize * sizeof(int));
	queue->t1 = - 1;
	queue->t2 = - 1;
    return queue;
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
	//abvious O(1)
	//s1 is empty
    if(obj->t1 == - 1)   	
    	obj->front = x;

	obj->s1[++(obj->t1)] = x;
}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
	//at the worst case,transport all element from s1 to s2
	//amortized, the time complexity is O(1)
    if(obj->t2 == - 1)
    	while(obj->t1 ! =- 1)
    		obj->s2[++(obj->t2)] = obj->s1[(obj->t1)--];

	return obj->s2[(obj->t2)--];

}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
    if(obj->t2 == - 1)
    	return obj->front;
    return obj->s2[obj->t2];
}

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
    return (obj->t1 == - 1 && obj->t2 == - 1)?1 : 0;
}

void myQueueFree(MyQueue* obj) {
    free(obj->s1);
    free(obj->s2);
    free(obj);
}
Copy the code

Amortized O(1), if s2 has an element on top of the stack, then it’s out of the stack, O(1), and if s2 has no element on top of the stack, then you push all the elements in S1 into S2 at once, and after an O(n), The next n exits will only pop s2 at the top of the stack, so after amortization, each exit is still O(n).

CircularDeque is also a common two-ended circular queue, which differs from the ordinary circular queue in that it can insert elements at the head and tail of the queue.

641. Design Circular Deque

typedef struct {
    int* array;
    int front;
    int rear;
    int size;
} MyCircularDeque;

/** Checks whether the circular deque is empty or not. */
int myCircularDequeIsEmpty(MyCircularDeque* obj) {
    return ((obj->front + 1) % obj->size == obj->rear) ? 1 : 0 ;
}

/** Checks whether the circular deque is full or not. */
int myCircularDequeIsFull(MyCircularDeque* obj) {
    return obj->front == obj->rear ? 1 : 0;
}

/** Initialize your data structure here. Set the size of the deque to be k. */
MyCircularDeque* myCircularDequeCreate(int k) {
    MyCircularDeque* mq = (MyCircularDeque*)malloc(sizeof(MyCircularDeque));
    //if k = 1, malloc k * sizeof int, the queue is full already
    mq->array = (int*)malloc((k + 1) * sizeof(int));
    mq->front = k;
    mq->rear = 0;
    mq->size = k + 1;
    return mq;
}

/** Adds an item at the front of Deque. Return true if the operation is successful. */
int myCircularDequeInsertFront(MyCircularDeque* obj, int value) {
    if(myCircularDequeIsFull(obj))
    	return 0;

    obj->array[obj->front] = value;
    obj->front = (obj->front - 1 + obj->size) % obj->size;   
    return 1;
}

/** Adds an item at the rear of Deque. Return true if the operation is successful. */
int myCircularDequeInsertLast(MyCircularDeque* obj, int value) {
    if(myCircularDequeIsFull(obj))
    	return 0;
    obj->array[obj->rear] = value;
    obj->rear = (obj->rear + 1) % obj->size;  
    return 1;
}

/** Deletes an item from the front of Deque. Return true if the operation is successful. */
int myCircularDequeDeleteFront(MyCircularDeque* obj) {
    if(myCircularDequeIsEmpty(obj))
    	return 0;
    obj->front = (obj->front + 1) % obj->size;
    return 1;
}

/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
int myCircularDequeDeleteLast(MyCircularDeque* obj) {
    if(myCircularDequeIsEmpty(obj))
    	return 0;
    obj->rear = (obj->rear - 1 + obj->size) % obj->size;
    return 1;
}

/** Get the front item from the deque. */
int myCircularDequeGetFront(MyCircularDeque* obj) {
	int index = (obj->front + 1) % obj->size;
    return myCircularDequeIsEmpty(obj) ? - 1 : obj->array[index];
}

/** Get the last item from the deque. */
int myCircularDequeGetRear(MyCircularDeque* obj) {
	int index = (obj->rear - 1 + obj->size) % obj->size;
    return myCircularDequeIsEmpty(obj) ? - 1 : obj->array[index];
}

void myCircularDequeFree(MyCircularDeque* obj) {
    free(obj->array);
    free(obj);
}
Copy the code

Several simple queue C language implementation

622. Design Circular Queue

232. Implement Queue using Stacks

641. Design Circular Deque

Related Posts

How to build the traffic condition of online application architecture | opening project

Case study: How can Young GC occur frequently in a BI system with 100,000 concurrent requests per second?

Leetcode 2160. Minimum Sum of Four Digit Number After Splitting Digits (Python)