AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

用队列实现栈(C语言版本)

2023-09-26 62
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 用队列实现栈(C语言版本)

前言

在做这个题目之前,应当熟悉栈和队列这两种数据结构.栈和队列都是常见的数据结构，它们是基于数组或链表实现的线性数据结构。

栈（Stack）：

栈是一种后进先出（Last-In-First-Out，LIFO）的数据结构，只允许在栈顶进行插入和删除操作。栈的基本操作包括入栈（push）、出栈（pop）、查看栈顶元素（top）和判断栈是否为空（empty）。

应用场景：实现程序调用的函数堆栈、表达式求值、括号匹配检验等。

队列（Queue）：

队列是一种先进先出（First-In-First-Out，FIFO）的数据结构，只允许在队尾插入元素，在队头删除元素。队列的基本操作包括入队（enqueue）、出队（dequeue）、查看队头元素（front）和判断队列是否为空（empty）。

一、题目介绍

题目来源于–力扣

题目链接:传送门

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

 ●  void push(int x) 将元素 x 压入栈顶。

 ●  int pop() 移除并返回栈顶元素。

 ●  int top() 返回栈顶元素。

 ●  boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

(1) 模拟栈的结构:

将模拟栈的结构定义为两个队列

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

1f186a199dad47568fd8bc4d6724f24c.png

(2 初始化模拟栈(myStackCreate)

调用两个栈对应的初始化函数.


代码实现:

MyStack* myStackCreate() {
    MyStack* stack=( MyStack*)malloc(sizeof(MyStack));//开辟栈所占的空间(两个队列)
    //初始化栈
    QueueInit(&stack->q1);
    QueueInit(&stack->q2);
    return stack;
}

(3) 压栈(myStackPush)

对于入栈操作,谁是空队列,就往这个队列中正常压数据,模拟压栈的过程.

387d394831a04f1bbf8ad75bcb3ff18f.png

代码实现:

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))//如果其中一个队列是空,就往空的队列中插入元素
    {
        QueuePush(&obj->q1,x);
    }
    else{
        QueuePush(&obj->q2,x);
    }
}

(4) 出栈(myStackPop)

出队列相对麻烦一些:


  1. 倒数据,将非空队列中的数据只保留队尾数据以外,其他全部导入另一个队列(空).
  2. 保存队尾数据.
  3. 将剩余的队尾数据出栈,并返回队尾.

a6b1f8b36d8b4d9e85664cc9c84ef420.png

8aa1467394954db1997ef9970f0d9e27.png

代码实现:

int myStackPop(MyStack* obj) {
    Queue* empty=&obj->q1;//假设q1是空队列
    Queue* Notempty=&obj->q2;
    if(!QueueEmpty(&obj->q1))//如果假设错误,则说明q2才是空队列
    {
        empty=&obj->q2;
        Notempty=&obj->q1;
    }
    //将除了最后一个要删除的元素以外其他元素,倒数据到空队列
    while(QueueSize(Notempty)>1)
    {
        //将有元素的队列中的队头的值放入空队列中
        QueuePush(empty,QueueFront(Notempty));
        //弹出这个队头元素
        QueuePop(Notempty);
    }
    int top=QueueFront(Notempty);
    QueuePop(Notempty);//删除剩下的最后一个元素.
    return top;
}

(5) 栈顶元素(myStackTop)

哪个队列有数据,则将这个队列的队尾元素返回即可.

4f7a7a63951847469358f615dbe7a1c8.png

代码实现:

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))//找到有元素的队列,将其队列尾部的数据打印出来
    {
        return QueueBack(&obj->q1);
    }
    else{
        return QueueBack(&obj->q2);
    }
}

(6) 栈空(myStackEmpty)

两个队列中都没有数据则表示栈为空.


代码实现:

bool myStackEmpty(MyStack* obj) {
   if(QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2))//如果都为空,则为空栈
    {
        return true;
    }
    else 
    return false;
    //return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

(7)栈的释放(myStackFree)

代码实现:

void myStackFree(MyStack* obj) {
    //先释放栈中申请的链式队列
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    //最后释放栈这个结构体
    free(obj);
}

二、总代码示例:

//手撕队列
/*
...
*/
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) {
    if(!QueueEmpty(&obj->q1))//如果其中一个队列是空,就往空的队列中插入元素
    {
        QueuePush(&obj->q1,x);
    }
    else{
        QueuePush(&obj->q2,x);
    }
}
int myStackPop(MyStack* obj) {
    Queue* empty=&obj->q1;//假设q1是空队列
    Queue* Notempty=&obj->q2;
    if(!QueueEmpty(&obj->q1))//如果假设错误,则说明q2才是空队列
    {
        empty=&obj->q2;
        Notempty=&obj->q1;
    }
    //将除了最后一个要删除的元素以外其他元素,倒数据到空队列
    while(QueueSize(Notempty)>1)
    {
        //将有元素的队列中的队头的值放入空队列中
        QueuePush(empty,QueueFront(Notempty));
        //弹出这个队头元素
        QueuePop(Notempty);
    }
    int top=QueueFront(Notempty);
    QueuePop(Notempty);//删除剩下的最后一个元素.
    return top;
}
int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))//找到有元素的队列,将其队列尾部的数据打印出来
    {
        return QueueBack(&obj->q1);
    }
    else{
        return QueueBack(&obj->q2);
    }
}
bool myStackEmpty(MyStack* obj) {
   if(QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2))//如果都为空,则为空栈
    {
        return true;
    }
    else 
    return false;
    //return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
    //先释放栈中申请的链式队列
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    //最后释放栈这个结构体
    free(obj);
}
/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 * int param_2 = myStackPop(obj);
 * int param_3 = myStackTop(obj);
 * bool param_4 = myStackEmpty(obj);
 * myStackFree(obj);
