数据结构之队列

[jyzwf]

队列是一种先入先出的数据结构，基本操作有如下几种：

1. initQueue：初始化队列
2. queueEmpty：队列是否为空
3. pushQueue：入队
4. popQueue：出队
5. clearQueue：清空队列
6. get_top：获取对头元素

主文件：

#include <stdio.h>
#include <stdlib.h>
#define QueueSize 40
typedef char DataType;

//#include "seqQueue.h"
#include "scQueue.h"

int main()
{
       SeqQueue Q;
       DataType str[]="ABCDEFGH";
       DataType e;

       int i=0,length=8;

       initQueue(&Q);

       for(;i<length;i++)
              pushQueue(&Q,str[i]);

       printf("开始出栈操作：\n");
       if(popQueue(&Q,&e)==1)
              printf("出队元素：%4c\n",e);

       printf("剩下顺序队列的元素：");
       if(queueEmpty(Q)==1)
              for(i=Q.front;i<Q.rear;i++)
                     printf("%c ",Q.queue[i]);

       return 0;

}

简单的顺序队列

#ifndef SEQQUEUE_H_INCLUDED
#define SEQQUEUE_H_INCLUDED


// 定义一个队列的结构体
typedef struct Squeue
{
       DataType queue[QueueSize];
       int front,rear;
}SeqQueue;

// 初始化队列
void initQueue(SeqQueue *SQ)
{
       SQ->front=SQ->rear=0;
}

// 判断队列是否为空
int queueEmpty(SeqQueue SQ)
{
       if(SQ.front==SQ.rear)
              return 0;
       return 1;
}


// 入队
int pushQueue(SeqQueue *SQ,DataType *e)
{
       if(SQ->rear==QueueSize-1){
              printf("队列已满，不能插入");
              return 0;
       }

       SQ->queue[SQ->rear++] = e;
       return 1;
}


// 出队
int popQueue(SeqQueue *SQ,DataType *e)
{
       if(SQ->front == SQ->rear){
              printf("队列已空，不能出队");
              return 0;
       }

       *e = SQ->queue[SQ->front++];
       return 1;
}



#endif // SEQQUEUE_H_INCLUDED

循环顺序队列

循环顺序队列节约了存储空间，利用一个标志位 flag 来标识当 队头指针等于对尾指针时是对满还是队空，出队时，flag 为0，此时如果 队头指针等于对尾指针，则表明队空,；入队时，flag 为1，此时如果 队头指针等于对尾指针，则表明队满；

#ifndef SCQUEUE_H_INCLUDED
#define SCQUEUE_H_INCLUDED

// 循环队列的操作

// 定义一个队列的结构体
typedef struct Scqueue
{
       DataType queue[QueueSize];
       int front,rear;
       int flag;     // 用来判断队头队尾指针相等时，是队满还是队空
}ScQueue;


// 初始化
void initQueue(ScQueue *SCQ)
{
       SCQ->front=SCQ->rear=0;
       SCQ->flag = 0;
}

// 判断是否为空
int queueEmpty(ScQueue SCQ)
{
       if(SCQ.front==SCQ.rear &&SCQ.flag==0)
              return 1;
       return 0;
}


// 入队
int pushQueue(ScQueue *SCQ,DataType e)
{
       if(SCQ->front == SCQ->rear && SCQ->flag == 1){
              printf("顺序循环队列已满，不能入队");
              return 0;
       }

       SCQ->queue[SCQ->rear] = e;
       SCQ->rear=(SCQ->rear+1)%QueueSize;
       SCQ->flag = 1;
       return 1;
}

// 出队
int popQueue(Scqueue *SCQ,DataType *e)
{
       if(queueEmpty(*SCQ))
       {
              printf("顺序循环队列已空，不能出队");
              return 0;
       }

       *e = SCQ->queue[SCQ->front];
       SCQ->front = (SCQ->front+1)%QueueSize;
       SCQ->flag = 0;
       return 1;
}

// 获取头元素
int get_top(Scqueue *SCQ,DataType *e)
{
       if(queueEmpty(*SCQ))
       {
              printf("顺序循环队列已空，不能出队");
              return 0;
       }

       *e = SCQ->queue[SCQ->front];

       return 1;
}


// 清空队列
void clearQueue(Scqueue *SCQ)
{
       SCQ->front=SCQ->rear=0;
       SCQ->flag = 0;
}






#endif // SCQUEUE_H_INCLUDED