队列的实现

队列的实现

队列，顾名思义，是指把数据像排队一样进行管理。先进先出，即只能从队尾加入数据，从队头删除数据。

队列的实现依靠以下结构体：

代码语言：javascript复制

struct queue {
	int front;
	int tail;
	int* elements;
};

实现关于队列各个操作：

代码语言：javascript复制

#include 
#include 

#define MAX_SIZE 100

// 初始化一个队列
void initialize(struct queue* q) {
	q->front = 0; //指向第一个元素的位置
	q->tail = 0; //tail指向最后一个元素的下一个位置，若跟front相同则表示队列空
	q->elements = (int *)malloc(sizeof(int)*(MAX_SIZE 1));//多分配一个位置，在首元素之前的那个必定是空
}

// 弹出队首元素，并返回该元素，如果队列为空，返回-1
int pop(struct queue* q) {
	if (q->tail == q->front) return -1;
	int temp = q->elements[q->front];
	q->front  ;
	if (q->front == MAX_SIZE   1) q->front = 0;
	return temp;
}

// 向队列中增加元素，并返回该元素，如果队列已满，返回-1
int push(struct queue* q, int number) {
	if ((q->tail 1)%(MAX_SIZE 1) == q->front%(MAX_SIZE 1)) return -1;//如果最后一个元素后面已经是首元素前一位，就满了
	q->elements[q->tail]  = number;
	q->tail  ;
	if (q->tail == MAX_SIZE 1) q->tail = 0;
	return number;
}

// 返回队列长度
int get_size(struct queue* q) {
    if(q->tail == q->front) return 0;
    if(q->tail > q->front) return q->tail - q->front;
	return q->tail   (MAX_SIZE   1 - q->front);
}

// 返回队首元素，若队列为空，返回-1
int get_front(struct queue* q) {
	if (q->tail == q->front) return -1;
	int temp = q->elements[q->front];
	return temp;
}

// 判断队列是否为空，若是，返回1，否则，返回0
int empty(struct queue* q) {
	if (q->tail == q->front) return 1;
	return 0;
}

// 输出队列，若队列为空，输出“Empty queue”
void list(struct queue* q) {
	if (empty(q)) {
		printf("Empty queuen");
	}
	else {
		int i=q->front;
        while(i!=q->tail%(MAX_SIZE 1)){
            if((i 1)%(MAX_SIZE 1)==(q->tail))printf("%dn",q->elements[i]);
            else printf("%d ",q->elements[i]);
            i=(i 1)%(MAX_SIZE 1);
        }
	}
}

int main(){
	int n = 0, op = 0, op_number = 0;
	scanf("%d", &n);
	struct queue q;
	initialize(&q);
	while(n--){
		scanf("%d", &op);
		switch(op){
			case 1:{
				int res = pop(&q);
				if(res == -1){
					printf("Pop failed!n");
				}
				else{
					printf("Pop %d successfully!n", res);
				}
				break;
			}
				
			case 2:{
				scanf("%d", &op_number);
				int res = push(&q, op_number);
				if(res == -1){
					printf("Push failed!n");
				}
				else{
					printf("Push %d successfully!n", res);
				}
				break;
			}
				
			case 3:{
				printf("Size of queue is %dn", get_size(&q));
				break;
			}
				
			case 4:{
				int res = get_front(&q);
				if(res == -1){
					printf("Queue is empty!n");
				}
				else{
					printf("Front element of queue is %dn", res);
				}
				break;
			}
				
			case 5:{
				int res = empty(&q);
				if(res){
					printf("Queue is empty!n");
				}
				else{
					printf("Queue is not empty!n");
				}
				break;
			}	
			default:
				printf("Curr queue is: ");
				list(&q);
		}
	}
	list(&q);
	free(q.elements);
	return 0;
}

队列 管理 数据

0 人点赞