开发者社区 开发与运维 文章 正文

栈和队列OJ题思路分享之栈和队列互换(C语言实现)

2023-06-08 50
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 我们紧接上一章的刷题分享来把后面两个题给搞定,它们分别是: 1. 用队列实现栈: 力扣225题— 2. 用栈实现队列: 力扣232题.如果你还没有自己实现过栈和队列,或者没有栈和队列的现成结构,请跳转栈和队列详解,或者去我的码云自取. 这里的题目需要使用自己实现过的结构!

1. 前言⚡

我们紧接上一章的刷题分享来把后面两个题给搞定,它们分别是: 1. 用队列实现栈: 力扣225题— 2. 用栈实现队列: 力扣232题.


如果你还没有自己实现过栈和队列,或者没有栈和队列的现成结构,请跳转栈和队列详解,或者去我的码云自取. 这里的题目需要使用自己实现过的结构!


2. 用队列实现栈⚡

2.1 审题🌈

先看题:

3601c89bb3ab6205abadc3a8ff1f564.png


这个题目的要求我们用两个队列来实现一共栈,并且这个栈可以支持插入(push),删除(pop),返回栈顶元素(top),判断栈是否为空(empty)四种基础操作.然而队列是先进先出,栈是先进后出,它们的结构完全不同,我们要实现这四个功能就要一步一步拆开来看


(值得注意的是这里所有的代码需要借助我们已经实现过的队列结构来实现)


2.11 删除⛅️

我们首先来考虑删除操作,栈中的删除是删除最后一个入栈的元素,而我们的队列是删除第一个入队列的元素,这里我们假设队列里已经有序插入了1 2 3 4,这里相当于我们要实现先删除4,再删除3,再删除2最后删除1.但是队列是先删除1,再删除2,再删除3,最后删除4,所以这个地方我们运用条件,这里我们拥有两个队列,假如我们要进行删除操作:



我们可以先把队列1中的前3个元素全部导入到队列2中,然后队列1现在只剩下4一个元素.这时再删除它.


第二次进行删除操作时,此时队列1为空,就将队列2中前2个元素导入队列1中,然后队列2这时只剩下3一个元素,这时再删除它.

画个图理解:


e517071d49621db697911fe8c46b031.png


2.12 插入⛅️

我们思考的方式和删除一样,就是要利用两个队列的优势,这里我直接给出一种思路


将要插入的数据插在不为空的队列中

因为我们在执行删除操作的时候,是将有数据的队列1的前n-1个数据导入宁外一个数据的队列2,再删除队列1中的唯一元素,执行完删除操作后,队列1也变成空队列了, 所以我们的两个队列只要有数据,就一定是这种情况:所有数据都在一个队列中,宁外一个队列没有数据


并且将数据插入不为空的队列后,它相当于是队列的尾,而我们的删除操作刚好又是将出了尾外其他元素导入宁外一个队列,并删除尾,所以这刚好又和我们的删除对应上了!


比如这个地方我们依次插入1 2 3 4,先删除一个数据,再插入一个数据,再删除!

35b832ff3a0b02a2c69f6e897e59c3d.png


正好匹配上栈的先进后出


2.13 取栈顶数据⛅️

还记得我们之前实现队列时写了两个函数:一个是取第一个元素(front函数),宁外一个是取最后一个元素(back函数), 这里要实现栈的取栈顶元素操作相当于将两个队列中,不为空的队列的尾元素给返回就是栈顶元素


2.2 代码实现🌈

这个题用两个队列实现栈,但是C语言没有这么强大的库函数来直接供我们使用,所以这里我们需要先把我们写好的栈导入到题目中


具体怎么导入如下:(这里的例子是导入栈结构,我们需要导入的是队列结构)



怎么导入自己的队列


2.21 初始化结构⛅️

