【数据结构初阶-oj题】栈和队列的oj题（入门）

前言

栈会了，队列会了，这些也要会哦

栈和队列

题1 用队列实现栈

• 队列实现栈只有一个问题： - 尾删
• 咱们有两个队列，就可以采用 “多链表操作” - 把前面的 n-1 个数据 倒进另一空链表，留下最后一个元素- QueuePop即使是头删，删的也是“最后一个元素”了

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->q1, x);elseQueuePush(&obj->q2, x);}intmyStackPop(MyStack* obj){int top =0;if(!QueueEmpty(&obj->q1)){while(QueueSize(&obj->q1)>1){QueuePush(&obj->q2,QueueFront(&obj->q1));QueuePop(&obj->q1);}
        top =QueueFront(&obj->q1);QueuePop(&obj->q1);return top;}else{while(QueueSize(&obj->q2)>1){QueuePush(&obj->q1,QueueFront(&obj->q2));QueuePop(&obj->q2);}
        top =QueueFront(&obj->q2);QueuePop(&obj->q2);return top;}}intmyStackTop(MyStack* obj){if(!QueueEmpty(&obj->q1))returnQueueBack(&obj->q1);elsereturnQueueBack(&obj->q2);}

bool myStackEmpty(MyStack* obj){returnQueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);}voidmyStackFree(MyStack* obj){
    QNode* cur1 = obj->q1.head;
    QNode* cur2 = obj->q2.head;while(cur1){
        QNode* del = cur1;
        cur1 = cur1->next;free(del);}while(cur2){
        QNode* del = cur2;
        cur2 = cur2->next;free(del);}free(obj);}

• 全程注意保持一个队列为空，用来倒数据
• 所谓实现，只要符合准则（LIFO），能够实现功能就行
• myStackCreate：此处要求在接口内创建myStack并返回
• myStackPush：直接入到非空队列
• myStackPop：把 n-1 个数据倒进空队列，再Pop并返回原非空队列的Front
• myStackTop：栈是后进先出，所有返回非空队列的Back
• myStackEmpty：myStack由两个Queue组成，两个Queue都空，myStack也空
• myStackFree：队列由链表实现，要遍历释放

来源：leetcode-225.

题2 用栈实现队列

• 用栈实现队列，有如下问题:- 头插- 获取队头（栈只能获取队尾）
• 从栈和队列的原则入手：- 先进后出- 先进先出
• 把一个栈的元素全部入到另一个，发现逆序了- 逆序后，栈的尾删 StackPop(popST) 就变成 队列头删 了！- 同理，获取队头也就是获取栈顶！尾删 逆序 就是头删****栈顶 逆序 就是栈底

typedefstruct{
    ST pushST;
    ST popST;} MyQueue;

MyQueue*myQueueCreate(){
    MyQueue* obj =(MyQueue*)malloc(sizeof(MyQueue));StackInit(&obj->pushST);StackInit(&obj->popST);return obj;}voidPushST2PopST(MyQueue* obj){if(StackEmpty(&obj->popST)){while(!StackEmpty(&obj->pushST)){StackPush(&obj->popST,StackTop(&obj->pushST));StackPop(&obj->pushST);}}}voidmyQueuePush(MyQueue* obj,int x){StackPush(&obj->pushST, x);}intmyQueuePop(MyQueue* obj){PushST2PopST(obj);int front =StackTop(&obj->popST);StackPop(&obj->popST);return front;}intmyQueuePeek(MyQueue* obj){PushST2PopST(obj);returnStackTop(&obj->popST);}

bool myQueueEmpty(MyQueue* obj){returnStackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);}voidmyQueueFree(MyQueue* obj){free((obj->pushST).arr);free((obj->popST).arr);free(obj);

    obj =NULL;}

• pushST 是专门用来入栈（入队列）的栈，popST是专门用来出栈（出队列）的栈
• 头删：pop 掉 popST 的栈顶- 如果 popST 空了，就到 pushST 取，完全不影响
• 获取队头：直接取 popST 的栈顶- 如果 popST 空了，就到 pushST取，完全不影响
• void PushST2PopST() 就是专门用来传数据的

题3 循环队列

：设计某种数据结构时，要考虑设计的结构方不方便实现需要的接口