*/

手撕队列的源码

//手撕队列
typedef int QDatatype;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDatatype data;
}QNode;
typedef struct Queue
{
  QNode* head;
  QNode* tail;
  int size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDatatype x);
void QueuePop(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
QDatatype QueueFront(Queue* pq);
QDatatype QueueBack(Queue* pq);
void QueueInit(Queue* pq)//队列的初始化
{
  assert(pq);
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
void QueueDestroy(Queue* pq)//销毁队列操作
{
  assert(pq);
  QNode* cur = pq->head;
  QNode* next = cur;
  while (next)
  {
    next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
void QueuePush(Queue* pq, QDatatype x)//入队列操作
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  newnode->data = x;
  newnode->next = NULL;
  if (newnode == NULL)
  {
    perror("newnode malloc fail:");
    return;
  }
  if (pq->head == NULL)//第一次插入
  {
    assert(pq->tail==NULL);
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
    pq->size++;
}
bool QueueEmpty(Queue* pq)//队列的判空操作
{
  assert(pq);
  if (pq->head == pq->tail && pq->head == NULL)
  {
    return true;
  }
  return false;
}
void QueuePop(Queue* pq)//出队列
{
  assert(pq);
  assert(!QueueEmpty(pq));
  if (pq->head->next == NULL)//代表还剩下一个结点
  {
    free(pq->head);//释放这个结点.
    pq->head = pq->tail = NULL;
  }
  else
  {
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
    pq->size--;
}
int QueueSize(Queue* pq)//队列元素的大小
{
  assert(pq);
  return pq->size;
}
QDatatype QueueFront(Queue* pq)//队首元素
{
  assert(pq);
  assert(pq->head);
  return pq->head->data;
}
QDatatype QueueBack(Queue* pq)//队尾元素
{
  assert(pq);
  assert(pq->head);
  return pq->tail->data;
}


文章标签：
C语言
关键词：
队列C语言
栈C语言
C语言栈
C语言队列
C语言版本
初阶牛
目录
相关文章
ephemerals__
|
15天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
90 9
石小浪♪
|
1月前
|
C语言
数组栈的实现(C语言描述)
本文介绍了如何在C语言中使用数组来实现栈的数据结构，包括栈的创建、入栈、出栈、获取栈顶元素、检查栈是否为空、获取栈的大小以及销毁栈等操作，并提供了相应的函数实现。
石小浪♪
27 1
小徐在进步
|
2月前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配，利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题，要求判断输入字符串中的括号是否正确匹配，并给出了完整的代码示例。此外，还探讨了栈在表达式求值中的应用，包括中缀、后缀和前缀表达式的转换与计算方法。最后，文章介绍了矩阵的压缩存储技术，涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略，提高存储效率。
小徐在进步
386 8
小徐在进步
|
2月前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表，常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈，顺序栈使用数组存储，链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛，如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成，链栈则基于单链表的头插法实现。
小徐在进步
367 3
爱你三千遍斯塔克
|
4月前
|
前端开发 C语言
C语言04---第一个HelloWorld（vc版本）
C语言04---第一个HelloWorld（vc版本）
爱你三千遍斯塔克
36 1
游客n5wu27bgadceq
|
5月前
|
C语言
C语言的栈帧
C语言的栈帧
游客n5wu27bgadceq
26 1
白子寰
|
1月前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
白子寰
34 3
华章计算机
|
机器学习/深度学习 算法
《数据结构与算法 C语言版》—— 3.2栈的应用举例
华章计算机
1900 0
Skyund
|
7天前
|
C语言
c语言调用的函数的声明
被调用的函数的声明： 一个函数调用另一个函数需具备的条件: 首先被调用的函数必须是已经存在的函数，即头文件中存在或已经定义过； 如果使用库函数，一般应该在本文件开头用#include命令将调用有关库函数时在所需要用到的信息“包含”到本文件中。.h文件是头文件所用的后缀。 如果使用用户自己定义的函数，而且该函数与使用它的函数在同一个文件中，一般还应该在主调函数中对被调用的函数做声明。 如果被调用的函数定义出现在主调函数之前可以不必声明。 如果已在所有函数定义之前，在函数的外部已做了函数声明，则在各个主调函数中不必多所调用的函数在做声明
Skyund
23 6
ephemerals__
|
27天前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余，其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值，并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出，支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
ephemerals__
34 10