typedef struct {//隐式结构体
   Queue list1;//队列1
   Queue list2;//队列2
} MyStack;
MyStack* myStackCreate() {
   MyStack* qu=(MyStack*)malloc(sizeof(MyStack));//创建一个结构体变量并且为它开辟空间
   QueueInit(&qu->list1);//初始化队列1
   QueueInit(&qu->list2);//初始化队列2
return qu;
}


这里和我们之前写过的结构有所不同,我们是在test.c文件中创建qu变量,并使用,而这个地方它是在Create中初始化变量.


2.22 插入函数⛅️

void myStackPush(MyStack* obj, int x) 
{
    if(QueueEmpty(&obj->list1))//谁为空就在宁外一个队列中插入
    {
        QueuePush(&obj->list2,x);
    }
    else
    {
        QueuePush(&obj->list1,x);
    }
}


2.23 删除函数⛅️

int myStackPop(MyStack* obj) 
{
   if(QueueEmpty(&obj->list1))//如果队列1不为空,就把队列2的前n-1个元素导入到队列1
   {
       while(QueueSize(&obj->list2)>1)//size>1进入while循环保证要剩下一个元素
       {
           QueuePush(&obj->list1,QueueFront(&obj->list2));//在第一个队列中插入第二个队列的元素
           QueuePop(&obj->list2);//队列2的元素导出去一个就要删除一下,保证下一个元素到队头
       }
       int top= QueueFront(&obj->list2);//记录队列2的最后一个元素做为栈顶
       QueuePop(&obj->list2);//再将最后一个元素删除,从此队列2从满元素变为空
       return top;//将记录好的数据返回
   }
   else//思路和上面一样,不过这个地方是队列2为空时
   {
         while(QueueSize(&obj->list1)>1)
       {
           QueuePush(&obj->list2,QueueFront(&obj->list1));
           QueuePop(&obj->list1);
       }
       int top= QueueFront(&obj->list1);
       QueuePop(&obj->list1);
       return top;
   }
}



所有的解释都放在了代码中,这个题当我们想要思路后,写代码就没有难度了!🌝


2.24 取栈顶元素⛅️

int myStackTop(MyStack* obj) {
   if(QueueEmpty(&obj->list1))//队列1为空就返回队列2的队尾
   {
       return QueueBack(&obj->list2);
   }
   else//队列2为空就返回队列1的队尾
   {
       return QueueBack(&obj->list1);
   }
}


2.25 判断栈是否为空⛅️

bool myStackEmpty(MyStack* obj) 
{
   return QueueEmpty(&obj->list1)&&QueueEmpty(&obj->list2);//当两个队列都为空时就返回空,只要有一个队列有数据就不为空
}


2.26 销毁栈⛅️

void myStackFree(MyStack* obj) {
  QueueDestroy(&obj->list1);//将队列1销毁
  QueueDestroy(&obj->list2);//将队列2销毁
  free(obj);//最后释放obj指向的空间,也就是我们最开始开辟的空间(qu)
}


2.3 需要注意的点🌈

这个题目中栈中元素的类型是整型,刚好我们自己实现的队列中typedef重命名的也是整型,所以这里没有去修改前面的代码,若题目要求存储的是浮点型,那我们就要去我们自己写的结构的第一行将 int 修改成 char 以来满足条件

这里我们实现代码的时候不能改变它给的结构,因为它会调用这些接口去判断我们写的是否正确,这里我们只能使用我们已经实现过的队列结构来实现栈结构

所有代码:(不要看它有几百行,实际上很简单)


