群体数据——数组、链表、栈、队列

心已赠人 2023-03-01 09:18 15阅读 0赞

### 目录 ###

*   *  线性群体的概念
     *  数组类模板
     *   *  动态数组类模板程序
     *  链表的概念与结点类模板
     *   *  顺序访问的线性群体——链表类
         *  单链表的节点类模板
         *   *  在当前结点之后插入一个节点
             *  删除当前结点之后的结点
         *  链表的基本操作
     *  栈类
     *   *  栈的基本状态
         *   *  栈空
             *  栈满
             *  一般状态
             *  栈的基本操作
             *  栈类模板
             *  栈的应用
     *  队列
     *   *  队列的基本状态
         *   *  队空
             *  队满
             *  一般状态
         *  循环队列

## 线性群体的概念 ##

*  群体是由多个数据元素组成的集合体。群体可以分为两大类：**线性群体**和**非线性群体**
 *  线性群体中的元素按位置排列有序，可以区分为第一元素、第二元素等。
 *  非线性群体不用位置顺序来标识元素。
 *  线性群体中的元素次序与其逻辑位置关系是对应的。在线性群体中，又可以按照访问元素的不同方法分为直接访问、顺序访问和索引访问。
 *  本章中，我们只介绍直接访问和顺序访问。

## 数组类模板 ##

*  静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。
    
     *  缺点：大小在编译时就已经确定，运行时无法修改。
 *  动态数组由一系列位置连续的、任意数量相同类型的元素组成。
    
     *  优点：其元素个数可以在程序运行时改变。
 *  `vector`就是用类模板实现的动态数组。

### 动态数组类模板程序 ###

#ifndef ARRAY_H
    #define ARRAY_H
    #include <cassert>
    
    template <class T> // 数组类模板定义
    class Array { 
    private:
    	T* list; // 用于存放动态分配的数组内存首地址
    	unsigned size; // 数组大小(元素个数)
    public:
    	Array(unsigned sz = 50); // 默认构造函数
    	Array(const Array<T> &a); // 拷贝构造函数
    	~Array();
    	Array<T> & operator = (const Array<T> &rhs); //拷贝赋值copy assignment,重载"="
    	T & operator [] (int i); // 重载 "[]"
    	const T & operator [] (unsigned i) const; // 重载"[]"为常函数
    	operator T* (); // 重载指针转换符T*
    	operator const T* () const; // 带有cosnt重载之后，指针指向的内容不可以改变；
    	unsigned getSize() const;
    	void resize(int sz); // 修改数组的大小
    };
    
    template <class T> 
    Array<T>::Array(int sz){  // 构造函数
    	assert(sz >= 0);
    	size = sz;
    	list = new T[size]; // 动态分配size个T类型的元素空间
    }
    
    template <class T> 
    Array<T>::~Array(){  // 析构函数
    	delete [] list;
    }
    
    template<class T>
    Array<T>::Array(const Array<T> &a){  // 拷贝构造函数
    	size = a.size; // 从对象a中获取数组的大小
    	list = new T[size]; // 动态分配n个T类型的元素空间
    	for(int i = 0; i < size; i++)
    		list[i] = a.list[i]; 
    
    }
    
    template <class T>
    Array<T>& Array<T>::operator = (const Array<T>& rhs){ 
    	if(&rhs != this){ 
    		if(size = rhs.size){ 
    			delete [] list;
    			size = rhs.size;
    			list = new T[size];
    		}
    		
    		for(int = 0; i < size; i++)
    			list[i] = rhs.list[i];
    	}
    	return *this; // 返回当前对象的引用
    }
    
    template <class T>
    T& Array<T>::operator[](int n){  // 重载下标运算符
    	assert(n >= 0 && n < size);
    	return list[n];
    }
    
    template <class T>
    const T& Array<T>::operator[] (int n) const{ 
    	assert(n >= 0 && n < size);
    	return list[n];
    }
    
    template <class T>
    int Array<T>::getSize() const{ 
    	return size;
    }
    
    template<class T>
    void Array<T>::resize(int sz){ 
    	assert(sz >= 0);
    	if(sz == size)
    		return;
    	T* newList = new T[sz];
    	int n = (sz < size)? sz : size;
    	for(int i = 0; i < n; i++)
    		newList[i] = list[i];
    	list = newList;
    	size = sz;
    }
    
    #endif // ARRAY_H

