232. 用栈实现队列
解
typedef struct {
int intop, outtop;
int instack[105], outstack[105];
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue *queue = (MyQueue *)malloc(sizeof(MyQueue));
queue->intop = queue->outtop = -1;
memset(queue->instack, -1, sizeof(int) * 105);
memset(queue->outstack, -1, sizeof(int) * 105);
return queue;
}
void myQueuePush(MyQueue* obj, int x) {
while (obj->outtop >= 0) {
obj->instack[++obj->intop] = obj->outstack[obj->outtop--];
}
obj->instack[++obj->intop] = x;
}
int myQueuePop(MyQueue* obj) {
while (obj->intop >= 0) {
obj->outstack[++obj->outtop] = obj->instack[obj->intop--];
}
return obj->outstack[obj->outtop--];
}
int myQueuePeek(MyQueue* obj) {
while (obj->intop >= 0) {
obj->outstack[++obj->outtop] = obj->instack[obj->intop--];
}
return obj->outstack[obj->outtop];
}
bool myQueueEmpty(MyQueue* obj) {
while (obj->intop >= 0) {
obj->outstack[++obj->outtop] = obj->instack[obj->intop--];
}
if (obj->outtop < 0) {
return true;
}
return false;
}
void myQueueFree(MyQueue* obj) {
free(obj);
}
225. 用队列实现栈
题目链接
解
用环形队列实现
const int max = 105;
typedef struct {
int front1, back1;
int front2, back2;
int queue1[105], queue2[105];
} MyStack;
MyStack* myStackCreate() {
MyStack *stack = (MyStack *)malloc(sizeof(MyStack));
memset(stack->queue1, -1, sizeof(int) * max);
stack->front1 = stack->back1 = 0;
memset(stack->queue2, -1, sizeof(int) * max);
stack->front2 = stack->back2 = 0;
return stack;
}
void myStackPush(MyStack* obj, int x) {
obj->queue1[obj->front1] = x;
obj->front1 = (obj->front1 + 1) % max;
return;
}
int myStackPop(MyStack* obj) {
int ret;
while (obj->back1 != obj->front1-1) {
obj->queue2[obj->front2] = obj->queue1[obj->back1];
obj->front2 = (obj->front2 + 1) % max;
obj->back1 = (obj->back1 + 1) % max;
}
ret = obj->queue1[obj->back1];
obj->back1 = (obj->back1 + 1) % max;
while (obj->back2 != obj->front2) {
obj->queue1[obj->front1] = obj->queue2[obj->back2];
obj->front1 = (obj->front1 + 1) % max;
obj->back2 = (obj->back2 + 1) % max;
}
return ret;
}
int myStackTop(MyStack* obj) {
int ret;
while (obj->back1 != obj->front1-1) {
obj->queue2[obj->front2] = obj->queue1[obj->back1];
obj->front2 = (obj->front2 + 1) % max;
obj->back1 = (obj->back1 + 1) % max;
}
ret = obj->queue1[obj->back1];
obj->queue2[obj->front2] = obj->queue1[obj->back1];
obj->front2 = (obj->front2 + 1) % max;
obj->back1 = (obj->back1 + 1) % max;
while (obj->back2 != obj->front2) {
obj->queue1[obj->front1] = obj->queue2[obj->back2];
obj->front1 = (obj->front1 + 1) % max;
obj->back2 = (obj->back2 + 1) % max;
}
return ret;
}
bool myStackEmpty(MyStack* obj) {
if (obj->front1 == obj->back1) {
return true;
}
return false;
}
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);
*/