数据结构学习之循环队列（顺序存储）

【摘要】队列特性：先进先出（FIFO)——先进队列的元素先出队列。来源于我们生活中的队列（先排队的先办完事）。

这样有个缺陷，空间利用率不高，所以我们直接学习循环队列（基于连续内存的）。

（1）设计队列数据结构

typedef struct _QUEUE_NODE
{
int* pData;
int length;//队列长度
int head ;//队头指针
int tail;//队尾指针
int count;//队列元素当前个数
}QUEUE_NODE;

（2）申请队列内存

QUEUE_NODE* alloca_queue(int number)
{
    QUEUE_NODE* pQueueNode;
if( 0 == number)
return NULL;

    pQueueNode = (QUEUE_NODE*)malloc(sizeof(QUEUE_NODE));
    assert(NULL != pQueueNode);
    memset(pQueueNode, 0, sizeof(QUEUE_NODE));

    pQueueNode->pData = (int*)malloc(sizeof(int) * number);
if(NULL == pQueueNode->pData){
        free(pQueueNode);
        pQueueNode = NULL;
return NULL;
    }

    pQueueNode->length = number;//队列长度
return pQueueNode;
}

(3）释放队列内存

STATUS delete_queue(const QUEUE_NODE* pQueueNode)
{
if(NULL == pQueueNode) 
return FALSE;

    assert(NULL != pQueueNode->pData);

    free(pQueueNode->pData);
    free((void*)pQueueNode);
return TRUE;
}

(4) 把数据压入队列

STATUS insert_queue(QUEUE_NODE* pQueueNode, int value)
{
if(NULL == pQueueNode)
return FALSE;

if(pQueueNode->length == pQueueNode->count)//判断是不是溢出
return FALSE;

    pQueueNode->pData[pQueueNode->tail] = value;
    pQueueNode->tail = (pQueueNode->tail + 1) % pQueueNode->length;  //队尾指针位置
    pQueueNode->count ++;
return TRUE;
}

(5)把数据弹出队列

STATUS get_queue_data(QUEUE_NODE* pQueueNode, int* value)
{
if(NULL == pQueueNode || NULL == value)
return FALSE;

if(0 == pQueueNode->count)
return FALSE;

    *value = pQueueNode->pData[pQueueNode->head];
    pQueueNode-> pData[pQueueNode->head] = 0; //被弹出的位置赋值为0
    pQueueNode-> count --;
    pQueueNode->head = (pQueueNode->head + 1) % pQueueNode->length;//重新定位队头指针的位置
return TRUE;
}

(6)统计当前队列中有多少数据

int  get_total_number(const QUEUE_NODE* pQueueNode)
{
if(NULL == pQueueNode)
return 0;

return pQueueNode->count;
}

(7)查看队列中初始化的时候总长度是多少

int  get_total_number(const QUEUE_NODE* pQueueNode)
{
if(NULL == pQueueNode)
return 0;

return pQueueNode->length;
}

// 循环队列.cpp : 定义控制台应用程序的入口点。
//
//循环队列
//Written by ZP1015
//2015.10.21

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

struct QUEUE_NODE
{
int* pData;
int QueueLenMax;//队列最大长度
int head ;//队头指针
int tail;//队尾指针
int QueueCurLen;//队列元素当前个数
};

struct QUEUE_NODE* alloc_queue(int Queue_Max_Size)
{

if(Queue_Max_Size <= 0)
return NULL;

struct QUEUE_NODE* pQueueNode  = NULL;

    pQueueNode = (QUEUE_NODE*)malloc(sizeof(QUEUE_NODE));
if(NULL == pQueueNode) {
return NULL;
    }
    memset(pQueueNode, 0, sizeof(struct QUEUE_NODE));

    pQueueNode->pData = (int*)malloc(sizeof(int) * Queue_Max_Size);
if(NULL == pQueueNode->pData) {
goto malloc_failed;
    }

    pQueueNode->QueueLenMax = Queue_Max_Size;//队列长度
    pQueueNode->head = 0;
    pQueueNode->tail = 0;
    pQueueNode->QueueCurLen = 0;

return pQueueNode;

malloc_failed:
    free(pQueueNode);
return NULL;
}

int free_queue(struct QUEUE_NODE* pQueueNode)
{
if(NULL == pQueueNode) 
return -1;

if(NULL == pQueueNode->pData) {
        free(pQueueNode);
return -1; 
    }

    free(pQueueNode->pData);
    free(pQueueNode);

return 0;
}

int queue_push(struct QUEUE_NODE* pQueueNode, int value)
{
if(NULL == pQueueNode)
return -1;

if(pQueueNode->QueueLenMax == pQueueNode->QueueCurLen)//判断是不是溢出
return -1;

    pQueueNode->pData[pQueueNode->tail] = value;
    pQueueNode->tail = (pQueueNode->tail + 1) % pQueueNode->QueueLenMax;  //队尾指针位置
    pQueueNode->QueueCurLen ++;

return 0;
}

int queue_pop(struct QUEUE_NODE* pQueueNode, int* value)
{
if(NULL == pQueueNode || NULL == value)
return -1;

if(0 == pQueueNode->QueueCurLen)
return -1;

    *value = pQueueNode->pData[pQueueNode->head];
    pQueueNode->pData[pQueueNode->head] = 0; //被弹出的位置赋值为0

    pQueueNode->QueueCurLen --;
    pQueueNode->head = (pQueueNode->head + 1) % pQueueNode->QueueLenMax;//重新定位队头指针的位置

return 0;
}

int get_queue_curlen(struct QUEUE_NODE* pQueueNode)
{
if(NULL == pQueueNode)
return -1;

return pQueueNode->QueueCurLen;
}

int get_queue_maxlen(struct QUEUE_NODE* pQueueNode)
{
if(NULL == pQueueNode)
return 0;

return pQueueNode->QueueLenMax;
}

void print_queue_node(struct QUEUE_NODE *pQueueNode) 
{
/*1.输入的参数有误*/
if(NULL == pQueueNode) {
        printf("[%d] pQueueNode is illegal! \n",__LINE__);
return;
    }
/*2.输入的链式堆栈为空*/
if(0 == pQueueNode->QueueCurLen) {
        printf("[%d] pQueueNode is empty!\n",__LINE__);
return ;
    }

struct QUEUE_NODE *pQueueNodeTemp = pQueueNode;
int count = 0;

while(count < pQueueNode->QueueCurLen) {
        printf("%d ",pQueueNode->pData[pQueueNode->head+count]);
        count++;;
    }
    printf("\n");
}


int main()
{
struct QUEUE_NODE *pQueueNode;
    pQueueNode = alloc_queue(20);
int i = 0;
for (i = 0;i<10;i++) {
        queue_push(pQueueNode,i);
    }
    print_queue_node(pQueueNode);
int a = 0;
    queue_pop(pQueueNode,&a);
    print_queue_node(pQueueNode);

    free_queue(pQueueNode);

    getchar();
    getchar();

return 0;
}

OJ 系列循环队列的基本操作

/******************************************************************************

 Copyright (C), 2001-2011, SCUT.

 ******************************************************************************
 File Name : 
 Version : 
 Author : 
 Created : 2016/01/21
 Last Modified :
 Description : 
 Function List :

 History :
 1.Date : 2016/01/21
 Author : 
 Modification: Created file

******************************************************************************/
#include <stdlib.h>

#define MAXSIZE 50

struct strqueue {
int queue[MAXSIZE];
int head; /* 队头 */
int tail; /* 队尾 */
int num;  /* 队元素个数 */
};

/* 初始化队列，返回0表示失败，返回1表示成功 */
bool initqueue(struct strqueue *s) 
{
if(!s)
return 0;
for(int i = 0;i<MAXSIZE;i++) {
        s->queue[i] = 0;
    }
    s->head = -1;
    s->tail = -1;
    s->num = 0;

return 1;
}

bool enqueue(struct strqueue *s, int x) /* 进队列，返回0表示失败，返回1表示成功 */
{
if(!s)
return 0;
if(s->num == MAXSIZE )
return 0;

if(s->head==-1||s->tail==-1) {
        s->head = 0;
        s->tail = 0;
        s->queue[s->tail] = x; /*赋值*/
        s->num  = 1;
return 1;
    } 

    s->tail  =  (s->tail + 1) % MAXSIZE;/*从队尾入队列*/
    s->queue[s->tail] = x; /*赋值*/

    s->num ++;

return 1;
}

bool dequeue(struct strqueue *s, int *x) /* 出队列，返回0表示失败，返回1表示成功 */
{
if(!s||!x)
return 0;
if(s->num == 0)
return 0;

    *x = s->queue[s->head]; /*赋值*/
    s->queue[s->head] = 0;

    s->head  =  (s->head + 1) % MAXSIZE;/*从对头出队列*/
    s->num --;

if(s->num==0) {
        s->head = -1;
        s->tail = -1;
    }

return 1;

}

int gethead(struct strqueue *s)  /* 获得队列头数值 */
{   
if(!s)
return -1;

if(s->num==0)
return -1;

int head = 0;
    head = s->queue[s->head];

return head;
}


int gettail(struct strqueue *s)  /* 获得队列尾数值 */
{
if(!s)
return 0;

int tail = 0;

if(s->num==0)
return -1;

    tail=s->queue[s->tail];

return tail;
}

int getqueuelenth(struct strqueue *s)  /* 获得队列长度 */
{
if(!s)
return 0;

int lenth = 0;
    lenth = s->num;

return lenth;
}

bool search(struct strqueue *s, int x)  /* 在队列中查找x是否存在，如果存在返回1，否则返回0 */
{
if(!s)
return 0;

int headTemp = s->head;
int tailTemp = s->tail;
/*1.队列为满的情况*/
if(s->num == MAXSIZE) {
for(int i=0;i<MAXSIZE;i++) {
if(x==s->queue[i])
return 1;
        }
    } else {
/*2.队列不满,从head到tail处是存在元素的*/
while(headTemp!=tailTemp) {
if(x==s->queue[headTemp])
return 1;
            headTemp=(headTemp + 1) % MAXSIZE;
        }
    }


return 0;
}