文章目录
- 一.什么是栈
- 二.什么是队列
- 三.怎么把栈变成队列（力扣）
- 四.怎么把队列变成栈（力扣）
- 总结
一.什么是栈
栈（stack）又名堆栈，它是一种运算受限的线性表。限定权在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
其实只要注意栈的一个特点就是后进先出
二.什么是队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
其实也是只有注意一点就是队列的特点就是先进先出
接下来我们只要是要解决队列是栈之间的转化，怎么把队列变成栈，怎么把栈变成队列
三.怎么把栈变成队列（力扣）
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（
push、pop、peek、empty）：实现
MyQueue类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false说明：
- 你 只能 使用标准的栈操作 —— 也就是只有
push to top,peek/pop from top,size, 和is empty操作是合法的。- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
思路：设置两个站一个入数据，一个出数据，设置两个站一个入数据，一个出数据
3.1初始化
typedef struct {
stack PushST;
stack PopST;
} MyQueue;3.2创建
开辟两个栈的空间
MyQueue* myQueueCreate() {
MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
stackInit(&q->PushST);
stackInit(&q->PopST);
return p;
}3.3插入 void push(int x) 将元素 x 推到队列的末尾
如果要插元素，就放入push这个栈里
void myQueuePush(MyQueue* obj, int x) {
assert(obj);
stack Push(&obj->PushST, x);
}3.4删除 从队列的开头移除并返回元素
因为是队列，要满足先入先出，所以先判断Pop栈里还有没有数据，如果没有，就把push里的数据放过来，放一个就把Push栈里的数据删一个，然后在删Pop里的就可以了
int myQueuePop(MyQueue* obj) {
if (stackEmpty(&obj->PopST))
{
while (!stackEmpty(&obj->PushST))
{
stackPush(&obj->PopST, stackTop(&obj->PushST));
stackPop((&obj->PushST);
}
}
int front = stackTop(&obj->PopST);
stackPop(&obj->PopST);
return front;
}3.5去数据 返回队列开头的元素
和删除数据前面是一样的，但是这个不用删，所以结尾返回就可以了
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);
}3.6检查数据和释放数据
bool myQueueEmpty(MyQueue* obj) {
return stackEmpty(&obj->PushST) && stackEmpty(&obj->PopST);
}
void myQueueFree(MyQueue* obj) {
stackDestroy(&obj->PushST);
stackDestroy(&obj->PopST);
free(obj);
}
四.怎么把队列变成栈（力扣）
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（
push、top、pop和empty）。实现
MyStack类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。文章来源地址https://www.toymoban.com/news/detail-847102.html
注意：
- 你只能使用队列的标准操作 —— 也就是
push to back、peek/pop from front、size和is empty这些操作。- 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
核心思路：入数据时，往部位空的队列入保持另一个队列为空，出数据的时候，一次从对头的数据转移到另一个队列保存，只剩最后一个的时候pop掉
3.1初始化
typedef struct {
Queue q1;
Queue q2;
} MyStack;3.2创建
开辟两个队列，用来实现栈结构
MyStack* myStackCreate() {
MyStack* st = (MyStack*)malloc(sizeof(MyStack));
QueueInit(st->q1);
QueueInit(st->q2);
return st;
}3.3插入 void push(int x) 将元素 x 压入栈顶
入数据时，往部位空的队列入保持另一个队列为空，谁空就入谁
void myStackPush(MyStack* obj, int x) {
if (!QueueEmpty(&obj->q1))
{
Queuepush(&obj->q1,x);
}
else
{
Queuepush(&obj->q2, x);
}
}3.4删除 移除并返回栈顶元素。
先判断那个队列是空的，然后把数据放到空的里，还剩一个的时候删除
int myStackPop(MyStack* obj) {
//判断那个为空
Queue* emptyQ = &obj->q1;
Queue* noemptyQ = &obj->q2;
if (!QueueEmpty(&obj->q1))
{
emptyQ = &obj->q2;
noemptyQ = &obj->q1;
}
while (Queuesize(noemptyQ > 1))
{
Queuepush(emptyQ, QueueFront(noemptyQ));
Queuepop(noemptyQ);
}
//还剩最后一个
Queuepop(noemptyQ);
int top = QueueFront(noemptyQ);
return top;
}3.5取头顶数据 返回栈顶元素。
先判断那个是空，top就是非空的尾数据
int myStackTop(MyStack* obj) {
if (!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}3.6检查数据和释放数据
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}总结
队列与栈是重要的顺序结构，看懂这个转化之前先要学习栈与队列的基本构建文章来源：https://www.toymoban.com/news/detail-847102.html
到了这里，关于如何实现队列和栈的转化（c语言）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
