1.链接

2.题目再现

3.解法

1.链接

2.题目再现

3.解法

# 一.【Leetcode225】队列实现栈

### 3.解法

1.入栈时就是在不为空的队列插入数据，若两个队列都为空，就随便插入到一个队列中；

2.出栈时将不为空的队列的数据倒入为空的队列中，当不为空的队列就剩一个数据时，就停止向空队列倒数据，然后再删点那最后一个数据；

3.判空时，需要两个队列都为空，才算栈为空；

4.取栈顶元素即取不为空的队列的队尾元素，在取栈顶元素前要判断栈是否为空；

5.销毁栈时，要先销毁其中的两个队列，然后再销毁栈。

``````typedef int Qdatatype;

typedef struct QueueNode
{
struct QueeuNode* next;
Qdatatype data;
}QueueNode;

typedef struct Queue
{
QueueNode* tail;
}Queue;
void Queueinit(Queue* pq)
{
assert(pq);
pq->tail = NULL;
}

void Queuedestroy(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;

while (cur != pq->tail)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}

pq->head = pq->tail = NULL;
}

void Queuepush(Queue* pq, Qdatatype x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));

if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}

void Queuepop(Queue* pq)
{
assert(pq);

QueueNode* next = pq->head->next;
if (pq->head->next == NULL)
{
pq->head = pq->tail = NULL;
}
else
{
}
}

Qdatatype Queuefront(Queue* pq)
{
assert(pq);

}

Qdatatype Queueback(Queue* pq)
{
assert(pq);
assert(Queuesize(pq) > 0);

return pq->tail->data;
}

int Queuesize(Queue* pq)
{
assert(pq);
int size = 0;
QueueNode* cur = pq->head;
while (cur != pq->tail->next)
{
size++;
cur = cur->next;
}

return size;
}

bool Queueempty(Queue* pq)
{
assert(pq);

return pq->head == NULL;
}

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

MyStack* myStackCreate() {
MyStack*obj=(MyStack*)malloc(sizeof(MyStack));
if(obj==NULL)
exit(-1);
Queueinit(&obj->q1);
Queueinit(&obj->q2);

return obj;
}

void myStackPush(MyStack* obj, int x)
{
if(!Queueempty(&obj->q1))
{
Queuepush(&obj->q1,x);
}
else
{
Queuepush(&obj->q2,x);
}
}

int myStackPop(MyStack* obj) {
Queue*empty=&obj->q1;
Queue*noempty=&obj->q2;
if(!Queueempty(&obj->q1))
{
empty=&obj->q2;
noempty=&obj->q1;
}
while(Queuesize(noempty)>1)
{
Queuepush(empty,Queuefront(noempty));
Queuepop(noempty);
}
int front=Queuefront(noempty);
Queuepop(noempty);
return front;
}

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

# 二.【Leetcode232】栈实现队列

### 3.解法

1.判空时，需要两个栈都为空，队列才为空；

2.返回队头数据时，和出数据的操作类似，只是不需要删除队头的数据，还有在之前要判断队列是否为空；

3.销毁队列前，要先销毁两个栈。

``````#define MR_CAP 5
typedef int STdatatype;

typedef struct Stack
{
STdatatype* arr;
int top;
int capacity;
}ST;

void Stackinit(ST* ps)
{
assert(ps);

ps->arr = (STdatatype*)malloc(MR_CAP * sizeof(STdatatype));
if (ps->arr == NULL)
{
perror("Stackinit malloc");
exit(-1);
}

ps->top = 0;
ps->capacity = MR_CAP;
}

void Stackdestroy(ST* ps)
{
assert(ps);

free(ps->arr);
ps->arr = NULL;
ps->top = 0;
ps->capacity = 0;
}

void Stackpush(ST* ps, STdatatype x)
{
assert(ps);

if (ps->top == ps->capacity)
{
STdatatype* tmp = (STdatatype*)realloc(ps->arr, ps->capacity * 2 * sizeof(STdatatype));
if (tmp == NULL)
{
perror("Stackpush realloc");
exit(-1);
}
else
{
ps->arr = tmp;
ps->capacity *= 2;
}
}

ps->arr[ps->top] = x;
ps->top++;
}

void Stackpop(ST* ps)
{
assert(ps);
assert(ps->top > 0);

ps->top--;
}

STdatatype Stacktop(ST* ps)
{
assert(ps);

return ps->arr[ps->top - 1];
}

int Stacksize(ST* ps)
{
assert(ps);

return ps->top;

}

bool Stackempty(ST* ps)
{
assert(ps);

if (ps->top == 0)
{
return true;
}
else
return false;

}

typedef struct {
ST Pushst;
ST Popst;
} MyQueue;

MyQueue* myQueueCreate() {
MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
if(obj==NULL)
exit(-1);
Stackinit(&obj->Pushst);
Stackinit(&obj->Popst);

return obj;
}

void myQueuePush(MyQueue* obj, int x) {
Stackpush(&obj->Pushst,x);
}

int myQueuePeek(MyQueue* obj) {
if(Stackempty(&obj->Popst))
{
while(!Stackempty(&obj->Pushst))
{
Stackpush(&obj->Popst,Stacktop(&obj->Pushst));
Stackpop(&obj->Pushst);
}
}

return Stacktop(&obj->Popst);

}

int myQueuePop(MyQueue* obj) {

int front=myQueuePeek(obj);
Stackpop(&obj->Popst);
return front;
}

bool myQueueEmpty(MyQueue* obj) {

return Stackempty(&obj->Pushst)&&Stackempty(&obj->Popst);
}

void myQueueFree(MyQueue* obj) {
Stackdestroy(&obj->Pushst);
Stackdestroy(&obj->Popst);

free(obj);
}
``````

🐲👻这两道题的讲解就到这里了，若有错误或是建议欢迎小伙伴们指出。🐯🤖

🥰🤩希望小伙伴们可以多多支持博主哦。😍😃

😁😄谢谢你的阅读。😼😸

THE END

)">