**指针转换运算符的作用简单举例**

#include <iostream>
    using namespace std;
    
    void read(int *p, int n){ 
    	for(int i = 0; i < n; i++)
    		cin >> p[i];
    }
    
    int main(){ 
    	int a[10];
    	read(a,10);
    	return 0;
    }
    
    #include "Array.h"
    #include <iostream>
    using namespace std;
    
    void read(int* p,int n){ 
    	for(int i = 0; i < n; i++)
    		cin >> p[i];
    }
    
    int main(){ 
    	Array<int> a(10);
    	// 重载指针转换符发挥了作用，否则一个对象不会转换成指针
    	read(a, 10);
    	return 0;
    }

**数组类应用举例**

*  求范围2~N中的质数，N在程序运行时由键盘输入。

#include <iostream>
    #include <iomanip>
    #include "Array.h"
    using namespace std;
    int main() { 
    	Array<int> a(10);
    	int n,count = 0;
    	cout << "Enter a value >= 2 as upper limit for prime numbers: ";
    	cin >> n;
    	
    	for(int i = 2; i <= n; i++){ 
    		bool isPrime = true;
    		for(int j = 0; j < count; j++){ 
    			if(i % a[i] == 0){ 
    				isPrime = false;
    				break;
    			}
    		}
    		
    		if(isPrime){ 
    			if(count == a.getSize())
    				a.resize(count*2);
    			a[count++] = i;
    		}
    	}
    	
    	for(int i = 0; i < count; i++)
    		cout << setw(8) << a[i];
    	cout << endl;
    	return 0;
    }

## 链表的概念与结点类模板 ##

### 顺序访问的线性群体——链表类 ###

*  链表是一种动态的数据结构，可以用来顺序访问的线性群体
 *  链表是由一系列**结点**组成的，结点可以在运行时动态生成。
 *  每一个结点包括数据域和指向链表中下一个节点的指针。如果链表每个节点中只有一个指向后继结点的指针，则该链表称为单链表。

**单链表**  
![在这里插入图片描述][20200723132626521.png]

### 单链表的节点类模板 ###

#### 在当前结点之后插入一个节点 ####

![20200723132658256.png][]

template <class T>
    void Node<T>::insertAfter(Node<T> *p){ 
    	//p节点指针域指向当前节点的后继节点
    	p->next = next;
    	next = p; // 当前节点的指针域指向p
    }

#### 删除当前结点之后的结点 ####

![20200723132811262.png][]

Node<T>* Node<T>::deleteAfter(void){ 
    	Node<T>* temPtr = next;
    	if(next == 0)
    		return 0;
    	next = temPtr->next;
    	return temPtr; // 返回被断开的结点
    }

**示例：结点类模板**

// Node.h
    #ifndef NODE_H
    #define NODE_H
    //类模板定义
    template <class T>
    class Node{ 
    private:
    	Node<T> *next;
    public:
    	T date; // 数据域
    	Node(const T& data, Node<T>* next = 0); //构造函数
    	void insertAfter(Node<T>* p); //在本节点后插入一个同类结点p
    	Node<T>* deleteAfter(); // 删除本节点的后继结点，并返回其地址
    	Node<T>* nextNode(); // 获取后继结点的地址
    	const Node<T>* nextNode() const; // 获取后继结点的地址，作仅读使用
    	
    };
    
    // 类的实现
    // 构造函数，初始化数据和指针成员
    template <class T>
    Node<T>::Node(const T& data, Node<T>* next = 0):data(data),next(next){ }
    //返回后继结点的指针
    template <class T>
    Node<T>* Node<T>::nextNode(){ 
    	return next;
    }
    // 返回后继结点的指针
    template <class T>
    const Node<T>* Node<T>::nextNode() const{ 
    	return next;
    }
    // 在当前结点之后插入一个结点p
    template <class T>
    void Node<T>::insertAfter(Node<T> *p){ 
    	p->next = next;
    	next = p; // 当前结点的指针域指向p
    }
    // 删除当前结点的后继结点，并返回其地址
    template <class T>
    Node<T>* Node<T>::deleteAfter(){ 
    	if(next == 0) // 若当前结点没有后继结点，则返回空指针
    		return 0;
    	Node<T>* temPtr = next; 
    	next = temPtr->next;
    	return temPtr;
    }
    
    #endif // NODE_H

