前言
例题1：循环队列
栈两种线性表示都能实现，队列呢？队列适合使用链表实现，使用顺序结构(即固定的连续空间)实现时会出现假溢出的问题，因此大佬们设计出了循环队列，循环队列就是为了解决顺序结构实现队列假溢出问题的现在我们来看看用顺序表实现队列：
因为队列长度有限，所以我们要及时的判断什么时候队列满了。那么怎么判断队列是否满了呢？
如果我们通过队尾和队顶是否相等来判断是否填满就会发现，在队列空的时候，队尾也等于对队顶。所以我们不能通过这种方法来判断：
那么我们该如何解决呢？
方法1：
加一个size来计数
方法2：
多添加一个位置：
空的情况：
满的情况：
下面我们就以方法2来实现代码：
typedef struct { int *a; int front; int rear; int k; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); obj->a=(int*)malloc(sizeof(int)*(k+1)); obj->k=k; obj->front=obj->rear=0; return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->rear==obj->front; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->rear+1)%(obj->k+1)==obj->front; } //入队 bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) return false; obj->a[obj->rear++]=value; obj->rear%=(obj->k+1); return true; } //出队 bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return false; ++obj->front; obj->front%=(obj->k+1); return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->a[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; return obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)]; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); }
这里我们只要关注这几点，其他的都很好实现：
空的情况：
满的情况：
在这里我们学到了如何在数组里建立循环！那就是通过mod数组的长度，就可以使数组循环起来！
找队尾：
尾部其实就是rear的后面一个元素，即rear-1，但是当rear等于0的时候，-1就会导致越界。对一个正数加a模a，得到的值不变。对于rear=0的时候进行这个操作就会避免越界的情况。
例题2：用队列实现栈
要通过队列表示栈就要熟知他们两个各自的性质。栈是有“先进后出”的特点，队列有“先进先出的特点”，综合她两的特点，我们通过以下方法来实现数据的出入：
保持一个队列为空，一个队列存数据
出栈的时候把前面的数据导入空队列，将最后一个数据pop出去。
具体实现：（队列的代码之前写过，就不展示了，详细：栈与队列）
void QueueInit(Queue* pq); void QueueDestroy(Queue* pq); void QueuePush(Queue* pq, QDatatype x); void QueuePop(Queue* pq); int QueueSize(Queue* pq); bool QueueEmpty(Queue* pq); QDatatype QueueFront(Queue* pq); QDatatype QueueBack(Queue* pq); typedef int QDatatype; typedef struct QueueNode { struct QueueNode* next; QDatatype data; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack*ptr=(MyStack*)malloc(sizeof(MyStack)); if(ptr==NULL) { perror("malloc::fail"); return 0; } QueueInit(&ptr->q1); QueueInit(&ptr->q2); return ptr; } void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); } else { QueuePush(&obj->q2,x); } } int myStackPop(MyStack* obj) { Queue*emptyQ=&obj->q1; Queue *noneQ=&obj->q2; if(!QueueEmpty(emptyQ)) { emptyQ=&obj->q2; noneQ=&obj->q1; } while(QueueSize(noneQ)>1) { QueuePush(emptyQ,QueueFront(noneQ)); QueuePop(noneQ); } int top=QueueBack(noneQ); QueuePop(noneQ); return top; } int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } return QueueBack(&obj->q2); } bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); }