typedef int QDataType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QN;
typedef struct Queue
{
  QN* head;
  QN* tail;
}Queue;
void QueueInit(Queue* pq);//初始化
void QueueDestroy(Queue* pq);//销毁
void QueeuPrint(Queue* pq);//打印
void QueuePush(Queue* pq,QDataType x);//插入
void QueuePop(Queue* pq);//删除
QDataType QueueFront(Queue* pq);//取队头的数据
QDataType QueueBack(Queue* pq);//取队尾的数据
size_t QueueSize(Queue* pq);//求队列有多少数据
bool QueueEmpty(Queue* pq);//判断队列是否为空
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
}
void QueueDestroy(Queue* pq)
{
  assert(pq);
  QN* cur = pq->head;
  while (cur != NULL)//如果是不等于pq->tail,最后一个数据没有被销毁
  {
  QN* next = cur->next;
  free(cur);
  cur = next;
  }
  pq->head = pq->tail = NULL;
}
void QueeuPrint(Queue* pq)
{
  assert(pq);
  QN* cur = pq->head;
  while (cur != NULL)
  {
  printf("%d ", cur->data);
  cur = cur->next;
  }
  printf("\n");
}
void QueuePush(Queue* pq,QDataType x)
{
  assert(pq);
    QN* newnode = (QN*)malloc(sizeof(QN));
  newnode->data = x;
  newnode->next = NULL;
  if (pq->head == NULL)//head为空的情况
  {
  pq->head = pq->tail = newnode;
  }
  else
  {
  pq->tail->next = newnode;
  pq->tail = newnode;
  }
}
void QueuePop(Queue* pq)//实际上是头删
{
  assert(pq);
  assert(pq->head != NULL);
  QN* cur = pq->head;
  QN* next = cur->next;
  free(cur);
  cur = NULL;
  pq->head = next;
  if (pq->head == NULL)//当删除到最后一个数据时,要把tail一起置空,否则下次再插入数据会出问题
  {
  pq->tail = NULL;
  }
}
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  QN* cur = pq->head;
  return cur->data;
}
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  QN* cur = pq->tail;
  return cur->data;
}
size_t QueueSize(Queue* pq)
{
  assert(pq);
  int count = 0;
        QN* cur = pq->head;
  while (cur)
  {
    count++;
    cur = cur->next;
  }
  return count;
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  if (pq->head == NULL)
  {
  return true;
  }
  else
  {
  return false;
  }
}
typedef struct {
Queue list1;
Queue list2;
} MyStack;
MyStack* myStackCreate() {
MyStack* qu=(MyStack*)malloc(sizeof(MyStack));
QueueInit(&qu->list1);
QueueInit(&qu->list2);
return qu;
}
void myStackPush(MyStack* obj, int x) 
{
    if(QueueEmpty(&obj->list1))
    {
        QueuePush(&obj->list2,x);
    }
    else
    {
        QueuePush(&obj->list1,x);
    }
}
int myStackPop(MyStack* obj) 
{
   if(QueueEmpty(&obj->list1))
   {
       while(QueueSize(&obj->list2)>1)
       {
           QueuePush(&obj->list1,QueueFront(&obj->list2));
           QueuePop(&obj->list2);
       }
       int top= QueueFront(&obj->list2);
       QueuePop(&obj->list2);
       return top;
   }
   else
   {
         while(QueueSize(&obj->list1)>1)
       {
           QueuePush(&obj->list2,QueueFront(&obj->list1));
           QueuePop(&obj->list1);
       }
       int top= QueueFront(&obj->list1);
       QueuePop(&obj->list1);
       return top;
   }
}
int myStackTop(MyStack* obj) {
if(QueueEmpty(&obj->list1))
{
    return QueueBack(&obj->list2);
}
else
{
    return QueueBack(&obj->list1);
}
}
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->list1)&&QueueEmpty(&obj->list2);
}
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->list1);
QueueDestroy(&obj->list2);
free(obj);
}



3. 用栈实现队列⚡

3.1 审题🌈


e1d6969797ef8636ea786a3cd60fe5e.png

有了前一个题的基础,这里我们话不多说,直接将每一个步骤拆开来一步一步实现


3.11 删除⛅️

这里用栈实现队列的删除还是比较容易想的,因为栈这种先进先出的结构, 所以我们将栈1的元素导入到栈2当中后,元素的存放顺序会倒过来,然后把数据倒过来后删除其实就是队列的删除,正合我意!并且我们的栈1导入栈2之后的每一次删除都不用重复此操作,相当于栈1导入栈2后,删除就是在栈2中进行了,这里我们就将栈2定义为专门的出数据的栈 这里假设栈1中有1 2 3 4 四个元素,我们来画图理解一下:


