数据结构|顺序队列的实现（实验3.3）

野性酷女 2022-06-07 10:27 157阅读 0赞

# 一、实验目的 #

1、   熟练掌队列的结构特点，掌握队列的顺序存储和实现。

2、      学会使用队列解决实际问题。

二、实验内容

1、自己确定结点的具体数据类型和问题规模，建立一个顺序队列，实现队列的入队和出队操作。

三、实验步骤

1、依据实验内容分别说明实验程序中用到的数据类型的定义；

template<typename T>
    class Cirqueue{
    	public:
    		Cirqueue(){ front = rear = Queuesize-1; }  //构造函数，初始化空队列
    		void EnQueue(T x);   //入队操作
    		T DeQueue();      //出队操作
    		T GetQueue();     //取头元素
    		void PrintQueue();   //遍历操作
    		int Empty() {front==rear?return 1:return 0;}  //判断是否为空对列
    	private:
    		T data[Queuesize];  //存放队列元素的数组
    		int front,rear;    //队头和队尾指针
    };

2.、相关操作的算法表达；

2.1 构造函数 初始化空队列

2.2入队操作函数：  
 \* 1.判断是否队满，若是则返回，否则   
 \* 2.队尾指针 rear 指向队尾的下一个位置   
 \*   注意：因为是循环结构，所以队尾指针 rear 指向的位置可能在原队尾的后面，也可能在原队尾的前面   
 \* 3.把 value 存储在队尾

2.3出队操作函数：   
 \* 1.判断是否队空，若是则抛出“下溢”，否则   
 \* 2.队头指针 front 指向队头（队头指针，指向队头元素的前一个位置）   
 \* 3.返回队头元素   
 \*   注意：此时队头指针 front 指向原队头元素，即指向新队头元素的前一个位置

2.4取队头元素操作函数：   
 \* 1.判断是否队空，若是则抛出“下溢”，否则  
 \* 2.返回队头元素

2.5输出操作函数：按照顺序，输出栈元素

3、完整程序；

由于结点元素类型不确定，因此采用C++模板机制。

源代码如下：

#include<iostream>
    using namespace std;
    
    const int Queuesize = 100;
    
    template<typename T>
    class Cirqueue{
    	public:
    		Cirqueue(){ front = rear = Queuesize-1; }  //构造函数，初始化空队列
    		void EnQueue(T x);   //入队操作
    		T DeQueue();      //出队操作
    		T GetQueue();     //取头元素
    		void PrintQueue();   //遍历操作
    		int Empty() {front==rear?return 1:return 0;}  //判断是否为空对列
    	private:
    		T data[Queuesize];  //存放队列元素的数组
    		int front,rear;    //队头和队尾指针
    };
    
    template <typename T>
    void Cirqueue<T>::EnQueue(T x)
    {
    	if((rear+1)%Queuesize==front) throw"上溢";
    	rear=(rear+1)%Queuesize;
    	data[rear]=x;
    }
    
    template <typename T>
    T Cirqueue<T>::DeQueue()
    {
    	if(rear==front) throw"下溢";
    	front=(front+1)%Queuesize;
    	return data[front];
    }
    
    template <typename T>
    T Cirqueue<T>::GetQueue()
    {
    	int i;
    	if(rear==front) throw"下溢";
    	i=(front+1)%Queuesize;
    	return data[i];
    }
    
    template <typename T>
    void Cirqueue<T>::PrintQueue()
    {
    	int p = (front+1) % Queuesize;  
        while(p != rear){  
            cout<<data[p]<<" ";  
            p = (p+1) % Queuesize;  
        }  
        cout<<data[p]<<endl;
    }
    
    void main()
    {
    	Cirqueue<int>b;
    	cout<<"按顺序使“1，2，3，4，5”进队列"<<endl;
    	for(int i=1;i<=5;i++)
    	{  b.EnQueue(i); cout<<i<<"入队成功！"<<endl<<endl;}
    	cout<<"结果如下："<<endl;
    	b.PrintQueue();
    	cout<<"出队一个元素"<<b.DeQueue()<<"结果如下："<<endl;
    	b.PrintQueue();
    	cout<<"现在对头元素为："<<b.GetQueue()<<endl;
    }

4、总结、运行结果和分析。

①总结

在程序内定义对象为int型，将元素1~5按顺序入队。

通过调用成员函数，实现入队、出队、输出等基本功能。

②运行结果如下:  
![Center][]

5、总体收获和不足，疑问等。

上次学习了循环队列后过了一段时间我才动手做实验，总体的实验有点吃力，但通过查阅相关书籍，网上浏览，我才发现其实不难。虽然花费时间较多，但收获颇丰。总的来说，我对理论知识有了更充分的理解，也能较大程度明白运行原理。

俗话说“实践是检验真理的唯一标准”。在课堂上短短的学习时间，并不能很好地对所学知识有很好的理解，相反，我们更需要在课后多花时间上机实验，才能更大程度地掌握所学知识的原理。

[Center]: /images/20220607/8f12e89587a4443ea39a9b839ec22496.png