【LeetCode】用队列实现栈和用栈实现队列（C语言）-创新互联
目录
我们提供的服务有：成都网站设计、成都网站建设、微信公众号开发、网站优化、网站认证、海城ssl等。为上1000家企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务，是有科学管理、有技术的海城网站制作公司
1.用队列实现栈
增删
求栈顶元素
判断栈为空
2.用栈实现队列
增删
返回队列开头的数据
判断队列为空
尾言
源码
队列实现栈
栈实现队列
1.用队列实现栈刚讲完栈和队列，LeetCode上有两题栈与队列的互相实现，简单地讲讲思路和实现吧。
原题地址：225.用队列实现栈
题目要求我们用两个队列来实现一个栈，我们知道队列的性质是先进先出，而栈是后进先出，假设随便给我们要的这个栈之中添加几个数，便能画出这样的图
那这样接下来若要出栈，输出的便是 5 ，但是队列出队的话只能输出 1 。所以我们就要用到另一个队列，把队列1最后一个数前面的数据导入到队列2之后再输出队列1的唯一数。这样就完成了出栈的模拟。
之后把队列1第一个数据删除，一定保证一个队列为空 ，即第二次出栈还是要把非空的队列的数据导入空队列里去。
求栈顶元素若是要入栈操作的话就是直接再非空队列队尾插入数据就可以了，最后面的值不会被导入到另一队列里。所以下次出栈就会将其输出。
找栈顶元素其实与出栈的唯一不同就是，出栈要删除栈顶元素，而求栈顶元素不一样，其要求要有返回值。偷懒的话可以先写求栈顶元素，之后出栈只要复用函数就可以完成了。
前面讲过，必定有一个队列为空，因此不能只检查一个队列而是两个队列都要检查，即两个队列都为空则证明栈为空。
原题地址：232.用栈实现队列
增删其实只要熟悉了队列和栈的基本性质，其实这两题也并不会很难，思路正确了剩下的就只需要注意编写程序时的小细节就可以了。
仔细分析题目，要求用两个栈实现一个队列，既然题目都这样要求了只用一个栈明显是不可能的，上一题的经验告诉我，要把数据导入到另一个栈里。
把数据导到另一个栈后我们惊奇的发现，数据恰好就成了我们想要的样子。这段数据就可以直接输出了。
这下我们就可以让一个栈专门承载输入数据，另一个栈专门输出数据，输出栈为空时再从输入栈把数据导入到输出栈里面。
也是跟删除是一个道理，不过只是返回值并不删除数据。即输出栈没有值就导入输入栈的值进去就可以了。
两个栈如果都为空，队列就为空，只有其中一个栈为空是不算的。
好了，这样今天我们两道题的思路与实现到这里就讲完了，说实在的用C语言写确实是麻烦了一点，但是之前写过栈和队列的话直接把代码复制过去，之后用自己之前写的函数写就可以了。有问题的话一定私信或者评论区指出，一定第一时间回复！！！
源码 队列实现栈typedef int Qdatatype;
typedef struct Qnode
{
Qdatatype data;
struct Queue* next;
}Qnode;
typedef struct Queue
{
Qnode* head;
Qnode* tail;
int size;
}Queue;
void Queueinit(Queue* p)
{
p->head = NULL;
p->tail = NULL;
p->size = 0;
}
bool QueueEmpty(Queue* p)
{
assert(p);
return p->head == NULL || p->tail == NULL;
}
void Queuepush(Queue* p, Qdatatype x)
{
assert(p);
Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
if (newnode == NULL)
{
perror(malloc);
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (p->head == NULL)
{
p->head = p->tail = newnode;
p->size++;
}
else
{
p->tail->next = newnode;
p->tail = newnode;
p->size++;
}
}
void Queuepop(Queue* p)
{
assert(p);
assert(!QueueEmpty(p));
Qnode* next = p->head->next;
free(p->head);
p->head = next;
p->size--;
}
Qdatatype Queuefront(Queue* p)
{
assert(p);
return p->head->data;
}
void QueueDestroy(Queue* p)
{
assert(p);
Qnode* cur = p->head;
while (cur)
{
Qnode* next = cur->next;
free(cur);
cur = next;
}
p->head = p->tail = NULL;
p->size = 0;
}
Qdatatype Queueback(Queue* p)
{
assert(p);
assert(!QueueEmpty(p));
return p->tail->data;
}
int Queuesize(Queue* p)
{
assert(p);
return p->size;
}
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* stack = (MyStack*)malloc(sizeof(MyStack)); //开辟栈的空间，动态开辟才不是局部变量
Queueinit(&stack->q1); //两个队列的初始化
Queueinit(&stack->q2);
return stack;
}
void myStackPush(MyStack* obj, int x) {
assert(obj);
if (!QueueEmpty(&obj->q1)) //在非空队列里插入数据，两个都为空则默认插入在第一个里面
{
return Queuepush(&obj->q1, x);
}
else
{
return Queuepush(&obj->q2, x);
}
}
int myStackPop(MyStack* obj) {
assert(obj);
Queue* emptyqueue = &obj->q1; //一定有一个空队列
Queue* queue = &obj->q2; //一个是有数据的队列
if (QueueEmpty(&obj->q2)) //判断为空的队列
{
emptyqueue = &obj->q2;
queue = &obj->q1;
}
while (Queuesize(queue) >1)
{
Queuepush(emptyqueue, Queuefront(queue)); //导入后删除原队列里的数据
Queuepop(queue);
}
int ret = Queuefront(queue);
Queuepop(queue);
return ret;
}
int myStackTop(MyStack* obj) {
assert(obj);
if (!QueueEmpty(&obj->q1))
{
return Queueback(&obj->q1);
}
else
{
return Queueback(&obj->q2);
}
}
bool myStackEmpty(MyStack* obj) {
assert(obj);
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}typedef int STdatatype;
typedef struct Stack
{
STdatatype* data;
int top;
int capacity;
}Stack;
void checkcapacity(Stack* p)
{
STdatatype* newp;
if (p->top == p->capacity)
{
newp = (STdatatype*)realloc(p->data, sizeof(Stack) * p->capacity * 2);
if (newp == NULL)
{
perror(realloc);
exit(-1);
}
p->data = newp;
p->capacity *= 2;
}
if (p == NULL)
{
perror(realloc);
exit(-1);
}
}
void StackInit(Stack* p)
{
STdatatype* np = (STdatatype*)malloc(sizeof(STdatatype) * 4);
if (np)
{
p->data = np;
}
p->top = 0;
p->capacity = 4;
}
void StackPush(Stack* p, STdatatype x)
{
assert(p);
checkcapacity(p);
(p->data)[p->top] = x;
p->top++;
}
void Stackprint(Stack* p)
{
int i = p->top - 1;
while (i >= 0)
{
printf("%d ", (p->data)[i--]);
}
printf("\n");
}
void StackPop(Stack* p)
{
assert(p);
assert(p->top);
p->top--;
}
STdatatype StackTop(Stack* p)
{
assert(p);
int top = p->top - 1;
return (p->data)[top];
}
int StackEmpty(Stack* p)
{
assert(p);
if (p->top != 0)
{
return 0;
}
return 1;
}
void StackDestroy(Stack* p)
{
assert(p);
assert(p->data);
free(p->data);
p->data = NULL;
p->top = 0;
p->capacity = 0;
}
typedef struct //两个队列一个输出一个输入，输出栈里没数据了之后就从输入里面倒数据过去
{
Stack S; //输入
Stack nullS; //输出
} MyQueue;
bool myQueueEmpty(MyQueue* obj);
int myQueuePeek(MyQueue* obj);
MyQueue* myQueueCreate() //创建队列
{
MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue)); //开辟队列空间
StackInit(&queue->S); //对两个栈初始化
StackInit(&queue->nullS);
return queue; //返回开辟的队列
}
void myQueuePush(MyQueue* obj, int x) {
assert(obj);
StackPush(&obj->S, x); //直接在插入的队列里插入数据
}
int myQueuePop(MyQueue* obj) {
assert(obj);
assert(!myQueueEmpty(obj)); //判断队列不为空
int ret = myQueuePeek(obj); //取最上面的值返回
StackPop(&obj->nullS); //pop在peek的基础上增加数据的删除
return ret;
}
int myQueuePeek(MyQueue* obj) { //拿最前面的数据
assert(obj);
assert(!myQueueEmpty(obj)); //队列不为空
if (StackEmpty(&obj->nullS)) //输出栈为空则倒入数据
{
while (!StackEmpty(&obj->S)) //直到输入栈为空，必定一个栈为空
{
StackPush(&obj->nullS, StackTop(&obj->S)); //取输入栈最上面导入到输出栈的最下面
StackPop(&obj->S); //清除输入栈的数据
}
}
return StackTop(&obj->nullS); //返回最上面的值
}
bool myQueueEmpty(MyQueue* obj) {
assert(obj);
return StackEmpty(&obj->nullS) && StackEmpty(&obj->S); //两个栈都为空则队列为空
}
void myQueueFree(MyQueue* obj) {
assert(obj);
StackDestroy(&obj->nullS); //销毁两个栈
StackDestroy(&obj->S);
free(obj); //销毁队列
}你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网页名称：【LeetCode】用队列实现栈和用栈实现队列（C语言）-创新互联
网站路径：http://6mz.cn/article/dicoph.html