### 链表的基本操作 ###

*  生成链表
 *  插入节点
 *  查找结点
 *  删除结点
 *  遍历链表
 *  清空链表

**示例：链表类模板**

//LinkedList.h
    #ifndef LINKEDLIST_H
    #define LINKEDLIST_H
    #include "Node.h"
    
    template <class T>
    class LinkedList { 
    private:
        //数据成员：
        Node<T> *front, *rear;  //表头和表尾指针
        Node<T> *prevPtr, *currPtr;   //记录表当前遍历位置的指针，由插入和删除操作更新
        int size;   //表中的元素个数
        int position;   //当前元素在表中的位置序号。由函数reset使用
    
        //函数成员：
        //生成新结点，数据域为item，指针域为ptrNext
        Node<T> *newNode(const T &item,Node<T> *ptrNext=NULL);
    
        //释放结点
        void freeNode(Node<T> *p);
    
        //将链表L 拷贝到当前表（假设当前表为空）。
        //被拷贝构造函数、operator = 调用
        void copy(const LinkedList<T>& L);
    
    public:
        LinkedList();   //构造函数
        LinkedList(const LinkedList<T> &L);  //拷贝构造函数
        ~LinkedList();  //析构函数
        LinkedList<T> & operator = (const LinkedList<T> &L); //重载赋值运算符
    
        int getSize() const;    //返回链表中元素个数
        bool isEmpty() const;   //链表是否为空
    
        void reset(int pos = 0);//初始化游标的位置
        void next();    //使游标移动到下一个结点
        bool endOfList() const; //游标是否到了链尾
        int currentPosition() const;    //返回游标当前的位置
    
        void insertFront(const T &item);    //在表头插入结点
        void insertRear(const T &item);     //在表尾添加结点
        void insertAt(const T &item);       //在当前结点之前插入结点
        void insertAfter(const T &item);    //在当前结点之后插入结点
    
        T deleteFront();    //删除头结点
        void deleteCurrent();   //删除当前结点
    
        T& data();              //返回对当前结点成员数据的引用
        const T& data() const;   //返回对当前结点成员数据的常引用
    
        //清空链表：释放所有结点的内存空间。被析构函数、operator= 调用
        void clear();
    };
    
    template <class T> //生成新结点
    Node<T> *LinkedList<T>::newNode(const T& item, Node<T>* ptrNext)
    { 
        Node<T> *p;
        p = new Node<T>(item, ptrNext);
        if (p == NULL)
        { 
            cout << "Memory allocation failure!\n";
            exit(1);
        }
        return p;
    }
    
    template <class T>
    void LinkedList<T>::freeNode(Node<T> *p) //释放结点
    { 
        delete p;
    }
    
    template <class T>
    void LinkedList<T>::copy(const LinkedList<T>& L) //链表复制函数
    { 
        Node<T> *p = L.front;   //P用来遍历L 
        int pos;
        while (p != NULL)   //将L中的每一个元素插入到当前链表最后
        { 
            insertRear(p->data);
            p = p->nextNode();
        }
        if (position == -1) //如果链表空,返回
            return;
        //在新链表中重新设置prevPtr和currPtr
        prevPtr = NULL;
        currPtr = front;
        for (pos = 0; pos != position; pos++)
        { 
            prevPtr = currPtr;
            currPtr = currPtr->nextNode();
        }
    }
    
    template <class T>  //构造一个新链表，将有关指针设置为空，size为0，position为-1
    LinkedList<T>::LinkedList() : front(NULL), rear(NULL),
    prevPtr(NULL), currPtr(NULL), size(0), position(-1)
    { }
    
    template <class T>
    LinkedList<T>::LinkedList(const LinkedList<T>& L)  //拷贝构造函数
    { 
        front = rear = NULL;
        prevPtr = currPtr = NULL;
        size = 0;
        position = -1;
        copy(L);
    }
    
    template <class T>
    LinkedList<T>::~LinkedList()    //析构函数
    { 
        clear();
    }
    
    template <class T>
    LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& L)//重载"="
    { 
        if (this == &L) // 不能将链表赋值给它自身
            return *this;
        clear();
        copy(L);
        return *this;
    }
    
    template <class T>
    int LinkedList<T>::getSize() const  //返回链表大小的函数
    { 
        return size;
    }
    
    template <class T>
    bool LinkedList<T>::isEmpty() const //判断链表为空否
    { 
        return size == 0;
    }
    
    template <class T>
    void LinkedList<T>::reset(int pos)  //将链表当前位置设置为pos 
    { 
        int startPos;
        if (front == NULL)  // 如果链表为空，返回
            return;
        if (pos < 0 || pos > size - 1)  // 如果指定位置不合法，中止程序
        { 
            std::cerr << "Reset: Invalid list position: " << pos << endl;
            return;
        }
        // 设置与遍历链表有关的成员
        if (pos == 0)   // 如果pos为0，将指针重新设置到表头
        { 
            prevPtr = NULL;
            currPtr = front;
            position = 0;
        }
        else    // 重新设置 currPtr, prevPtr, 和 position 
        { 
            currPtr = front->nextNode();
            prevPtr = front;
            startPos = 1;
            for (position = startPos; position != pos; position++)
            { 
                prevPtr = currPtr;
                currPtr = currPtr->nextNode();
            }
        }
    }
    
    template <class T>
    void LinkedList<T>::next()  //将prevPtr和currPtr向前移动一个结点
    { 
        if (currPtr != NULL)
        { 
            prevPtr = currPtr;
            currPtr = currPtr->nextNode();
            position++;
        }
    }
    
    template <class T>
    bool LinkedList<T>::endOfList() const   // 判断是否已达表尾
    { 
        return currPtr == NULL;
    }
    
    template <class T>
    int LinkedList<T>::currentPosition() const  // 返回当前结点的位置
    { 
        return position;
    }
    
    template <class T>
    void LinkedList<T>::insertFront(const T& item)   // 将item插入在表头
    { 
        if (front != NULL)  // 如果链表不空则调用Reset 
            reset();
        insertAt(item); // 在表头插入
    }
    
    template <class T>
    void LinkedList<T>::insertRear(const T& item)   // 在表尾插入结点
    { 
        Node<T> *nNode;
        prevPtr = rear;
        nNode = newNode(item);  // 创建新结点
        if (rear == NULL)   // 如果表空则插入在表头
            front = rear = nNode;
        else
        { 
            rear->insertAfter(nNode);
            rear = nNode;
        }
        currPtr = rear;
        position = size;
        size++;
    }
    
    template <class T>
    void LinkedList<T>::insertAt(const T& item) // 将item插入在链表当前位置
    { 
        Node<T> *nNode;
        if (prevPtr == NULL)    // 插入在链表头，包括将结点插入到空表中
        { 
            nNode = newNode(item, front);
            front = nNode;
        }
        else    // 插入到链表之中. 将结点置于prevPtr之后
        { 
            nNode = newNode(item);
            prevPtr->insertAfter(nNode);
        }
        if (prevPtr == rear)    //正在向空表中插入，或者是插入到非空表的表尾
        { 
            rear = nNode;   //更新rear 
            position = size;    //更新position 
        }
        currPtr = nNode;    //更新currPtr
        size++; //使size增值
    }
    
    template <class T>
    void LinkedList<T>::insertAfter(const T& item)  // 将item 插入到链表当前位置之后
    { 
        Node<T> *p;
        p = newNode(item);
        if (front == NULL)   // 向空表中插入
        { 
            front = currPtr = rear = p;
            position = 0;
        }
        else    // 插入到最后一个结点之后
        { 
            if (currPtr == NULL)
                currPtr = prevPtr;
            currPtr->insertAfter(p);
            if (currPtr == rear)
            { 
                rear = p;
                position = size;
            }
            else
                position++;
            prevPtr = currPtr;
            currPtr = p;
        }
        size++;              // 使链表长度增值
    }
    
    template <class T>
    T LinkedList<T>::deleteFront()  // 删除表头结点
    { 
        T item;
        reset();
        if (front == NULL)
        { 
            cerr << "Invalid deletion!" << endl;
            exit(1);
        }
        item = currPtr->data;
        deleteCurrent();
        return item;
    }
    
    template <class T>
    void LinkedList<T>::deleteCurrent() // 删除链表当前位置的结点
    { 
        Node<T> *p;
        if (currPtr == NULL)    // 如果表空或达到表尾则出错
        { 
            cerr << "Invalid deletion!" << endl;
            exit(1);
        }
        if (prevPtr == NULL)    // 删除将发生在表头或链表之中
        { 
            p = front;  // 保存头结点地址
            front = front->nextNode();  //将其从链表中分离
        }
        else    //分离prevPtr之后的一个内部结点，保存其地址
            p = prevPtr->deleteAfter();
    
        if (p == rear)  // 如果表尾结点被删除
        { 
            rear = prevPtr; //新的表尾是prevPtr 
            position--; //position自减
        }
        currPtr = p->nextNode();    // 使currPtr越过被删除的结点
        freeNode(p);    // 释放结点，并
        size--; //使链表长度自减
    }
    
    template <class T>
    T& LinkedList<T>::data()    //返回一个当前结点数值的引用
    { 
        if (size == 0 || currPtr == NULL)   // 如果链表为空或已经完成遍历则出错
        { 
            cerr << "Data: invalid reference!" << endl;
            exit(1);
        }
        return currPtr->data;
    }
    
    template <class T>
    void LinkedList<T>::clear() //清空链表
    { 
        Node<T> *currPosition, *nextPosition;
        currPosition = front;
        while (currPosition != NULL)
        { 
            nextPosition = currPosition->nextNode(); //取得下一结点的地址
            freeNode(currPosition); //删除当前结点
            currPosition = nextPosition;    //当前指针移动到下一结点
        }
        front = rear = NULL;
        prevPtr = currPtr = NULL;
        size = 0;
        position = -1;
    }
    #endif //LINKEDLIST_H

