1.队列也是一种线性的数据结构，队列的特征是先进先出，单向队列从队尾进去，队头出去。这种数据结构在程序里面的应用十分广泛。例如：在OS中，多进程的并发执行就是将就绪状态的进程（这个分类标准不唯一，我们简单的讨论一下ready的进程）排成一个队列，依次执行，一个进程下面的多线程也是如此。这一节我们采用数组（连续储存的方式）和链表（链式储存的方式）分别实现队列。
/*队列的基本实现*/ #include"stdafx.h" #include<iostream> #include<iomanip> #define MaxSize 64 using namespace std; /*基于数组的队列实现*/ typedef struct squeue{ int data[MaxSize]; int front=0;//队头指针 int rear=0;//队尾指针 }*squlink; class Squeue { private: squlink s;//s队列指针 public: Squeue(){ s = new squeue; } int push(int data);//从队尾入队 int pop();//从队头出队 int clear();//清空队列 int isFull();//队列是否已经饱和 int isEmpty();//队列是否已空 int num_of_queue();//队列中元素的个数 void print_all();//遍历输出 }; /*置空队列的算法*/ int Squeue::clear() { s->front = s->rear = 0; return 0; } /*判断队空的算法*/ int Squeue::isEmpty() { if (s->front == s->rear) { return 1;//返回1是队空 } return 0;//队非空。 } /*元素进队算法*/ int Squeue::push(int a) { if ((s->rear + 1) % MaxSize == s->front) { cout << "队满溢出" << endl; return 0; } else { /*首先使队尾指针位置加一，这样一来就有空间给入队元素*/ s->rear = (s->rear + 1) % MaxSize;//因为可能会出现假性溢出的情况，所以队Maxsize取模 s->data[s->rear] = a;//元素入队 return 1; } } /*判断是否队满的算法*/ int Squeue::isFull() { if ((s->rear + 1) % MaxSize == s->front) { return 1;//队满 } return 0;//队尚未满 } /*出队算法：返回当前队头元素*/ int Squeue::pop() { if (isEmpty()) { return 0;//队空 } else { s->front = (s->front + 1) % MaxSize; return (s->data[s->front]);//返回队头元素 } } int Squeue::num_of_queue() { int i = 0; i = (s->rear - s->front + MaxSize) % MaxSize; return i; } void Squeue::print_all() { int k = num_of_queue(); for (int i =1; i < k; i++) { cout << setw(5) << s->data[i]; } } /*链式储存的队列的实现*/ /*节点的结构*/ typedef struct link { int data; struct link*next; link(int a) { data = a; } }*linknode; typedef struct Q { linknode head;//队头指针 linknode tail;//队尾指针 int front;//队头 int rear;//队尾 }*Queue; class link_queue { private: Queue queue; public: link_queue();//默认构造函数。我需要他来做一些事情，把该队列初始化成一个状态 int push(int data);//元素进队 int pop();//元素出队 int clear();//清空队列 int isEmpty();//是否为空队列 void print_all();//遍历输出所有元素 }; link_queue::link_queue() { queue = new Q;//给Q队列分配空间 queue->front = queue->rear = 0; queue->head = new link(0);//初始化头部指针。 queue->tail = queue->head;//当前尾部指向头部 } int link_queue::push(int data) { linknode p = new link(data);//节点的开辟； if((queue->rear + 1) % MaxSize == queue->front) { cout << "队列已满" << endl; return 0; } queue->rear = (queue->rear + 1) % MaxSize;//队尾指针加一 queue->tail->next = p;//链表的头部指针指向下一个元素 queue->tail = p;//更新尾部 queue->tail->next = NULL;//尾部元素设置为空 return 0; } int link_queue::pop() { linknode p = NULL;//用来保存当前节点。 if (queue->front == queue->rear) { cout << "当前队列为空" << endl; return 0; } p = queue->head->next; queue->front = (queue->front + 1) % MaxSize;//头部元素更新 queue->head->next = p->next;//头部更新到下一个元素 int k = p->data; delete p;//删除当前节点 return k;//返回头部元素 } /*清空队列算法*/ int link_queue::clear() { linknode p = queue->head->next; linknode q = NULL; queue->front = queue->rear = 0; while (p) { q = p; p = p->next; delete q; } return 0; } int link_queue::isEmpty() { if (queue->front == queue->rear) { return 1;//空队列 } return 0;//非空队列 } void link_queue::print_all() { linknode p = queue->head->next; while (p) { cout << p->data << " "; p = p->next; } } int main() { cout << "************************" << endl; cout << "顺序储存的队列的实现" << endl; Squeue S; for (int i = 0; i < 10&& i < MaxSize; i++) { S.push(i); } S.print_all(); cout << endl; S.print_all(); cout << endl; cout << "*******************************" << endl; cout << "链式储存的队列的实现" << endl; link_queue l; for (int i = 0; i < 10; i++) { l.push(i); } l.print_all(); l.pop(); cout << endl; l.print_all(); return 0;
}
在前边两节我们讨论了线性数据结构：数组，链表，栈，队列。接下来我们需要在实际问题中应用他们。我将会在接下来的几章内容里举例讨论链表，队列与栈的应用。当然，我还会继续深入讨论数据结构：树（主要集中在二叉树，红黑树上），图论。
