栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。 出栈:栈的删除操作叫做出栈。出数据也在栈顶。
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 的原则
入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头
通过上述的介绍,栈与队列仿佛毫不相干,一个先入先出,一个后入后出。 栈像一个容器来装物品,队列像排队买饭。这两个事情看起来毫不相干,那么如何实现栈与队列的相互转换呢。下面我们来看两道OJ题,来进行具体解决。
我们来看题目描述
这道题给了我们六个接口,接下来我们来逐一完成。
首先先把队列的代码拷贝到代码区,方便我们使用队列中的对应接口。、
首先,我们来分析一下怎样通过队列来模拟栈
我们看,我们模拟一下发现,删除操作只需要将一个队列的前n个数据迁移到另一个队列就可以,那我们不妨就假设看看两个队列能否实现栈。
typedef struct {
Queue q1;
Queue q2;
} MyStack;
非常简单的我们初始化一下
MyStack* myStackCreate() {
MyStack* st = (MyStack*)malloc(sizeof(MyStack));
QueueInit(st->q1);
QueueInit(st->q2);
return st;
}
void myStackPush(MyStack* obj, int x) {
Queue* emptyQueue = &obj->q1;
Queue* unemptyQueue = &obj->q2;
if (!QueueEmpty(emptyQueue)) {
emptyQueue = &obj->q2;
unemptyQueue = &obj->q1;
}
QueuePush(unemptyQueue, x);
}
使用假设法来判断两个队列的空与非空,选择非空进行插入。
int myStackPop(MyStack* obj) {
Queue* emptyQueue = &obj->q1;
Queue* unemptyQueue = &obj->q2;
if (!QueueEmpty(emptyQueue)) {
emptyQueue = &obj->q2;
unemptyQueue = &obj->q1;
}
while (QueueSize(unemptyQueue) > 1) {
QueuePush(emptyQueue, unemptyQueue->front->data);
QueuePop(unemptyQueue);
}
int ret = QueueFront(unemptyQueue);
QueuePop(unemptyQueue);
return ret;
}
依然是通过假设法来判断是否非空,然后依次将非空队列的前n-1个元素移动到空队列,这里的移动不是将节点的移动,而是将值赋给空队列。最后取栈顶 返回值,再出栈一下非空队列,完成操作。
int myStackTop(MyStack* obj) {
if (!QueueEmpty(&obj->q1)) {
return QueueBack(&obj->q1);
}
else {
return QueueBack(&obj->q2);
}
}
选择判断是否为非空进行取队列顶操作即可。
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
都为空才为空
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
obj = NULL;
}
一步一步free掉即可。
我将源码放在下面,原理与上述相似,请自行观看。
typedef struct {
Stack st1;
Stack st2;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&pq->st1);
StackInit(&pq->st2);
return pq;
}
void myQueuePush(MyQueue* obj, int x) {
if(!StackEmpty(&obj->st1)){
StackPush(&obj->st1,x);
}
else{
StackPush(&obj->st2,x);
}
}
int myQueuePop(MyQueue* obj) {
//判断 空与非空
Stack* empty_st = &obj->st1;
Stack* nonempty_st = &obj->st2;
if(!StackEmpty(&obj->st1)){
empty_st = &obj->st2;
nonempty_st = &obj->st1;
}
//转移元素
while(StackSize(nonempty_st)>1){
StackPush(empty_st,StackTop(nonempty_st));
StackPop(nonempty_st);
}
int del = StackTop(nonempty_st);
StackPop(nonempty_st);
while(!StackEmpty(empty_st)){
StackPush(nonempty_st,StackTop(empty_st));
StackPop(empty_st);
}
return del;
}
int myQueuePeek(MyQueue* obj) {
//判断 空与非空
Stack* empty_st = &obj->st1;
Stack* nonempty_st = &obj->st2;
if(!StackEmpty(&obj->st1)){
empty_st = &obj->st2;
nonempty_st = &obj->st1;
}
while(StackSize(nonempty_st)>1){
StackPush(empty_st,StackTop(nonempty_st));
StackPop(nonempty_st);
}
int ret = StackTop(nonempty_st);
while(!StackEmpty(empty_st)){
StackPush(nonempty_st,StackTop(empty_st));
StackPop(empty_st);
}
return ret;
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->st1) && StackEmpty(&obj->st2);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->st1);
StackDestroy(&obj->st2);
free(obj);
}