## 栈类 ##

栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈底。栈是一种**后进先出**的数据结构。

**栈示意图**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2_size_16_color_FFFFFF_t_70][]

### 栈的基本状态 ###

*  栈空
 *  栈满
 *  一般状态

#### 栈空 ####

*  栈中没有元素（以数组容纳的栈为例）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2_size_16_color_FFFFFF_t_70 1][]

#### 栈满 ####

*  栈中元素个数达到上限（以数组容纳的栈为例）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2_size_16_color_FFFFFF_t_70 2][]

#### 一般状态 ####

*  栈中有元素，但未达到栈满状态（以数组容纳的栈为例）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2_size_16_color_FFFFFF_t_70 3][]

#### 栈的基本操作 ####

*  初始化
 *  入栈
 *  出栈
 *  清空栈
 *  访问栈顶元素
 *  检查栈的状态(满、空)

#### 栈类模板 ####

//Stack.h
    #ifndef STACK_H
    #define STACK_H
    #include <cassert> 
    template <class T, int SIZE = 50>
    class Stack {
    private:
        T list[SIZE];
        int top;   // 栈顶状态
    public:
        Stack();
        void push(const T &item);
        T pop();
        void clear();
        const T &peek() const;
        bool isEmpty() const;
        bool isFull() const;
    };
    
    //模板的实现
    template <class T, int SIZE>
    Stack<T, SIZE>::Stack() : top(-1) { }   
    template <class T, int SIZE>
    void Stack<T, SIZE>::push(const T &item) {  
        assert(!isFull());  
        list[++top] = item; 
    }
    template <class T, int SIZE>
    T Stack<T, SIZE>::pop() {   
        assert(!isEmpty()); 
        return list[top--]; 
    }
    template <class T, int SIZE>
    const T &Stack<T, SIZE>::peek() const {
        assert(!isEmpty()); 
        return list[top];   //返回栈顶元素
    }
    template <class T, int SIZE>
    bool Stack<T, SIZE>::isEmpty() const {
        return top == -1;
    }
    template <class T, int SIZE>
    bool Stack<T, SIZE>::isFull() const {   
        return top == SIZE - 1;
    }
    
    template <class T, int SIZE>
    void Stack<T, SIZE>::clear() {  
        top = -1;
    }
    
    #endif  //STACK_H

