原创

队列的顺序存储结构-顺序队列

温馨提示:
本文最后更新于 2021年02月24日,已超过 587 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我

队列的定义

队列是一种先进先出的线性表,它只允许在表的一段进行插入,而在另一端进行删除。在队列中允许插入的一端叫做队尾,允许删除的一端叫做对头。

队列的基本操作

(1)队列的初始化
(2)销毁队列
(3)清空队列
(4)判空
(5)取队列长度
(6)取队头元素
(7)入队
(8)出队

定义顺序队列结构

typedef struct {
    int *base;  //基地址用于存储队列元素
    int front;  //头指针 
    int rear;   //尾指针 
}SqQueue;

队列的初始化

/*初始化顺序队列*/
int InitQueue(SqQueue &Q){
    Q.base = (int*)malloc(MAXSIZE*sizeof(int));
    if(!Q.base) return -1;
    Q.front = Q.rear = 0;
    printf("顺序队列初始化成功\n");
    return 0; 
}

销毁队列

/*销毁顺序队列*/
int DestroyQueue(SqQueue &Q){
    if(!Q.base) return -1;
    free(Q.base);
    return 0;
}

清空队列

/*清空顺序队列*/
int ClearQueue(SqQueue &Q){
    if(!Q.base) return -1;
    Q.front = Q.rear;
    printf("队列清空成功\n");
    return 0;
}

判空

/*判断队列为空*/ 
int QueueEmpty(SqQueue Q){
    if(Q.rear == Q.front){
        printf("队列为空\n") ;
        return 0;  //队列为空返回0 
    }else{
        printf("队列不为空\n");
        return 1;   //队列不为空返回1 
    }
}

取队列长度

/*获取队列长度*/
int QueueLength(SqQueue Q) {
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}

取队头元素

/*获取队头元素*/ 
int GetHead(SqQueue Q,int e) {
    if(!Q.base) return -1;
    return Q.base[Q.front];
}

入队

/*顺序队列入队*/
int InQueue(SqQueue &Q,int e) {
    //队满不能入队
    if((Q.rear+1)%MAXSIZE == Q.front) return -1;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear+1)%MAXSIZE;
    printf("元素【%d】入队成功\n",e);
    return 0;
}

出队

/*顺序队列出队*/
int EnQueue(SqQueue &Q,int e) {
    //队空不能出队
    if((Q.rear == Q.front)){
        printf("出队失败\n");
        return -1;    
    }             
    e = Q.base[Q.front];
    Q.front = (Q.front+1)%MAXSIZE;
    printf("元素【%d】出队成功\n",e);
    return 0;
}

完整代码

#include <stdio.h> 
#include <stdlib.h>
#define MAXSIZE 100

typedef struct {
    int *base;  //基地址用于存储队列元素
    int front;  //头指针 
    int rear;   //尾指针 
}SqQueue;

/*初始化顺序队列*/
int InitQueue(SqQueue &Q){
    Q.base = (int*)malloc(MAXSIZE*sizeof(int));
    if(!Q.base) return -1;
    Q.front = Q.rear = 0;
    printf("顺序队列初始化成功\n");
    return 0; 
} 
/*销毁顺序队列*/
int DestroyQueue(SqQueue &Q){
    if(!Q.base) return -1;
    free(Q.base);
    return 0;
} 
/*清空顺序队列*/
int ClearQueue(SqQueue &Q){
    if(!Q.base) return -1;
    Q.front = Q.rear;
    printf("队列清空成功\n");
    return 0;
} 
/*顺序队列入队*/
int InQueue(SqQueue &Q,int e) {
    //队满不能入队
    if((Q.rear+1)%MAXSIZE == Q.front) return -1;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear+1)%MAXSIZE;
    printf("元素【%d】入队成功\n",e);
    return 0;
}
/*顺序队列出队*/
int EnQueue(SqQueue &Q,int e) {
    //队空不能出队
    if((Q.rear == Q.front)){
        printf("出队失败\n");
        return -1;    
    }             
    e = Q.base[Q.front];
    Q.front = (Q.front+1)%MAXSIZE;
    printf("元素【%d】出队成功\n",e);
    return 0;
}
/*获取队头元素*/ 
int GetHead(SqQueue Q,int e) {
    if(!Q.base) return -1;
    return Q.base[Q.front];
}
/*获取队列长度*/
int QueueLength(SqQueue Q) {
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}
/*判断队列为空*/ 
int QueueEmpty(SqQueue Q){
    if(Q.rear == Q.front){
        printf("队列为空\n") ;
        return 0;  //队列为空返回0 
    }else{
        printf("队列不为空\n");
        return 1;   //队列不为空返回1 
    }
} 
int main(){
    SqQueue Q; 
    int e;
    //初始化顺序队列
    InitQueue(Q);
    //判断队列是都为空
    QueueEmpty(Q);
    //顺序队列入队
    InQueue(Q,1); 
    InQueue(Q,2);
    InQueue(Q,3);
    InQueue(Q,4);
    //队列长度
    printf("队列长度为:%d\n",QueueLength(Q)) ;
    printf("======分界线======\n"); 
    //ClearQueue(Q); 
    //顺序队列出队
    EnQueue(Q,e); 
    EnQueue(Q,e);
    EnQueue(Q,e);
    EnQueue(Q,e);
    EnQueue(Q,e);
    //清空队列
    ClearQueue(Q); 
    QueueEmpty(Q);
}

运行结果

file

正文到此结束
本文目录