00348b9bc70d20f8dd09e3a1dbb8531.png


3.12 插入⛅️

有了删除做铺垫,这里我们就不叫它们为栈1和栈2了,我们直接叫它们为入数据栈(栈1)和出数据栈(栈2),既然我们说有一个栈是专门用来插入数据的,那我也不卖关子了,出数据在栈2,那么入数据就在栈1. 我们这里先假设原队列中有1 2 3 4四个元素,我们删除一个元素后再插入两个数:6和8,再来删除,看看我们的思路正不正确:


29bb1fb526d2063eddd8c0812562536.png


当我们出数据栈中所有数据都被删除了之后,我们再将入数据栈中的数据导入到出数据栈,然后再进行删除:

77e8a306726f6f3accbcd7d7132b9d2.png


有了基本思路就可以上手写代码了 :


3.2 代码实现🌈

实现代码之前,我们需要先把我们实现好的栈导入到题目中!


3.21 初始化结构⛅️

typedef struct {
   ST pushST;//入数据栈
   ST popST;//出数据栈
} MyQueue;
MyQueue* myQueueCreate() {
   MyQueue* q=(MyQueue*)malloc(sizeof(MyQueue));//和前一个题一样在create函数中开辟空间
   StackInit(&q->pushST);
   StackInit(&q->popST);
   return q;


3.22 插入函数⛅️

void myQueuePush(MyQueue* obj, int x)
{
  StackPush(&obj->pushST,x);//直接将数据插入到入数据栈中
}


3.23 删除函数⛅️

int myQueuePop(MyQueue* obj) {
   if(StackEmpty(&obj->popST))//若出数据栈中没有数据,就将入数据栈中数据导入进去
   {
       while(!StackEmpty(&obj->pushST))//将入数据栈中所有数据全部导入
       {
           StackPush(&obj->popST,StackTop(&obj->pushST));
           StackPop(&obj->pushST);//导入一个数据删除一个,以便下一个数据能来到栈顶
       }
   }
   int top=StackTop(&obj->popST);//记录出数据栈的栈顶元素并返回
   StackPop(&obj->popST);//删除出数据栈中栈顶元素
   return top;
}


这里值得注意的是导入入数据栈的元素时,不要想到我们导入一个删除一个,这样执行效率较低,应该将所有元素全部导入到出数据栈


3.24 取队头数据⛅️

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.25 其他函数⛅️

其他函数的实现和用队列实现栈大同小异,这里就不单独拿出来讲,我们直接讲所有代码放出来:


typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;//栈顶
  int capacity;
}ST;
void StackInit(ST* ps);//初始化
void StackPrint(ST* ps);//打印
void StackDestroy(ST* ps);//销毁
void StackPush(ST* ps,STDataType x);//插入数据
void StackPop(ST* ps);//删除数据
STDataType StackTop(ST* ps);//取出栈顶数据
int StackSize(ST* ps);//栈的大小
bool StackEmpty(ST* ps);//判断栈是否为空
void StackInit(ST* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->top = 0;//top指向栈顶数据的下一位,top为-1指向栈顶数据
  ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
  int newcapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
  STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)*newcapacity);
  ps->capacity = newcapacity;
  ps->a = tmp;
  }
  ps->a[ps->top] = x;
  ps->top++;
}
void StackPrint(ST* ps)
{
  assert(ps);
  while (ps->top >0)
  {
  printf("%d ", ps->a[ps->top - 1]);
  ps->top--;
  }
  printf("\n");
}
void StackPop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  ps->top--;
}
STDataType StackTop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  return ps->a[ps->top-1];
}
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;//top等于2有a[0]和a[1]两个数据
}
bool StackEmpty(ST* ps)
{
  assert(ps);
  if (ps->top <= 0)
  {
  return true;
  }
  else
  {
  return false;
  }
}
void StackDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->top = 0;
  ps->capacity = 0;
}
typedef struct {
   ST pushST;
   ST popST;
} MyQueue;
MyQueue* myQueueCreate() {
   MyQueue* q=(MyQueue*)malloc(sizeof(MyQueue));
   StackInit(&q->pushST);
   StackInit(&q->popST);
   return q;
}
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->pushST,x);
}
int myQueuePop(MyQueue* obj) {
   if(StackEmpty(&obj->popST))//若popst中中没有数据,就将pushst中数据导入进去
   {
       while(!StackEmpty(&obj->pushST))
       {
           StackPush(&obj->popST,StackTop(&obj->pushST));
           StackPop(&obj->pushST);
       }
   }
   int top=StackTop(&obj->popST);
   StackPop(&obj->popST);
   return top;
}
int myQueuePeek(MyQueue* obj) {//取队头数据
if(StackEmpty(&obj->popST))//若popst中中没有数据,就将pushst中数据导入进去
   {
       while(!StackEmpty(&obj->pushST))
       {
           StackPush(&obj->popST,StackTop(&obj->pushST));
           StackPop(&obj->pushST);
       }
   }
   return StackTop(&obj->popST);
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->pushST);
StackDestroy(&obj->popST);
free(obj);
obj=NULL;
}



