# 【栈与队列】栈与队列的相互转换OJ题

## 1 栈与队列

### 1.1 栈

：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

## 2 栈与队列的相互转换

### 2.1 队列模拟实现栈

#### 2.1.1 栈的结构体设置

typedef struct {
Queue q1;
Queue q2;
} MyStack;

#### 2.1.2 初始化接口

MyStack* myStackCreate() {
MyStack* st = (MyStack*)malloc(sizeof(MyStack));
QueueInit(st->q1);
QueueInit(st->q2);
return st

#### 2.1.3 压栈操作

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);
}


#### 2.1.4 出栈

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;
}

#### 2.1.5 取栈顶

int myStackTop(MyStack* obj) {

if (!QueueEmpty(&obj->q1)) {
return QueueBack(&obj->q1);
}
else {
return QueueBack(&obj->q2);
}

}

#### 2.1.6 判断是否为空

bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

#### 2.1.7 销毁栈

void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
obj = NULL;
}

### 2.2 栈模拟实现队列

#### 2.2.1 版本一

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);
}

## Thanks♪(･ω･)ﾉ

|
4天前
|

【数据结构OJ题】设计循环队列

14 1
|
4天前
【数据结构OJ题】有效的括号

10 1
|
4天前
|

【数据结构】栈和队列

10 1
|
5天前
【数据结构OJ题】复制带随机指针的链表

12 1
|
4天前
【数据结构OJ题】用栈实现队列

11 0
|
4天前
【数据结构OJ题】用队列实现栈

15 0
|
28天前
|

【数据结构与算法 经典例题】使用栈实现队列（图文详解）
【数据结构与算法 经典例题】使用栈实现队列（图文详解）
34 0
|
22天前
|

26 2
|
28天前
|

【数据结构】操作受限的线性表，栈的具体实现
【数据结构】操作受限的线性表，栈的具体实现
30 5
|
28天前
|

【数据结构与算法 经典例题】使用队列实现栈（图文详解）
【数据结构与算法 经典例题】使用队列实现栈（图文详解）
27 1