#### 栈的应用 ####

**一个简单的整数计算器**

实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，若要计算"3+5"则输入"3 5 +"。乘方运算符用"^“表示。每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入"c”。当键入"q"时程序结束。

//Calculator.h
    #ifndef CALCULATOR_H
    #define CALCULATOR_H
    #include "Stack.h" // 包含栈类模板定义文件
    
    class Calculator {   //计算器类
    private:
        Stack<double> s;    // 操作数栈
        void enter(double num); //将操作数num压入栈
        //连续将两个操作数弹出栈，放在opnd1和opnd2中
        bool getTwoOperands(double &opnd1, double &opnd2);
        void compute(char op);  //执行由操作符op指定的运算
    public:
        void run();     //运行计算器程序
        void clear();   //清空操作数栈
    };
    #endif //CALCULATOR_H
    
    //Calculator.cpp
    #include "Calculator.h"
    #include <iostream>
    #include <sstream>
    #include <cmath>
    using namespace std;
    
    //工具函数，用于将字符串转换为实数
    inline double stringToDouble(const string &str) { 
        istringstream stream(str);  //字符串输入流
        double result;
        stream >> result;
        return result;
    }
    
    void Calculator::enter(double num) {     //将操作数num压入栈
        s.push(num);
    }
    
    bool Calculator::getTwoOperands(double &opnd1, double &opnd2) { 
        if (s.isEmpty()) {   //检查栈是否空
            cerr << "Missing operand!" << endl;
            return false;
        }
        opnd1 = s.pop();    //将右操作数弹出栈
        if (s.isEmpty()) {   //检查栈是否空
            cerr << "Missing operand!" << endl;
            return false;
        }
        opnd2 = s.pop();    //将左操作数弹出栈
        return true;
    }
    
    void Calculator::compute(char op) {  //执行运算
        double operand1, operand2;
        bool result = getTwoOperands(operand1, operand2);   
        if (result) {    //如果成功，执行运算并将运算结果压入栈
            switch(op) { 
            case '+': s.push(operand2 + operand1); break;
            case '-': s.push(operand2 - operand1); break;
            case '*': s.push(operand2 * operand1); break;
            case '/': if (operand1 == 0) {     //检查除数是否为0
                     cerr << "Divided by 0!" << endl;
                     s.clear();    //除数为0时清空栈
                          } else
                     s.push(operand2 / operand1);
                          break;
            case '^': s.push(pow(operand2, operand1)); break;
            default:  cerr << "Unrecognized operator!" << endl;
                          break;
            }
            cout << "= " << s.peek() << " ";    //输出本次运算结果 
        } else
            s.clear();  //操作数不够，清空栈
    }
    
    void Calculator::run() {  //读入并处理后缀表达式
        string str;
        while (cin >> str, str != "q") { 
            switch(str[0]) { 
            case 'c': s.clear(); break;
            case '-': //遇'-'需判断是减号还是负号
                if (str.size() > 1)
                    enter(stringToDouble(str)); 
                else
                    compute(str[0]);    
                break;
            case '+':   //遇到其它操作符时
            case '*':
            case '/':
            case '^':
                compute(str[0]);   break;
            default: //若读入的是操作数，转换为整型后压入栈
                enter(stringToDouble(str)); break;
            }
        }
    }
    void Calculator::clear() {   //清空操作数栈
        s.clear(); 
    }
    
    //9_9.cpp
    #include "Calculator.h"
    
    int main() { 
        Calculator c;
        c.run();
        return 0;
    }