4. 总结⚡

这里栈和队列的相互实现就讲完了,如果你使用c语言刷题刷到这儿我还是很佩服你的,因为C语言的库没有像c++那么强大,所以基本上什么东西都需要我们自己取实现.给你点个赞👍 👍 👍


文章标签：
C++
C语言
存储
关键词：
队列C语言
栈C语言
C语言oj
C语言栈和队列
栈队列C语言
杭电码农-NEO
目录
相关文章
小徐在进步
|
2天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表，常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈，顺序栈使用数组存储，链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛，如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成，链栈则基于单链表的头插法实现。
小徐在进步
13 3
游客n5wu27bgadceq
|
3月前
|
C语言
C语言的栈帧
C语言的栈帧
游客n5wu27bgadceq
17 1
知更鸟呆呆
|
3月前
|
C语言 C++
【数据结构】C语言实现：栈（Stack）与队列（Queue）
【数据结构】C语言实现：栈（Stack）与队列（Queue）
知更鸟呆呆
40 0
7fa6b5ui5pmtk
|
3月前
数据结构——栈(C语言版)
数据结构——栈(C语言版)
7fa6b5ui5pmtk
18 0
7fa6b5ui5pmtk
|
3月前
数据结构——队列（C语言版）
数据结构——队列（C语言版）
7fa6b5ui5pmtk
28 0
7fa6b5ui5pmtk
|
3月前
|
C语言
C语言——oj刷题——猜数字游戏
C语言——oj刷题——猜数字游戏
7fa6b5ui5pmtk
15 0
7fa6b5ui5pmtk
|
3月前
|
编译器 C语言
C语言——oj刷题——判断闰年
C语言——oj刷题——判断闰年
7fa6b5ui5pmtk
22 0
7fa6b5ui5pmtk
|
3月前
|
C语言
C语言——oj刷题——找单身狗1
C语言——oj刷题——找单身狗1
7fa6b5ui5pmtk
24 0
华章计算机
|
机器学习/深度学习 算法
《数据结构与算法 C语言版》—— 3.2栈的应用举例
华章计算机
1868 0
小徐在进步
|
2天前
|
存储 C语言
C语言程序设计核心详解 第十章:位运算和c语言文件操作详解_文件操作函数
本文详细介绍了C语言中的位运算和文件操作。位运算包括按位与、或、异或、取反、左移和右移等六种运算符及其复合赋值运算符，每种运算符的功能和应用场景都有具体说明。文件操作部分则涵盖了文件的概念、分类、文件类型指针、文件的打开与关闭、读写操作及当前读写位置的调整等内容，提供了丰富的示例帮助理解。通过对本文的学习，读者可以全面掌握C语言中的位运算和文件处理技术。
小徐在进步
13 5