用队列实现栈
队列是先进先出，而栈是先进后出，那我们怎么用两个队列来实现一个栈呢？
我们想要出数据的话，由于要实现的是栈，所以要后进先出，所以我们需要出4，但是由于他是队列，只能出1，但是我们有两个队列，我们假设队列一中有size个数据，那我们只需要将size-1个都放到另一个队列里面，然后在出掉最后一个就可以了。
如果需要入数据的话，我们就在不为空的那个队列后面入数据。
大概思想知道以后，我们就可以上手写代码了。（由于C语言没有队列，所以我们需要先拷贝一份我们之前写好的队列）
typedef int QDataType; typedef struct QNode { QDataType date; struct QNode* next; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; //初始化队列 void QueueInit(Queue* pq); //入队列 void QueuePush(Queue* pq, QDataType x); //出队列 void QueuePop(Queue* pq); //获取队头的元素 QDataType QueueFront(Queue* pq); //获取队头尾的元素 QDataType QueueBack(Queue* pq); //获取队列中有效数据的个数 int QueueSize(Queue* pq); //判断队列是否为空 bool QueueEmpty(Queue* pq); //销毁队列 void QueuDestroy(Queue* pq); //初始化队列 void QueueInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; pq->size = 0; } //入队列 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->date = x; newnode->next = NULL; if (pq->head == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; } //出队列 void QueuePop(Queue* pq) { assert(pq); assert(pq->head); if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); pq->head = next; } pq->size--; } //获取队头的元素 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head); return pq->head->date; } //获取队头尾的元素 QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->head); return pq->tail->date; } //获取队列中有效数据的个数 int QueueSize(Queue* pq) { assert(pq); return pq->size; } //判断队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; } //销毁队列 void QueuDestroy(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; } //上面是我们自己的队列 // typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* obj = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&obj->q1); QueueInit(&obj->q2); return obj; } void myStackPush(MyStack* obj, int x) { //Push到不为空的队列中 if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); } else { QueuePush(&obj->q2,x); } } int myStackPop(MyStack* obj) { //假设q1不为空 Queue* noEmpty = &obj->q1; Queue* Empty = &obj->q2; //如果假设错误，修改 if(QueueEmpty(&obj->q1)) { noEmpty = &obj->q2; Empty = &obj->q1; } //到数据 int x = QueueFront(noEmpty); while(noEmpty->size>1) { QueuePush(Empty,x); QueuePop(noEmpty); x = QueueFront(noEmpty); } //此时x就保存了最后一个数据，pop掉，返回就可以 QueuePop(noEmpty); return x; } int myStackTop(MyStack* obj) { //返回不为空的队列的尾 if(QueueEmpty(&obj->q1)) { return QueueBack(&obj->q2); } else { return QueueBack(&obj->q1); } } bool myStackEmpty(MyStack* obj) { //两个队列都为空，栈才为空 return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { QueuDestroy(&obj->q1); QueuDestroy(&obj->q2); free(obj); }
本题逻辑比较简单，但是结构很强，需要好好理解消化。
用栈实现队列
这个题和第一个题很相似，是用两个栈实现一个队列。
那这又怎么操作呢？
我们同样push数据时，如果两个都为空的话都可以push，但是如果出数据的话，由于需要先进先出，所以需要将不为空的那个栈的数据放到另一个栈中。
接下来另一个栈的数据是不是就满足我们需要的顺序了，正好1先进的1先出，接着是2,3,4,那如果没出的话接着push数据呢，我们只需要将数据还push到原来的呢个栈，这是我们不难发现只要当第二个栈的数据出完之后，然后将原本那个栈的数据倒过来就可以了。这个个队列不一样的是，不用每次都倒数据，我们可以将第一个栈叫push栈，第二个栈叫pop栈，然后当pop栈为空时，就将数据倒过来，接着出就可以了，如果两个栈都空了，那说明我们的队列就空了。
代码如下;
typedef int STDateType; typedef struct Stack { STDateType* arr; int top; int capacity; }Stack; // 初始化栈 void StackInit(Stack* ps); // 入栈 void StackPush(Stack* ps, STDateType x); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDateType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 bool StackEmpty(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps); // 初始化栈 void StackInit(Stack* ps) { assert(ps); ps->arr = NULL; ps->capacity = 0; ps->top = 0; } // 入栈 void StackPush(Stack* ps, STDateType x) { assert(ps); if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDateType* pa = (STDateType*)realloc(ps->arr, newcapacity * sizeof(STDateType)); if (ps == NULL) { perror("realloc fail"); exit(-1); } ps->arr = pa; ps->capacity = newcapacity; } ps->arr[ps->top] = x; ps->top++; } // 出栈 void StackPop(Stack* ps) { assert(ps); assert(ps ->top > 0); ps->top--; } // 获取栈顶元素 STDateType StackTop(Stack* ps) { assert(ps); return ps->arr[ps->top - 1]; } // 获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps->top; } // 检测栈是否为空 bool StackEmpty(Stack* ps) { assert(ps); return ps->top == 0 ? true : false; } // 销毁栈 void StackDestroy(Stack* ps) { assert(ps); free(ps->arr); ps->arr = NULL; ps->capacity = 0; ps->top = 0; } //我们自己的栈 / typedef struct { Stack Stackpush; Stack Stackpop; } MyQueue; MyQueue* myQueueCreate() { MyQueue* obj= (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&obj->Stackpush); StackInit(&obj->Stackpop); return obj; } void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->Stackpush,x); } int myQueuePeek(MyQueue* obj) { //如果Pop栈为空就倒数据 if(StackEmpty(&obj->Stackpop)) { while(!StackEmpty(&obj->Stackpush)) { StackPush(&obj->Stackpop,StackTop(&obj->Stackpush)); StackPop(&obj->Stackpush); } } return StackTop(&obj->Stackpop); } int myQueuePop(MyQueue* obj) { //调用返回队头的元素，并且判断了Pop栈是否为空 int x = myQueuePeek(obj); StackPop(&obj->Stackpop); return x; } bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->Stackpop)&&StackEmpty(&obj->Stackpush); } void myQueueFree(MyQueue* obj) { StackDestroy(&obj->Stackpop); StackDestroy(&obj->Stackpush); free(obj); }
这两个题逻辑非常简单，但是都对我们对结构的了解有很大的挑战。
设计循环队列
循环队列我们也可以用数组实现，也可以用链表实现，但是使用链表我们构造链表也是一件很麻烦的事情，而且当队列满时和队列空时情况一样，我们会很难区分，但是用链表也是可以实现的，但是我们这里介绍用数组实现。
我们这里需要K个空间，但是我们多开一个空间不存储数据，方便我们来区别空和满的情况。
我们可以看到空队列时front是和rear相等的。
当满队列时rear+1就等于front了。
设计这个循环队列，当rear超过K+1是我们就要让他回到0出，我们可以用if判断，也可以用取模操作。我们入数据就在rear位置入，出数据只需要将front++就可以了但是front也可能会越界。所以也需要取模操作。
这种情况front就可能越界，所以在写代码是要控制好边界。
代码如下：
typedef struct { int* a; int front; int rear; int k; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* Mq = ( MyCircularQueue*)malloc(sizeof(MyCircularQueue)); Mq->a = (int*)malloc(sizeof(int)*(k+1)); Mq->front = 0; Mq->rear = 0; Mq->k = k; return Mq; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front==obj->rear; } 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->rear = obj->rear%(obj->k+1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return false; } obj->front++; //防止front越界 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; } //obj->read==0的话应该是返回k那个位置的 return obj->rear==0?obj->a[obj->k]:obj->a[obj->rear-1]; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); }
今天的分享就到这里结束了，感谢大家的关注和支持。
