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

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

2023-09-26 68
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 用队列实现栈(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__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
210 9
龙大吉
|
27天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
53 5
石小浪♪
|
2月前
|
C语言
数组栈的实现(C语言描述)
本文介绍了如何在C语言中使用数组来实现栈的数据结构，包括栈的创建、入栈、出栈、获取栈顶元素、检查栈是否为空、获取栈的大小以及销毁栈等操作，并提供了相应的函数实现。
石小浪♪
44 1
小徐在进步
|
3月前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配，利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题，要求判断输入字符串中的括号是否正确匹配，并给出了完整的代码示例。此外，还探讨了栈在表达式求值中的应用，包括中缀、后缀和前缀表达式的转换与计算方法。最后，文章介绍了矩阵的压缩存储技术，涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略，提高存储效率。
小徐在进步
484 8
小徐在进步
|
3月前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表，常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈，顺序栈使用数组存储，链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛，如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成，链栈则基于单链表的头插法实现。
小徐在进步
542 3
程序员大阳
|
C语言
C语言队列实现
一，简介 开发环境是VC6.0，实现了一个基于C语言的队列。 主要功能，入队、出队、显示当前队列元素。
程序员大阳
130 0
LuckiBit
|
24天前
|
存储 C语言 开发者
【C语言】字符串操作函数详解
这些字符串操作函数在C语言中提供了强大的功能，帮助开发者有效地处理字符串数据。通过对每个函数的详细讲解、示例代码和表格说明，可以更好地理解如何使用这些函数进行各种字符串操作。如果在实际编程中遇到特定的字符串处理需求，可以参考这些函数和示例，灵活运用。
LuckiBit
48 10
LuckiBit
|
24天前
|
存储 程序员 C语言
【C语言】文件操作函数详解
C语言提供了一组标准库函数来处理文件操作，这些函数定义在 `<stdio.h>` 头文件中。文件操作包括文件的打开、读写、关闭以及文件属性的查询等。以下是常用文件操作函数的详细讲解，包括函数原型、参数说明、返回值说明、示例代码和表格汇总。
LuckiBit
43 9
LuckiBit
|
24天前
|
存储 Unix Serverless
【C语言】常用函数汇总表
本文总结了C语言中常用的函数，涵盖输入/输出、字符串操作、内存管理、数学运算、时间处理、文件操作及布尔类型等多个方面。每类函数均以表格形式列出其功能和使用示例，便于快速查阅和学习。通过综合示例代码，展示了这些函数的实际应用，帮助读者更好地理解和掌握C语言的基本功能和标准库函数的使用方法。感谢阅读，希望对你有所帮助！
LuckiBit
33 8
LuckiBit
|
24天前
|
C语言 开发者
【C语言】数学函数详解
在C语言中，数学函数是由标准库 `math.h` 提供的。使用这些函数时，需要包含 `#include <math.h>` 头文件。以下是一些常用的数学函数的详细讲解，包括函数原型、参数说明、返回值说明以及示例代码和表格汇总。
LuckiBit
43 6