hello！
我是云边有个稻草人
目录
正文开始——
一、用队列实现栈
根据题目要求，我们要用两个队列来实现栈的相关功能，push入栈，top取栈顶元素，pop出栈，empty判空。我们要利用队列的功能操作来实现，所以我们要提前手撕一个队列的代码出来。
下面我们来看一下主要操作实现的思路：
出栈：现在我们有两个队列，找到其一非空队列，将非空队列里面前 size-1个元素导入到另一个队列里面，那么原非空队列中还剩一个元素，将该元素出队列，这样就能实现出栈的操作，符合栈“后进先出”的原则，（遵守队列的规则，实现栈的功能），每进行一次出栈操作之后，都至少有一个队列为空。
//出栈
int myStackPop(MyStack* obj) {
//找到非空队列
Queue* empQ=&obj->q1;
Queue* noneQ=&obj->q2;
if(!QueueEmpty(&obj->q1))
{
empQ=&obj->q2;
noneQ=&obj->q1;
}
//将非空队列里面size-1个数据导入到空队列里面
while(QueueSize(noneQ)>1)
{
int front=QueueFront(noneQ);
QueuePush(empQ,front);
QueuePop(noneQ);
}
//剩下一个栈顶元素
int Pop=QueueFront(noneQ);
QueuePop(noneQ);
return Pop;
}入栈：找不为空的队列入栈。
void myStackPush(MyStack* obj, int x) {
//入栈，往不为空的队列里面插入数据
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}取栈顶元素：找非空队列里面的队尾元素
//找栈顶元素
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);
}完整代码：
先手撕一个队列的完整代码，
再用两个队列来创建一个栈，
对栈进行初始化等各种操作，
最后销毁。
typedef int QDataType;
typedef struct QueueNode{
QDataType data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue{
QueueNode* phead;
QueueNode* ptail;
int size;
}Queue;
//初始化
void QueueInit(Queue* pq)
{
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
//入数据 队尾
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//申请一个新结点
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc file!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
//若队列为空
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
//判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL;
}
//出队列 队头
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
//当队列只有一个元素时，避免ptail成为野指针
if (pq->phead == pq->ptail)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QueueNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
--pq->size;
}
//取队头元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}
//取队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
//队列里有效元素的个数
int QueueSize(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->size;
}
//销毁
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* pcur = pq->phead;
while (pcur)
{
QueueNode* next = pcur->next;
free(pcur);
pcur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
//用两个队列来创建栈
typedef struct {
Queue q1;
Queue q2;
} MyStack;
//初始化栈
MyStack* myStackCreate() {
MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
QueueInit(&pst->q1);
QueueInit(&pst->q2);
return pst;
}
void myStackPush(MyStack* obj, int x) {
//入栈，往不为空的队列里面插入数据
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}
//出栈
int myStackPop(MyStack* obj) {
//找到非空队列
Queue* empQ=&obj->q1;
Queue* noneQ=&obj->q2;
if(!QueueEmpty(&obj->q1))
{
empQ=&obj->q2;
noneQ=&obj->q1;
}
//将非空队列里面size-1个数据导入到空队列里面
while(QueueSize(noneQ)>1)
{
int front=QueueFront(noneQ);
QueuePush(empQ,front);
QueuePop(noneQ);
}
//剩下一个栈顶元素
int Pop=QueueFront(noneQ);
QueuePop(noneQ);
return Pop;
}
//找栈顶元素
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;
}
/**
* 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);
*/二、用栈实现队列
【思路】
【代码】
//创建栈的结构
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;
int capacity; //栈的容量
int top; //栈顶
}Stack;
//初始化
void StackInit(Stack* ps)
{
assert(ps);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
//销毁
void StackDestroy(Stack* ps)
{
assert(ps);
if (ps->arr)
{
free(ps->arr);
}
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
//入数据
void StackPush(Stack* ps, STDataType x)
{
assert(ps);
//判断空间是否充足
if (ps->capacity == ps->top)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc file!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
//此时空间充足,开始入数据
ps->arr[ps->top++] = x;
}
//判空
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top==0;
}
//出数据
void StackPop(Stack* ps)
{
assert(ps);
//此处判空，要想出数据，栈中就必须有数据
assert(!StackEmpty(ps));
//top为栈中有效元素数据个数，指向有效元素的下一个元素，减一，有效数据就少一个
ps->top--;
}
//取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->arr[ps->top - 1];
}
//栈中有效元素的个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
//用两个栈创建队列
typedef struct {
Stack PushST;
Stack PopST;
} MyQueue;
//队列的初始化
MyQueue* myQueueCreate() {
MyQueue* pst=(MyQueue*)malloc(sizeof(MyQueue));
StackInit(&pst->PushST);
StackInit(&pst->PopST);
return pst;
}
//入队列
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->PushST,x);
}
//判断PopST队列是否为空
//1)为空，就先把PushST里面的数据导入到PopST里面，再出PopST里面的栈顶数据
//2)不为空，直接出
int myQueuePop(MyQueue* obj) {
if(StackEmpty(&obj->PopST))
{
//导数据
while(!StackEmpty(&obj->PushST))
{
StackPush(&obj->PopST,StackTop(&obj->PushST));
StackPop(&obj->PushST);
}
}
//取栈顶元素，删除栈顶元素并返回栈顶元素
int top=StackTop(&obj->PopST);
StackPop(&obj->PopST);
return top;
}
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);
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->PushST)&&StackEmpty(&obj->PopST);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->PushST);
StackDestroy(&obj->PopST);
free(obj);
obj=NULL;
}至此结束——
Relaxing Time ！
~ 听首歌放松一下吧 ~
一起来看流星雨
https://t3.kugou.com/song.html?id=63RnxacCQV2我是云边有个稻草人
期待与你的下一次相遇！