欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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);                                                             
}