(力扣)用两个队列实现栈---C语言

分享一首歌曲吧，希望在枯燥的刷题生活中带给你希望和勇气，加油！

  

题目：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

题解： 

首先自己实现一个队列粘贴复制过去：

注意：这道题目队列的实现方法不同不会影响题目，只要是个队列，先进先出，那么不管你是双向还是结构不同，都不会影响题目的实现。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int DataType;
typedef struct Queue
{DataType data;struct Queue *next;
}Queue;typedef struct Q
{Queue* head;Queue* tail;int size;
}Q;void Init(Q *qq);
void Destroy(Q* qq);
void QueuePush(Q* qq, DataType x);
void QueuePop(Q* qq);
DataType GetQueueFrontNum(Q* qq);
DataType GetQueueBackNum(Q* qq);
bool Empty(Q* qq);
int Size(Q* qq);void Init(Q* qq)
{assert(qq);qq->head = NULL;qq->tail = NULL;qq->size = 0;
}void QueuePush(Q* qq, DataType x)
{assert(qq);Queue* temp = (Queue*)malloc(sizeof(Queue));if (temp == NULL){perror("malloc fail");exit(-1);}temp->data = x;temp->next = NULL;if (qq->tail == NULL)qq->head = qq->tail = temp;else{qq->tail->next = temp;qq->tail = temp;}qq->size++;
}void QueuePop(Q* qq)
{assert(qq);assert(!Empty(qq));if (qq->head == qq->tail){free(qq->head);qq->head = qq->tail = NULL;}else{Queue* next = qq->head->next;free(qq->head);qq->head = next;}qq->size--;
}DataType GetQueueFrontNum(Q* qq)
{assert(qq);assert(!Empty(qq));return qq->head->data;
}DataType GetQueueBackNum(Q* qq)
{assert(qq);assert(!Empty(qq));return qq->tail->data;
}bool Empty(Q* qq)
{assert(qq);return qq->size == 0;
}void Destroy(Q* qq)
{assert(qq);Queue *cur = qq->head;while(cur){Queue *next = cur->next;free(cur);cur = next;}qq->head = qq->tail = NULL;qq->size = 0;
}int Size(Q* qq)
{assert(qq);return qq->size;
}

剩下的就是题目接口：

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

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

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

int myStackPop(MyStack* obj) 
{Q *empty = &obj->q1;Q *obempty = &obj->q2;if(!Empty(&obj->q1)){empty = &obj->q2;obempty = &obj->q1;}int sz = Size(obempty) - 1;for(int i=0; i<sz; i++){QueuePush(empty,GetQueueFrontNum(obempty));QueuePop(obempty);}int num = GetQueueFrontNum(obempty);QueuePop(obempty);return num;
}

int myStackTop(MyStack* obj) 
{if(!Empty(&obj->q1)){return GetQueueBackNum(&obj->q1);}else{return GetQueueBackNum(&obj->q2);}   
}

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

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