## 队列 ##

*  队列是只能向一端添加元素，从另一端删除元素的线性群体

![20200723133326771.png][]

### 队列的基本状态 ###

*  队空
 *  队满
 *  一般状态

#### 队空 ####

*  队列中没有元素（以数组容纳的队列为例）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2_size_16_color_FFFFFF_t_70 4][]

#### 队满 ####

*  队列中元素个数达到上限（以数组容纳的队列为例）

![2020072313340373.png][]

#### 一般状态 ####

*  队列中有元素，但未达到队满状态（以数组容纳的队列为例）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2_size_16_color_FFFFFF_t_70 5][]

### 循环队列 ###

*  在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组开头。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2_size_16_color_FFFFFF_t_70 6][]

//Queue.h
    #ifndef QUEUE_H
    #define QUEUE_H
    #include <cassert>
    //类模板的定义
    template <class T, int SIZE = 50>
    class Queue { 
    private:
        int front, rear, count; //队头指针、队尾指针、元素个数
        T list[SIZE];   //队列元素数组
    public:
        Queue();          //构造函数，初始化队头指针、队尾指针、元素个数
        void insert(const T &item); //新元素入队
        T remove(); //元素出队
        void clear();   //清空队列
        const T &getFront() const;  //访问队首元素
        //测试队列状态
        int getLength() const;//求队列长度
        bool isEmpty() const;//判断队列空否
        bool isFull() const;//判断队列满否
    };
    //构造函数，初始化队头指针、队尾指针、元素个数
    template <class T, int SIZE>
    Queue<T, SIZE>::Queue() : front(0), rear(0), count(0) {  }
    
    template <class T, int SIZE>
    void Queue<T, SIZE>::insert (const T& item) { //向队尾插入元素
        assert(count != SIZE);
        count++;    //元素个数增1
        list[rear] = item;  //向队尾插入元素
        rear = (rear + 1) % SIZE;   //队尾指针增1，用取余运算实现循环队列
    }
    template <class T, int SIZE> T Queue<T, SIZE>::remove() {    
        assert(count != 0);
        int temp = front;   //记录下原先的队首指针
        count--;        //元素个数自减
        front = (front + 1) % SIZE;//队首指针增1。取余以实现循环队列
        return list[temp];  //返回首元素值
    }
    template <class T, int SIZE>
    const T &Queue<T, SIZE>::getFront() const {  
        return list[front];
    }
    template <class T, int SIZE>
    int Queue<T, SIZE>::getLength() const {  //返回队列元素个数
        return count;
    }
    
    template <class T, int SIZE>
    bool Queue<T, SIZE>::isEmpty() const {   //测试队空否
        return count == 0;
    }
    template <class T, int SIZE>
    bool Queue<T, SIZE>::isFull() const {    //测试队满否
        return count == SIZE;
    }
    template <class T, int SIZE>
    void Queue<T, SIZE>::clear() {   //清空队列
        count = 0;
        front = 0; 
        rear = 0; 
    }
    #endif //QUEUE_H

[20200723132626521.png]: /images/20230209/0629046afba64424aee49035cd318afc.png
[20200723132658256.png]: https://img-blog.csdnimg.cn/20200723132658256.png
[20200723132811262.png]: https://img-blog.csdnimg.cn/20200723132811262.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200723132910535.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200723132955958.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200723133036313.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200723133123589.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2,size_16,color_FFFFFF,t_70
[20200723133326771.png]: https://img-blog.csdnimg.cn/20200723133326771.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2020072313321415.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2,size_16,color_FFFFFF,t_70
[2020072313340373.png]: https://img-blog.csdnimg.cn/2020072313340373.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200723133439880.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200723133518391.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1ODY2NzM2,size_16,color_FFFFFF,t_70