为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular
Queue)。
循环队列中,由于入队时尾指针向前追赶头指针;出队时头指针向前追赶尾指针,造成队空和队满时头尾指针均相等。因此,无法通过条件front==rear来判别队列是"空"还是"满"。
解决这个问题的方法至少有两种:
②另一种方式就是数据结构常用的:
队满时:(rear+1)%n==front,n为队列长度(所用数组大小),由于rear,front均为所用空间的指针,循环只是逻辑上的循环,所以需要求余运算。如图情况,队已满,但是rear(5)+1=6!=front(0),对空间长度求余,作用就在此6%6=0=front(0)。
队满时:(rear+1)%n==front,n为队列长度(所用数组大小),由于rear,front均为所用空间的指针,循环只是逻辑上的循环,所以需要求余运算。如图情况,队已满,但是rear(5)+1=6!=front(0),对空间长度求余,作用就在此6%6=0=front(0)。
#pragma once #define MAX_LENGTH 10 class Cirqueue { public: Cirqueue(void); ~Cirqueue(void); private: int m_elementerlist[MAX_LENGTH]; int m_head; int m_tail; public: bool push(int value); bool pop(); bool gettop(int *value); bool isempty(); int getsize(); void output(); }; #include "Cirqueue.h" #include "stdio.h" //循环队列初始化 Cirqueue::Cirqueue(void) { m_head = 0; m_tail = 0; for(int i=0; i<MAX_LENGTH; i++) { m_elementerlist[i] = 0xFFFFFFFF; } } Cirqueue::~Cirqueue(void) { } //循环队列入队 bool Cirqueue::push(int value) { bool result = true; //循环队列已经满的标志,尾指针 + 1 等于 头指针 if (((m_tail + 1) % MAX_LENGTH) == m_head) { result = false; } else { m_elementerlist[m_tail] = value; m_tail = (m_tail + 1) % MAX_LENGTH; } return result; } bool Cirqueue::pop() { bool result = true; //循环队列为空的标示,首尾指针相等 if (m_tail == m_head) { result = false; } else { m_elementerlist[m_head] = 0xFFFFFFFF; m_head = (m_head + 1) % MAX_LENGTH; } return result; } //不出队列,仅仅得到队列头部的元素 bool Cirqueue::gettop(int *value) { bool result = true; //队列为空,返回false if (m_tail == m_head) { result = false; } else { *value = m_elementerlist[m_head]; } return result; } //判断队列是否为空 bool Cirqueue::isempty() { bool result = false; if (m_tail == m_head) { result = true; } return result; } //输出队列中的元素 void Cirqueue::output() { if (m_head <= m_tail) { for(int i = m_head; i < m_tail; i++) { printf("%d ", m_elementerlist[i]); } } else { for(int i = m_head; i < MAX_LENGTH; i++) { printf("%d ", m_elementerlist[i]); } for(int i = 0; i < m_tail; i++) { printf("%d ", m_elementerlist[i]); } } printf("\n"); } //得到队列大小 int Cirqueue::getsize() { return (m_tail - m_head + MAX_LENGTH) % MAX_LENGTH; }
主函数测试:
// CircularQueue.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "Cirqueue.h" int _tmain(int argc, _TCHAR* argv[]) { Cirqueue queue; printf("push 9 elements into queue\n"); for(int i=0; i<9; i++) { queue.push(i); } queue.output(); int count = queue.getsize(); printf("size=%d\n", count); printf("pop 3 elements into queue\n"); for(int i=0; i<3; i++) { int value = 0; queue.gettop(&value); queue.pop(); } queue.output(); count = queue.getsize(); printf("size=%d\n", count); printf("push 7 elements into queue\n"); for(int i=0; i<7; i++) { queue.push(i); } queue.output(); count = queue.getsize(); printf("size=%d\n", count); getchar(); return 0; }