3.用栈实现队列
这个题目的思路与“用队列实现栈”的方法一样，用两个栈实现队列，重点也是解决出队列QueuePop的问题，将数据栈倒入临时栈，再将临时栈的栈顶取出就等同于出队列，如下：
typedef struct {
Stack _DataST;
Stack _TempST;
} MyQueue;
/** Initialize your data structure here. */
MyQueue* myQueueCreate() {
MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&pq->_DataST);
StackInit(&pq->_TempST);
return pq;
}
/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->_DataST, x);
}
/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
int front = myQueuePeek(obj);
StackPop(&obj->_TempST);
return front;
}
/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
if(StackEmpty(&obj->_TempST))
{
while(StackSize(&obj->_DataST))
{
StackPush(&obj->_TempST,StackTop(&obj->_DataST));
StackPop(&obj->_DataST);
}
}
int front = StackTop(&obj->_TempST);
return front;
}
/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->_DataST) && StackEmpty(&obj->_TempST);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->_DataST);
StackDestroy(&obj->_TempST);
free(obj);
}
4.设计循环队列
这个题目比较有意思的点在于环形，一般这种队列可以用数组和循环链表进行实现，但是出于方便起见，本题用静态数组（容量不变）实现，一般我们设置的数组大小会比实际的环形多出一个元素，而且多出来的这一个数据并不存放数据，至于为什么，主要是为了区分判空与判满的条件，如下：
有了这个判断条件之后，这个题目也就迎刃而解了，代码如下：
typedef struct {
int* _data;
int _front;
int _rear;
int _k;
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
pq->_data = (int*)malloc(sizeof(int)*(k+1));
pq->_front = pq->_rear = 0;
pq->_k = k;
return pq;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
{
return false;
}
obj->_data[obj->_rear] = value;
obj->_rear++;
//注意当尾下标为k+1的情况
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->_data[obj->_front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
int rear = obj->_rear - 1;
//注意尾下标为0的情况
if(rear == -1)
{
rear = obj->_k;
}
return obj->_data[rear];
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->_front == obj->_rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return obj->_front == (obj->_rear+1)%(obj->_k + 1);
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->_data);
free(obj);
}
