c/c++线性循环队列
程序员文章站
2022-03-21 21:28:25
线性循环队列 队列是先进先出,和栈相反. 线性循环队列,牺牲一个空间,实现循环。比如空间大小为4,牺牲一个空间,所以最多放3个元素。 假设front指向0位置,tail指向3位置 | 1 | 2 | 3 | 空 | | | | | | 出队后 front指向1位置,tail位置不变还是3 | 空 | ......
线性循环队列
队列是先进先出,和栈相反.
线性循环队列,牺牲一个空间,实现循环。比如空间大小为4,牺牲一个空间,所以最多放3个元素。
假设front指向0位置,tail指向3位置
1 | 2 | 3 | 空 |
---|
出队后
front指向1位置,tail位置不变还是3
空 | 2 | 3 | 空 |
---|
入队后(4)
front指向不变还是1,tail指向0位置
空 | 2 | 3 | 4 |
---|
出队后
front指向2位置,tail位置不变还是0
空 | 空 | 3 | 4 |
---|
入队后(5)
front指向不变还是2,tail指向1位置
5 | 空 | 3 | 4 |
---|
whilequeue.h
#ifndef __WHILEQUEUE__ #define __WHILEQUEUE__ #include <stdio.h> #include <malloc.h> #include <assert.h> #include <memory.h> #include <stdbool.h> #define WHILEQUEUE_INIT_SIZE 8 typedef int ElemType; typedef struct whilequeue{ ElemType* base; int front; int tail; }whilequeue; void init(whilequeue*); //入队 void enQueue(whilequeue*, ElemType); void show_list(whilequeue*); //出队 void deQueue(whilequeue*); void clear(whilequeue*); void destroy(whilequeue*); #endif
whilequeue.c
#include "whilequeue.h" void init(whilequeue* seq){ seq->base = (ElemType*)malloc(sizeof(ElemType) * WHILEQUEUE_INIT_SIZE); seq->front = seq->tail = 0; } void enQueue(whilequeue* seq, ElemType x){ //判断队列是否已满 if((seq->tail + 1) % WHILEQUEUE_INIT_SIZE == seq->front){ printf("queue is full\n"); return; } seq->base[seq->tail] = x; seq->tail = (seq->tail + 1) % WHILEQUEUE_INIT_SIZE; } void show_list(whilequeue* seq){ int i = seq->front; while(i != seq->tail){ printf("%d\n", seq->base[i++ % WHILEQUEUE_INIT_SIZE]); i = i % WHILEQUEUE_INIT_SIZE; } } void deQueue(whilequeue* seq){ //判断队列是否为空,空了的话,就不需要移动front if(seq->front == seq->tail)return; seq->front = (seq->front + 1) % WHILEQUEUE_INIT_SIZE; } void clear(whilequeue* seq){ } void destroy(whilequeue* seq){ }
whilequeuemain.c
#include "whilequeue.h" int main(){ whilequeue list; init(&list); int select = 1; ElemType item; int index; while(select){ printf("*****************************************\n"); printf("*** [1] push [2] pop ***\n"); printf("*** [3] show_list [4] length ***\n"); printf("*** [5] clear [6] destroy ***\n"); printf("*** [0] quit ***\n"); printf("*****************************************\n"); printf("请选择:>"); scanf("%d", &select); if(0 == select) break; switch(select){ case 1: printf("请输入要插入的数据>\n"); scanf("%d",&item); enQueue(&list, item); show_list(&list); break; case 2: deQueue(&list); show_list(&list); break; case 3: show_list(&list); break; case 5: clear(&list); show_list(&list); break; case 6: destroy(&list); break; default: printf("输入的选择错误,请重新选择\n"); break; } } //destroy(&list); }