栈与队列的3个oj题

栈与队列

225.用队列实现栈

解题思路

队列的性质是先进的先出，栈的性质是先进是后出。
我们设计的这两个队列，当添加数据的时候，插入有数据不为空的一个队列。当删除数据的，把数据移动到为空的队列中去，只留下队尾的数据，该数据就是要删除的数据。

代码

下面这是创建队列

typedefint QueueTypeDate;typedefstructQListNode{structQListNode* next;
    QueueTypeDate val;}QNode;typedefstructQueue{
    QNode* head;
    QNode* tail;}Queue;voidQueueInit(Queue* q){assert(q);
    q->head = q->tail =NULL;}

bool QueueEmpty(Queue* q){assert(q);return q->head ==NULL;}voidQueuePush(Queue* q, QueueTypeDate x){assert(q);
    QNode* newnode =(QNode*)malloc(sizeof(QNode));
    newnode->next =NULL;
    newnode->val = x;if(QueueEmpty(q))
        q->head = q->tail = newnode;else{
        q->tail->next = newnode;
        q->tail = newnode;}}voidQueuePop(Queue* q){assert(q);assert(!QueueEmpty(q));if(q->head == q->tail){free(q->head);
        q->head = q->tail =NULL;}else{
        QNode* next = q->head->next;free(q->head);
        q->head = next;}}
QueueTypeDate QueueFront(Queue* q){assert(q);assert(!QueueEmpty(q));return q->head->val;}
QueueTypeDate QueueBack(Queue* q){assert(q);assert(!QueueEmpty(q));return q->tail->val;}intQueueSize(Queue* q){assert(q);
    QNode* cur = q->head;int size =0;while(cur){
        size++;
        cur = cur->next;}return size;}voidQueueDestroy(Queue* q){assert(q);while(q->head){QueuePop(q);}}

队列实现栈

typedefstruct{
    Queue Q1;
    Queue Q2;} MyStack;

MyStack*myStackCreate(){
    MyStack* obj=(MyStack*)malloc(sizeof(MyStack));QueueInit(&obj->Q1);QueueInit(&obj->Q2);return obj;}voidmyStackPush(MyStack* obj,int x){if(QueueEmpty(&obj->Q1))QueuePush(&obj->Q2,x);elseQueuePush(&obj->Q1,x);}intmyStackPop(MyStack* obj){int x;if(QueueEmpty(&obj->Q1)){while((&obj->Q2)->head!=(&obj->Q2)->tail){
            x=QueueFront(&obj->Q2);QueuePop(&obj->Q2);QueuePush(&obj->Q1,x);}   
        x=QueueFront(&obj->Q2);QueuePop(&obj->Q2);}else{while((&obj->Q1)->head!=(&obj->Q1)->tail){
            x=QueueFront(&obj->Q1);QueuePop(&obj->Q1);QueuePush(&obj->Q2,x);}   
        x=QueueFront(&obj->Q1);QueuePop(&obj->Q1);}return x;}intmyStackTop(MyStack* obj){if(QueueEmpty(&obj->Q1))returnQueueBack(&obj->Q2);elsereturnQueueBack(&obj->Q1);}

bool myStackEmpty(MyStack* obj){returnQueueEmpty(&obj->Q1)&&QueueEmpty(&obj->Q2);}voidmyStackFree(MyStack* obj){QueueDestroy(&obj->Q1);QueueDestroy(&obj->Q2);free(obj);}

232.用栈实现队列

解题思路

一个栈来表示入队（简称入栈），另一个栈来表示出队（简称出栈）。当出队是，如果出栈为空，入栈里面的全部数据进入出栈中。
当查看队头的元素的时候，就是要察看出栈栈顶的数据。要注意出栈数据为空的情况。

代码

栈的实现——》数据结构——栈

typedefstruct{
    Stack outstack;
    Stack instack;} MyQueue;

MyQueue*myQueueCreate(){
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));InitStack(&obj->outstack);InitStack(&obj->instack);return obj;}voidmyQueuePush(MyQueue* obj,int x){StackPush(&obj->instack,x);}intmyQueuePop(MyQueue* obj){if(!StackSize(&obj->outstack)){while(StackSize(&obj->instack)){StackPush(&obj->outstack,StackTop(&obj->instack));StackPop(&obj->instack);}}int x=StackTop(&obj->outstack);StackPop(&obj->outstack);return x;}intmyQueuePeek(MyQueue* obj){if(!StackSize(&obj->outstack)){while(StackSize(&obj->instack)){StackPush(&obj->outstack,StackTop(&obj->instack));StackPop(&obj->instack);}}returnStackTop(&obj->outstack);}

bool myQueueEmpty(MyQueue* obj){return!(StackSize(&obj->instack)||StackSize(&obj->outstack));}voidmyQueueFree(MyQueue* obj){StackDestroy(&obj->outstack);StackDestroy(&obj->instack);free(obj);}

622.设计循环队列

解题思路

我们创建的循环队列为静态。队列长度为N，那么我们里面只用来储存N-1个数据。
队列里面的成员包括，数据，队列起始下标（头标），队列末尾下标（尾标）,队列可以有效储存数据的长度。
我们这样设计循环队列：当头标和尾标相等时，队列为空；当尾标下一个坐标等于头标时，为满。

我们设计的队列本质是连续储存的数组。
当增加数据的时候，尾向后移动；当删除数据的时候，头向后走。
不为空的时候。头或尾到最后的边界的时候，要回到头的地方。
插入的时候注意满的情况，删除的时候注意为空的时候。

代码

typedefstruct{int* arr;int head;int tail;int capacity;} MyCircularQueue;

MyCircularQueue*myCircularQueueCreate(int k){
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->arr=(int*)malloc(sizeof(int)*(k+1));
    obj->head=obj->tail=0;
    obj->capacity=k;return obj;}

bool myCircularQueueIsEmpty(MyCircularQueue* obj){return obj->head==obj->tail;}

bool myCircularQueueIsFull(MyCircularQueue* obj){int curtail=obj->tail+1;if(curtail==obj->capacity+1)
    curtail=0;return curtail==obj->head;}

bool myCircularQueueEnQueue(MyCircularQueue* obj,int value){if(myCircularQueueIsFull(obj))return false;
    obj->arr[obj->tail]=value;
    obj->tail++;if(obj->tail==obj->capacity+1)
    obj->tail=0;return true;}

bool myCircularQueueDeQueue(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj))return false;
    obj->head++;if(obj->head==obj->capacity+1)
    obj->head=0;return true;}intmyCircularQueueFront(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj))return-1;return obj->arr[obj->head];}intmyCircularQueueRear(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj))return-1;int curtail=obj->tail-1;if(curtail==-1)return obj->arr[obj->capacity];elsereturn obj->arr[curtail];}voidmyCircularQueueFree(MyCircularQueue* obj){free(obj->arr);
    obj->arr=NULL;free(obj);}