【算法集训】基础数据结构：六、栈和队列

做这几天的数据结构的题目的时候有很多函数需要填写，这里需要有一个大致的顺序，一般是先补全结构体，也就是创建队列 | 栈；
而后初始化，设置初值create（）函数，再然后C语言需要释放，补全释放函数也就是free；
这下可以根据题目要求进行操作了，一般情况下模拟操作自己是可以做出来的，但是像我第一次看到这个题目肯定是一脸懵逼，只有看了视频才知道。
数据结构我感觉就是孰能生巧的东西，不像算法变化很多，还是要多敲代码记住就可以了。

第一题 面试题 03.04. 化栈为队

第一种：这里初始化顶部为0，所以要访问顶部的话需要-1再进行访问。

// 题目要求两个栈,这里用数组创建两个栈
typedef struct {
    int stackin[30000], topin;
    int stackout[30000], topout;
} MyQueue;

/** Initialize your data structure here. */
//创建"队列",初始化
MyQueue* myQueueCreate() {
    MyQueue * obj = (MyQueue *)malloc(sizeof(MyQueue));
    obj->topin = 0;
    obj->topout = 0;
    return obj;
}

/** 往队列中加入元素. */
void myQueuePush(MyQueue* obj, int x) {
    obj->stackin[obj->topin++] = x;
}

/** 移除队列的头部 */
int myQueuePop(MyQueue* obj) {
    if(obj->topout == 0) {
        while(obj->topin) {
            obj->stackout[obj->topout++] = obj->stackin[--obj->topin];
        }
    }
    return obj->stackout[--obj->topout];
}

/** 获取队列的头部(不删除). */
int myQueuePeek(MyQueue* obj) {
    if(obj->topout == 0) {
        while(obj->topin) {
            obj->stackout[obj->topout++] = obj->stackin[--obj->topin];
        }
    }
    return obj->stackout[obj->topout - 1];
}

/** 判断队列是否为空. */
bool myQueueEmpty(MyQueue* obj) {
    return obj->topin + obj->topout == 0;
}
// 释放队列
void myQueueFree(MyQueue* obj) {
    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

第二种：这里初始化顶部为1

typedef struct {
    int stackin[30000], topin;
    int stackout[30000], topout;
} MyQueue;

/** Initialize your data structure here. */

MyQueue* myQueueCreate() {
    MyQueue * obj = (MyQueue *)malloc(sizeof(MyQueue));
    obj->topin = -1;
    obj->topout = -1;
    return obj;
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
    obj->stackin[++obj->topin] = x;
}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
    if(obj->topout == -1) {
        while(obj->topin != -1) {
            obj->stackout[++obj->topout] = obj->stackin[obj->topin--];
        }
    }
    return obj->stackout[obj->topout--];
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
    if(obj->topout == -1) {
        while(obj->topin != -1) {
            obj->stackout[++obj->topout] = obj->stackin[obj->topin--];
        }
    }
    return obj->stackout[obj->topout];
}

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
    return obj->topin + obj->topout == -2;
}

void myQueueFree(MyQueue* obj) {
    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

第二题 LCR 125. 图书整理 II

这里删除图书那里，和上一题不一样，上一题保证没有空的，但这一题是有空的，这里需要进行一个判断，如果两个栈都为空则返回-1；

typedef struct {
    int stackin[10001], topin;
    int stackout[10001], topout;
} CQueue;


CQueue* cQueueCreate() {
    CQueue * obj = (CQueue *)malloc(sizeof(CQueue));
    obj->topin = 0;
    obj->topout = 0;
    return obj;
}

void cQueueAppendTail(CQueue* obj, int value) {
    obj->stackin[obj->topin++] = value;
}

int cQueueDeleteHead(CQueue* obj) {
    if(obj->topout == 0) {
        while(obj->topin) {
            obj->stackout[obj->topout++] = obj->stackin[--obj->topin];
        }
    }
    if(obj->topout == 0) {
        return -1;
    }else {
        return obj->stackout[--obj->topout];
    }
    
}

void cQueueFree(CQueue* obj) {
    free(obj);
}

/**
 * Your CQueue struct will be instantiated and called as such:
 * CQueue* obj = cQueueCreate();
 * cQueueAppendTail(obj, value);
 
 * int param_2 = cQueueDeleteHead(obj);
 
 * cQueueFree(obj);
*/

第三题 232. 用栈实现队列

typedef struct {
    int stackin[101], topin;
    int stackout[101], topout;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue * obj = (MyQueue *)malloc(sizeof(MyQueue));
    obj->topin = -1;
    obj->topout = -1;
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    obj->stackin[++obj->topin] = x;
}

int myQueuePop(MyQueue* obj) {
    if(obj->topout == -1) {
        while(obj->topin != -1) {
            obj->stackout[++obj->topout] = obj->stackin[obj->topin--];
        }
    }
    return obj->stackout[obj->topout--];
}

int myQueuePeek(MyQueue* obj) {
    if(obj->topout == -1) {
        while(obj->topin != -1) {
            obj->stackout[++obj->topout] = obj->stackin[obj->topin--];
        }
    }
    return obj->stackout[obj->topout];
}

bool myQueueEmpty(MyQueue* obj) {
    return obj->topin + obj->topout == -2;
}

void myQueueFree(MyQueue* obj) {
    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

第四题 225. 用队列实现栈

// 创建队列
typedef struct {
    int head;
    int tail;
    int data[100001];
} MyQueue;

void myQueueInit(MyQueue * obj) {
    obj->head = 0;
    obj->tail = -1;
}

void myQueuePush(MyQueue * obj, int x) {
    obj->data[++obj->tail] = x;
}

int myQueuePop(MyQueue * obj) {
    return obj->data[obj->head++];
}

int myQueueTop(MyQueue * obj) {
    return obj->data[obj->head];
}

int myQueueSize(MyQueue * obj) {
    return obj->tail - obj->head + 1;
}


typedef struct {
    MyQueue q[2];
    int pushIdx;
} MyStack;


MyStack* myStackCreate() {
    MyStack * obj = (MyStack *)malloc( sizeof(MyStack) );
    for(int i = 0; i < 2; i++) {
        myQueueInit( &obj->q[i]);
    }
    obj->pushIdx = 0;
    return obj;
}

void myStackPush(MyStack* obj, int x) {
    MyQueue * q = &(obj->q[obj->pushIdx]);
    myQueuePush( q, x);
}

int myStackPop(MyStack* obj) {
    MyQueue * pushq = &(obj->q[obj->pushIdx]);
    MyQueue * emptyq = &(obj->q[1 - obj->pushIdx]);
    while( myQueueSize(pushq) > 1 ) {
        myQueuePush(emptyq, myQueuePop(pushq));
    }
    int ret = myQueuePop(pushq);
    obj->pushIdx = 1 - obj->pushIdx;
    return ret;
}

int myStackTop(MyStack* obj) {
    MyQueue * pushq = &(obj->q[obj->pushIdx]);
    MyQueue * emptyq = &(obj->q[1 - obj->pushIdx]);
    while( myQueueSize(pushq) > 1 ) {
        myQueuePush(emptyq, myQueuePop(pushq));
    }
    int ret = myQueuePop(pushq); 
    myQueuePush(emptyq, ret);
    obj->pushIdx = 1 - obj->pushIdx;
    return ret;
}

bool myStackEmpty(MyStack* obj) {
    return myQueueSize(&(obj->q[obj->pushIdx]))  == 0;
}

void myStackFree(MyStack* obj) {
    free(obj);
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/