1. 用栈（数组）实现 思想： 因为数组是一维的，头尾不相连，所以考虑使用两个整型变量记录队列的头和尾在数组中的下标（也就是pop和push的位置），通过对数组长度取余的方式从数组的头跳到尾，实现头尾相连（围成一圈）。
文字很难描述，可以在脑海中想象一下，有点像是火车在围成一圈的轨道上跑的感觉，火车是队列，轨道是数组。比如长度为10的数组（下标0到9），pop或者push的下标从9增加到10时，通过对10取余回到下标为0的位置。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> using namespace std; template<typename T> class Queue { public: Queue(int size) { MAX_SIZE = size; tp = new T[size]; this->size = 0; this->p_pop = 0; //队列从下标0开始pop出数据，所以初始化为0 this->p_push = -1; //队列从下标0开始push数据，所以初始化为-1 } ~Queue() { delete tp; } void push(T dat) { if (this->size == MAX_SIZE) { printf("stack is overflow!\n"); return; } p_push++; p_push %= MAX_SIZE; //push入数据到数组的末尾时，通过取余跳到数组的开头，实现循环和重复利用地址 tp[p_push] = dat; size++; } T pop() { if (size == 0) { printf("stack is empty!\n"); exit(1); } T temp = tp[p_pop++]; p_pop %= MAX_SIZE; //pop出数据到数组的末尾时，通过取余跳到数组的 size--; return temp; } int getSize() { return size; } void travel() { int len = size; int p = p_pop; printf(":==================================\n"); printf("size=%d\t", size); printf("p_pop=%d, p_push=%d\n", p_pop, p_push); // while (p != p_push + 1) { //用下标判断队列为空 // printf("%d ", tp[p]); // p++; // p %= MAX_SIZE; // } while (len--) {//用队列长度判断队列为空 printf("%d ", tp[p]); p++; p %= MAX_SIZE; } printf("\n==================================;\n"); } private: int size; //队列的长度 int MAX_SIZE; //队列长度上限，也就是数组的长度，通过构造函数初始化 T* tp; int p_pop; //记录pop的位置，也就是队列的头 int p_push; //记录push的位置，也就是队列的尾 }; int main() { Queue<int> queue(30); queue.travel(); //打印空表验证 //报三减一的游戏来验证 for (int i = 1; i <= 13; i++) {序号为1~13的人围成一圈队列 queue.push(i); } queue.travel(); int count = 0; //报数的记录，报到3的倍数的人被淘汰 while (queue.getSize()) { count++; int temp = queue.pop(); //报数的人被pop出来 if (count % 3 == 0) { //如果是3的倍数直接淘汰，不push回队列。 printf("%d\n", temp); } else { //不是3的倍数的成员push回队列，接着后面的游戏 queue.push(temp); } } queue.travel();//打印空表验证 return 0; }运行结果（Eclipse）：
2. 用链表实现 思想： 类（List）模板内创建结构体（即每一个成员），结构体内存放数据data和尾指针next（指向下一个成员从而实现循环一圈）。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; template<class T> class Link { public: Link() : head(0), tail(0), LinkSize(0) { } ~Link() { Clear(); } bool is_Empty(); int getSize(); void Push(const T&); void Pop(); void show(); void Clear(); T& getHead() { //其实可以和Pop函数合并成一个函数，带有返回值T的Pop函数 return head->data; } private: struct Node { T data; //Node* prev; Node* next; Node(const T& data, Node* next = NULL) : data(data), next(next) { } ; }; Node* head, *tail; int LinkSize; }; template<class T> inline int Link<T>::getSize() { return LinkSize; } template<class T> inline bool Link<T>::is_Empty() { return head == NULL; } template<class T> inline void Link<T>::Push(const T& data) { if (is_Empty()) { head = new Node(data); tail = head; } else { tail->next = new Node(data); tail = tail->next; } LinkSize++; } template<class T> inline void Link<T>::Pop() { Node* temp = head; head = head->next; delete temp; LinkSize--; } template<class T> inline void Link<T>::Clear() { while (!is_Empty()) { Pop(); } } template<class T> inline void Link<T>::show() { Node* lp = head; for (int i = 0; i < LinkSize; i++) { cout << lp->data << "\t"; lp = lp->next; } cout << endl; cout << endl; } int main() { int i , j; Link<int> link1; for (i = 1; i <= 9; i++) { link1.Push(i); } link1.show(); i = 0; while (!link1.is_Empty()) { i++; j = link1.getHead(); if (i % 3 != 0) { link1.Push(j); } link1.Pop(); if (i % 3 == 0) { cout << j << " is out!" << endl; link1.show(); } } return 0; }运行结果（Eclipse）：
======================================================== 【文章为本人的学习笔记部分的分享，有任何错误地方欢迎评论指出，万分感谢！】
