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

    在这里插入图片描述

    🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
    🐻强烈推荐优质专栏: 🍔🍟🌯C++的世界(持续更新中)
    🐻推荐专栏1: 🍔🍟🌯C语言初阶
    🐻推荐专栏2: 🍔🍟🌯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;

    • 1
    • 2
    • 3
    • 4

    在这里插入图片描述

    (2 初始化模拟栈(myStackCreate)

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

    代码实现:

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    (3) 压栈(myStackPush)

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

    代码实现:

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    (4) 出栈(myStackPop)

    出队列相对麻烦一些:

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

    在这里插入图片描述
    在这里插入图片描述

    代码实现:

    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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    (5) 栈顶元素(myStackTop)

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

    在这里插入图片描述
    代码实现:

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    (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);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    (7)栈的释放(myStackFree)

    代码实现:

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    二、总代码示例:

    //手撕队列
/*
...
*/

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);
*/

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92

    手撕队列的源码

    //手撕队列
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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
  • 相关阅读:
    通过GFlags工具来复现因为野指针、内存越界等造成的程序崩溃
    【英雄哥六月集训】第 27天: 图
    C/C++跨平台构建工具CMake-----在C++源码中读取CMakeLists.txt配置文件中的内容
    usb2 packet format
    MFC Teechart 绘图控件使用
    mybatis与spring集成
    PHP Web 开发基础
    SFI立昌在Telecom通讯行业的方案与应用
    【Linux】gdb调试器
    软考高级系统架构设计师系列之：深入理解设计模式
  • 原文地址：https://blog.csdn.net/qq_67276605/article/details/132571690