(力扣)用两个栈实现队列

 这里是栈的源代码：栈和队列的实现

当然，自己也可以写一个栈来用，对题目来说不影响，只要符合栈的特点就行。

题目：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

题解： 

做题前需要的栈：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int DataType;
typedef struct Stack
{DataType* data;int top;int capacity;
}Stack;void Init(Stack *st);
void Push(Stack* st, DataType x);
void Pop(Stack* st);
DataType GetTop(Stack* st);
bool Empty(Stack* st);
void Destroy(Stack* st);
int Size(Stack* st);void Init(Stack* st)
{assert(st);st->data = NULL;st->top = 0;st->capacity = 0;
}void Push(Stack* st, DataType x)
{assert(st);if (st->capacity == st->top){int newcapacity = (st->capacity == 0) ? 4 : st->capacity * 2;DataType* temp = (DataType*)realloc(st->data, sizeof(DataType) * newcapacity);if (temp == NULL){perror("realloc fail");exit(-1);}st->data = temp;st->capacity = newcapacity;}st->data[st->top++] = x;
}void Pop(Stack* st)
{assert(st);assert(st->top > 0);st->top--;
}DataType GetTop(Stack* st)
{assert(st);assert(st->top > 0);return st->data[st->top - 1];
}bool Empty(Stack* st)
{assert(st);return (st->top == 0);
}void Destroy(Stack* st)
{assert(st);free(st->data);st->data = NULL;st->top = st->capacity = 0;}int Size(Stack* st)
{assert(st);return st->top;
}

---

---

 

题目正题：  

---

​
//定义出两个栈
typedef struct 
{Stack push;Stack pop;
} MyQueue;​

---

//初始化队列
MyQueue* myQueueCreate() 
{MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));Init(&obj->push);Init(&obj->pop);return obj;
}

---

//向队列中插入元素
void myQueuePush(MyQueue* obj, int x) 
{Push(&obj->push,x);
}

---

//元素出队列
int myQueuePop(MyQueue* obj) 
{int ret = myQueuePeek(obj);Pop(&obj->pop);return ret;
}

---

//返回队列开头的元素
int myQueuePeek(MyQueue* obj) 
{if(Empty(&obj->pop)){int size = Size(&obj->push);for(int i=0; i<size; i++){Push(&obj->pop,GetTop(&obj->push));Pop(&obj->push);}}return GetTop(&obj->pop);
}

---

//判断队列是否为空
bool myQueueEmpty(MyQueue* obj) 
{return Empty(&obj->pop) && Empty(&obj->push);
}

---

//销毁队列
void myQueueFree(MyQueue* obj) 
{free((&obj->push)->data);free((&obj->pop)->data);free(obj);
}

---

Lei宝啊：我的主页鸭

愿所有美好如期而遇