【计算机本科补全计划】王道单科--队列的数组实现

正文之前

我发现哈，王道单科现在对我的作用真的很有限，以前看起来觉得挺难得东西，但是现在看书看多了觉得，也就那样？就以前考研的时候，为了加深理解一定要自己实现一遍，有兴趣看看的可以看看我的以前的考研的文章，跟今天这种比起来完全简直是被吊打！那时候瞻前顾后的实现栈，实现队列，后来C++ primer给我的不仅仅是容器的使用，更多的还是加深了对这些数据结构的认识。让我能驾轻就熟的认识这些概念。建议大家也多看看。

正文

#include <iostream>
using namespace std;
#define maxsize 20


typedef struct 
{
    int a[maxsize];
    int front;
    int rear;
} Queue,*ptrq;

void InitQueue(ptrq ptrs)
{
    ptrs->front=ptrs->rear=0;
}

void push_back(ptrq ptrs,int item)
{
    if(ptrs->front!=(ptrs->rear+1)%maxsize)   
        ptrs->a[ptrs->rear++]=item;
    else 
        {cout<<"The Queue is Full! Get out!"<<endl;return;};
}

int pop_front(ptrq ptrs)
{
    if(ptrs->front!=ptrs->rear)
        return ptrs->a[ptrs->front++];
    else 
    {
        cout<<"False ,the Queue is empty！"<<endl;
        return 0;
    }
}

bool IsEmpty(ptrq ptrs)
{
    if(ptrs->front==ptrs->rear)
    {
        cout<<"The Queue is Empty!!"<<endl;
        return false;
    }
    return true;
}

int main()
{
    ptrq test = new Queue;
    InitQueue(test);
    bool emp=IsEmpty(test);
    if(!emp)
        cout<<"Please fill this Queue"<<endl;
    for(int i=0;i<maxsize;++i)
        push_back(test,10*(i/4)+i%3+3);
    for(;test->front!=test->rear;)
        cout<<pop_front(test)<<endl;
    delete(test);  
    return 0;
}

注释我就不打了，但是还是解释下吧，解释完了就去吃饭！！！吃饭吃饭！！ 因为下午有课，所以待会吃完饭，回去睡个觉就去教室，晚点吃饭有利于压缩娱乐时间！

首先，定义了基于数组的Queue结构体，并且表明了一个指向Queue的ptrq的指针类型别名。里面包含了一个数组用于存储数据，两个指针用下标的方式作为队头队尾指针之用。有想法的也可以自己改点别的结构。反正最后这几个是没法跑的。另外，maxsize是20，但是实际用于存储数据的只有19个数据块，因为要满足留出一个空地在队尾元素的下一个地方，想必熟悉新标准的朋友们就知道了。这就是新标准中随处可见的前闭后开的区间模型。好比迭代器，begin指向第一个元素，但是end指向最后一个元素的下一个地方，也称为尾后迭代器，这里的尾指针是同一个意思。[begin，end）

初始化队列的话就是把两个指针调整下，在new分配动态内存的过程中其实已经默认值初始化了，但是我们以防万一对不？另外还可以用这个瞬间置空整个队列， 岂不是很爽！！？？

pushback() 以及 popfront()这两个成员函数是很经典的么，顾名思义，从队尾插入，从队首删除。只是注意，队首队尾都是++，而且都提供了预判的，一旦队空或者队满，都会跳过读取过程！另外这个跟栈是很不同的，具体的仔细处希望大家伙好好揣摩。

IsEmpty（）这个完全原理就更简单了！不说了！

另外，大家看新的C++11标准，气死人！！

容器都给你规划的好好地了。根本不用自己写！哎。

std::queue

C++ Containers library std::queue

Defined in header <queue>
template<
    class T,
    class Container = std::deque<T>
\> class queue;

The std::queue class is a container adapter that gives the programmer the functionality of a queue - specifically, a FIFO (first-in, first-out) data structure.

The class template acts as a wrapper to the underlying container - only a specific set of functions is provided. The queue pushes the elements on the back of the underlying container and pops them from the front.

Template parameters

T - The type of the stored elements. The behavior is undefined if T is not the same type as Container::value_type. (since C++17)

Container - The type of the underlying container to use to store the elements. The container must satisfy the requirements of SequenceContainer. Additionally, it must provide the following functions with the usual semantics:

• back()
• front()
• push_back()
• pop_front()

The standard containers std::deque and std::list satisfy these requirements.

Member types

• Member type Definition
• container_type Container
• valuetype Container::valuetype
• sizetype Container::sizetype
• reference Container::reference
• constreference Container::constreference

Member functions

Element access

Non-member functions

• operator==
• operator!=
• operator<
• operator<=
• operator>
• operator>=

正文之后

我需要说明下，王道里的都是传入引用作为实参，我的是指针，这个是初期学习的时候受到了一些影响，严格来说其实引用更加安全而且好用，规避了C里面最难的指针，但是有些时候指针也是很好用的，各有长处吧！