题解 | 【模板】双端队列

//优化版双端队列
#include <stdio.h>

#define MAXSIZE 262144

typedef struct Queue {
	int data[MAXSIZE];
	int front, back, length;
}Queue;

inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

int push_front(Queue* q, int data) {
    if (q->length >= MAXSIZE) return 0;
    q->front = (q->front - 1) & (MAXSIZE - 1);
    q->data[q->front] = data;
    q->length++;
    return 1;
}

int push_back(Queue* q, int data) {
    if (q->length >= MAXSIZE) return 0;
    q->data[q->back] = data;
    q->back = (q->back + 1) & (MAXSIZE - 1);
    q->length++;
    return 1;
}
int pop_front(Queue* q) {
    int data = q->data[q->front];
    q->front = (q->front + 1) & (MAXSIZE - 1);
    q->length--;
    return data;
}

int pop_back(Queue* q) {
    q->back = (q->back - 1) & (MAXSIZE - 1);
    int data = q->data[q->back];
    q->length--;
    return data;
}
int main() {
	int q = 0;
	q = read();
	int operate = 0;
	int data = 0;
	Queue queue;
	queue.front = 0;
	queue.back = 0;
	queue.length = 0;
	while (q--) {
		operate = read();
		switch (operate) {
		case 1:
			data = read();
			push_front(&queue, data);
			break;
		case 2:
			data = read();
			push_back(&queue, data);
			break;
		case 3:
			if (queue.length > 0) {
				printf("%d\n", pop_front(&queue));
			}
			else {
				printf("no data\n");
			}
			break;
		case 4:
			if (queue.length > 0) {
				printf("%d\n", pop_back(&queue));
			}
			else {
				printf("no data\n");
			}
			break;
		}
	}
	return 0;
}