每日一题(3):使用两个栈实现一个队列

一、栈

栈：只允许在固定的一端进行插入和删除元素操作。进入和删除操作的一端称为栈顶，另一端为栈底。

栈特性：后进先出

栈功能：将数据从一个序列改变到另一种序列

二、队列

1.只允许在一端进行插入数据，在另一端删除数据

2.进行插入操作的一端称为队尾（入队列）

3.进行删除操作的一端称为队头（出队列）

4.队列具有先进先出的特性

使用两个栈实现一个队列

想法：定义一个结构体里面有两个栈，一个专门用于入数据、一个专门用于出数据，将数据先入栈到栈1中，在将数据搬移到栈2，此过程是：当满足条件栈1不为空，栈2为空时，将栈1的栈顶数据先拿出来放进栈2，这样以此类推，最后再将栈2的数据pop就可以实现一个队列

具体代码如下:

代码语言：javascript复制

#pragma once
#include "stack1.h"
#include <stdio.h>
typedef struct SQueue{
  Stack stack1;//入数据
  Stack stack2;//出数据
}SQueue;
 
//初始化
void Init(SQueue *pSQ)
{
  Stack *p1, *p2;
  p1 = &(pSQ->stack1);
  p2 = &(pSQ->stack2);
  StackInit(p1);
  StackInit(p2);
}
//入栈
void Push(SQueue *pSQ, SDataType data)
{
  Stack *p1, *p2;
  p1 = &(pSQ->stack1);
  p2 = &(pSQ->stack2);
  StackPush(p1, data);
}
 
//出栈
void Pop(SQueue *pSQ)
{
  Stack *p1, *p2;
  p1 = &(pSQ->stack1);
  p2 = &(pSQ->stack2);
  SDataType data;
 
  if(StackIsEmpty(p2))
  {
    while(!StackIsEmpty(p1))
    {
      data=StackTop(p1);
      StackPop(p1);
      StackPush(p1, data);
    }
  }
     StackPop(p2);
}
 
SDataType Front(SQueue *pSQ)
{
  Stack *p1, *p2;
  p1 = &(pSQ->stack1);
  p2 = &(pSQ->stack2);
  SDataType data;
 
  if (StackIsEmpty(p2))
  {
    while (!StackIsEmpty(p1))
    {
      data = StackTop(p1);
      StackPop(p1);
      StackPush(p1, data);
    }
  }
  return StackTop(p2);
}

队列

0 人点赞