• 因为数组头删效率低，所以先前的队列都是用链表实现；但此处的循环队列头删不需要删除元素，只需要 头指针往下走所以，循环队列用数组和链表都可以。那用哪个？
• 得从接口实现的效率和简单程度入手——循环队列的接口：- 出队： - 数组：front往后走- 链表：front往后走- 入队： - 数组：back往后走- 链表：back往后走- 判空： - 数组：…- 链表：…- 判满： - 数组：…- 链表：…不对啊，判空这里出问题了：判满和判空都是 return front == back ？？咋整？- 判空判满 方法1：循环队列结构体内定义size，capacity- 判空判满 方法2：既然判空和判满重合，那我们让 空 和 满 的 front 和 back 不一样不就好了！：多开辟一个空间，结构体内定义一个 N（arr要开辟的元素个数） ，并在初始化接口中 赋值为 k+1- 数组 - - 空：front = back- 满：back + 1 = front- 警惕！如果用这里对下标进行 + 的操作了！很可能越界，所以实现的时候要检查下标合法性- 链表 - - 空：front = back- 满： back->next = front- 获取队头：- 数组：arr[0]- 链表：head->val- 获取队尾- 数组：arr[back - 1]？很可能越界！ arr[ (back - 1 + N) % N ] 才是正解—— - - % N 可以得到 0 ~ N-1 的数- 链表：不好取，除非搞个带头/双向，但这样进一步增加结构的复杂程度-

分析到这里，用数组实现，虽然逻辑结构看起来没链表清晰，但是实际实现起来，还是数组更方便。
方法2：开辟额外空间

typedefstruct{int* arr;int front;//队头int back;//队尾的下一位置int N;} MyCircularQueue;

MyCircularQueue*myCircularQueueCreate(int k){
    MyCircularQueue* obj =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));

    obj->N = k+1;
    obj->arr =(int*)malloc(sizeof(int)* obj->N);
    obj->front = obj->back =0;return obj;}

bool myCircularQueueIsEmpty(MyCircularQueue* obj){if(obj->back == obj->front)return true;elsereturn false;}

bool myCircularQueueIsFull(MyCircularQueue* obj){if((obj->back +1+ obj->N)% obj->N == obj->front)return true;elsereturn false;}

bool myCircularQueueEnQueue(MyCircularQueue* obj,int value){if(myCircularQueueIsFull(obj)){return false;}

    obj->arr[obj->back]= value;
    obj->back++;
    obj->back %= obj->N;return true;}

bool myCircularQueueDeQueue(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj)){return false;}
    obj->front++;
    obj->front %= obj->N;return true;}intmyCircularQueueFront(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj))return-1;return obj->arr[obj->front];}intmyCircularQueueRear(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj))return-1;return obj->arr[(obj->back-1+ obj->N)% obj->N];}voidmyCircularQueueFree(MyCircularQueue* obj){free(obj->arr);
    obj->arr =NULL;free(obj);
    obj =NULL;}

方法1 ：封装size 和 capacity

typedefstruct{int* arr;int front;int back;int size;int capacity;} MyCircularQueue;

MyCircularQueue*myCircularQueueCreate(int k){
    MyCircularQueue* obj =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->arr =(int*)malloc(sizeof(int)*k);
    obj->front = obj->back = obj->size =0;
    obj->capacity = k;return obj;}

bool myCircularQueueIsEmpty(MyCircularQueue* obj){return obj->size ==0;}

bool myCircularQueueIsFull(MyCircularQueue* obj){return obj->size == obj->capacity;}

bool myCircularQueueEnQueue(MyCircularQueue* obj,int value){if(myCircularQueueIsFull(obj))return false;

    obj->arr[obj->back]= value;
    obj->back++;
    obj->back %= obj->capacity;
    obj->size++;return true;}

bool myCircularQueueDeQueue(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj))return false;

    obj->front++;
    obj->front %= obj->capacity;
    obj->size--;return true;}intmyCircularQueueFront(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj))return-1;elsereturn obj->arr[obj->front];}intmyCircularQueueRear(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj))return-1;elsereturn obj->arr[(obj->back -1+ obj->capacity)% obj->capacity];}voidmyCircularQueueFree(MyCircularQueue* obj){free(obj->arr);
    obj->arr =NULL;free(obj);
    obj =NULL;}

本期分享就到这啦，不足之处望请斧正

培根的blog，和你共同进步！