当前位置： 首页 > article >正文

【数据结构】_栈与队列经典算法OJ：栈与队列的互相实现

article 2025/2/11 0:51:18

目录

1. 用队列实现栈

1.1 题目链接及描述

1.2 解题思路

1.3 程序

2. 用栈实现队列

2.1 题目链接及描述

2.2 解题思路

2.3 程序

1. 用队列实现栈

1.1 题目链接及描述

1. 题目链接 ： 225. 用队列实现栈 - 力扣（LeetCode）

2. 题目描述：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

1.2 解题思路

队列的特点是先进先出，栈的特点是后进先出。

（1）分析出栈操作的实现：

令第一个队列入队4个元素：1、2、3、4；

此时出栈要求出4，而当前队列只能出1。

思路：依次从第一个队列出队1、2、3元素，并依次入队第二个队列；

（出队直至第一个队列只剩一个元素，该元素就是出栈要求的元素）：

（2）分析入栈操作的实现：
基于（1），现假设需入栈5、6，考虑下一个需出栈的情况，若为栈则需出6，为了实现该效果，将5、6入第二个队列，再类似（1）步骤，将2~5元素依次入队第一个队列，再出队第二队列的6以实现目标效果：

总结：保持一个存数据，一个为空；

入数据则入非空队列，出数据则将前面若干个数据入队至另一空队列；

1.3 程序

由于C语言并未提供实现有队列的库，故队列需自行实现。

相关代码见下文：

【数据结构】_队列的结构与实现-CSDN博客文章浏览阅读495次，点赞8次，收藏4次。队列：只允许在一端进行数据的插入操作，在另一端进行数据的删除操作的特殊线性表，队列具有先进先出FIFO（First In First Out）的特点。（2）若队列仅剩一个元素，按当前无特殊情况处理的方法实现，则pq->ptail未置空，使得其成为野指针，故需对其进行单独处理。注：若采取设有头结点的单链表，可传一级指针，但仍然需传队尾结点指针，仍需要传递两个参数，总体而言依然较为麻烦。若将数组头视为队头，数组尾视为队尾，则插入对应尾插实现方便，但删除对应头删实现麻烦；出队列：进行删除操作的一端称为队头；https://blog.csdn.net/m0_63299495/article/details/145443895https://blog.csdn.net/m0_63299495/article/details/145443895完整解答程序如下：

typedef int QDataType;
typedef struct QueueNode {
	QDataType val;
	struct QueueNode* next;
}QNode;
typedef struct Queue {
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;
// 初始化
void QueueInit(Queue* pq);
// 销毁
void QueueDestory(Queue* pq);
// 队尾插入
void QueuePush(Queue* pq, QDataType x);
// 队头删除
void QueuePop(Queue* pq);
// 计算列表元素个数；
int QueueSize(Queue* pq);
// 取队头/队尾数据
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
// 判空
bool QueueEmpty(Queue* pq);

// 初始化
void QueueInit(Queue* pq) {
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}
// 队尾插入
void QueuePush(Queue* pq, QDataType x) {
	assert(pq);
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL) {
		perror("malloc fail");
		return;
	}
	newNode->val = x;
	newNode->next = NULL;
	// 情况1：队列为空
	if (pq->ptail == NULL) {
		pq->phead = pq->ptail = newNode;
	}
	// 情况2：队列不为空：队尾插入
	else {
		pq->ptail->next = newNode;
		pq->ptail = newNode;
	}
	pq->size++;
}
// 队头删除
void QueuePop(Queue* pq) {
	assert(pq);
	assert(QueueSize(pq)!=0);
	// 情况1：队列仅一个结点
	if (pq->phead->next == NULL) {
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	// 情况2：队列有多个结点
	else {
		QNode* pheadNext = pq->phead->next;
		free(pq->phead);
		pq->phead = NULL;
		pq->phead = pheadNext;
	}
	pq->size--;
}
// 计算列表元素个数；
int QueueSize(Queue* pq) {
	return pq->size;
}
// 取队头/队尾数据
QDataType QueueFront(Queue* pq) {
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}
QDataType QueueBack(Queue* pq) {
	assert(pq);
	assert(pq->phead);
	return pq->ptail->val;
}
// 判空
bool QueueEmpty(Queue* pq) {
	assert(pq);
	return pq->size == 0;
}
// 销毁
void QueueDestory(Queue* pq) {
	assert(pq);
	QNode* cur = pq->phead;
	while (cur) {
		QNode* curNext = cur->next;
		free(cur);
		cur = NULL;
		cur = curNext;
	}
	pq->phead = pq->ptail = NULL;
}

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


MyStack* myStackCreate() {
    MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
    if(pst == NULL){
        perror("malloc fail");
        return NULL;
    }
    QueueInit(&(pst->q1));
    QueueInit(&(pst->q2));
    return pst;
}

void myStackPush(MyStack* obj, int x) {
    assert(obj);
    // 入队不为空的队列
    if(!QueueEmpty(&(obj->q1))){
        QueuePush(&(obj->q1),x);
    }else{
        QueuePush(&(obj->q2),x);
    }
}

int myStackPop(MyStack* obj) {
    assert(obj);
    // 假设法确定空队列与非空队列
    Queue* empty=&(obj->q1);
    Queue* nonEmpty=&(obj->q2);
    if(!QueueEmpty(&(obj->q1))){
        empty=&(obj->q2);
        nonEmpty=&(obj->q1);
    }
    // 将非空队列前size-1个数据至另一队列
    while(QueueSize(nonEmpty)>1){
        QueuePush(empty,QueueFront(nonEmpty));
        QueuePop(nonEmpty);
    }
    // 返回栈顶元素
    int top=QueueFront(nonEmpty);
    QueuePop(nonEmpty);
    return top;
}

int myStackTop(MyStack* obj) {
    // 无需移动数据，返回非空队列的队尾结点的数据域即可
    if(!QueueEmpty(&(obj->q1))){
        return QueueBack(&(obj->q1));
    }else{
        return QueueBack(&(obj->q2));
    }
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&(obj->q1))&&QueueEmpty(&(obj->q2));
}

void myStackFree(MyStack* obj) {
    QueueDestory(&(obj->q1));
    QueueDestory(&(obj->q2));
    free(obj);
}

注：关于本题中各结构体及指针的指向关系：

同时也由于结构体指针又作为另一结构体的成员变量，进行free时需要全部释放，防止因为需要释放空间的遗漏导致内存泄漏；

2. 用栈实现队列

2.1 题目链接及描述

题目链接：232. 用栈实现队列 - 力扣（LeetCode）

题目描述：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true；否则，返回 false；

2.2 解题思路

栈的特点是后进先出，队列的特点是先进先出。

（1）分析出队列操作：

令第一个栈入栈1、2、3、4四个元素，此时队列要求出队1，但当前栈只能出栈4，

思路：依次从第一个栈出栈4、3、2，并令其入栈第二个栈，再出栈第一个栈的元素1即可；

（2）分析入队列操作：

令要实现的队列入队列5、6，将其入栈到第一个栈，而后将第一个栈视为push栈，仅用于入数据；将第二个栈视为pop栈，仅用于出数据。当pop栈为空但还要进行pop操作时，将push栈的元素依次出栈并入栈pop栈；

2.3 程序

由于C语言并未提供实现有栈的库，故栈需自行实现。

相关代码见下文：

【数据结构】_栈的结构与实现-CSDN博客文章浏览阅读296次，点赞3次，收藏7次。若top表示栈顶元素的下标，则初始化时(栈内无元素)，top=-1，插入时在a[top++]处入栈元素；若top表示栈顶元素的下一个元素的下标，则初始化时top为0，插入时在a[top]处入栈元素。1、若采用数组实现栈，则可将数组头视为栈底，数组尾视为栈顶，出入栈都在数组尾进行操作。3、若采用双链表实现栈，则无论将哪端视为栈底，出栈、入栈等方法的实现都非常方便；1、栈：一种特殊的线性表，只允许在固定的一端插入和删除数据；2、压栈：栈的插入操作叫做进栈、压栈、入栈。3、出栈：栈的删除操作叫做出栈。https://blog.csdn.net/m0_63299495/article/details/145428244https://blog.csdn.net/m0_63299495/article/details/145428244完整程序如下：

typedef int STDataType;
typedef struct Stack {
	// 动态开辟数组
	STDataType* a;
	// top表示栈顶元素的下一个元素的下标
	int top;
	int capacity;
}ST;
void STInit(ST* pst);
void STDestory(ST* pst);
// 压栈
void STPush(ST* pst,STDataType x);
// 出栈
void STPop(ST* pst);
// 获取栈顶数据
STDataType STTop(ST* pst);
// 判空
bool STEmpty(ST* pst);
// 获取栈元素个数
int STSize(ST* pst);

typedef struct {
    ST pushst;
    ST popst;
}MyQueue;

MyQueue* myQueueCreate();
void myQueuePush(MyQueue* obj, int x);
int myQueuePop(MyQueue* obj);
int myQueuePeek(MyQueue* obj);
bool myQueueEmpty(MyQueue* obj);
void myQueueFree(MyQueue* obj);

// 初始化
void STInit(ST* pst) {
	assert(pst);
	pst->a = NULL;
	// top表示栈顶元素的下一个元素的下标
	pst->top = 0;
	// capacity表示栈内元素个数（等价于栈顶元素的下一个元素的下标）
	pst->capacity = 0;
}
// 销毁
void STDestory(ST* pst) {
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}
// 压栈
void STPush(ST* pst, STDataType x) {
	assert(pst);
	// 满则扩容
	if (pst->top == pst->capacity) {
		int newCapacity = pst->capacity == 0? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * (sizeof(STDataType)));
		if (tmp == NULL) {
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newCapacity;
	}
	// 入栈数据
	pst->a[pst->top] = x;
	pst->top++;
}
// 出栈
void STPop(ST* pst) {
	assert(pst);
	// 判栈非空
	assert(pst->top>0);
	pst->top--;
}
// 获取栈顶数据
STDataType STTop(ST* pst) {
	assert(pst);
	assert(pst->top>0);
	return pst->a[pst->top - 1];
}
// 判空
bool STEmpty(ST* pst) {
	if (pst->top == 0) {
		return true;
	}
	return false;
	//return pst->top == 0;
}
// 获取栈元素个数
int STSize(ST* pst) {
	assert(pst);
	return pst->top;
}


MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    STInit(&(obj->pushst));
    STInit(&(obj->popst));
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    STPush(&(obj->pushst),x);
}

int myQueuePop(MyQueue* obj) {
    assert(obj);
    // 借用myQueuePeek保证popst有数据
    int front=myQueuePeek(obj);
    STPop(&(obj->popst));
    return front;
}

int myQueuePeek(MyQueue* obj) {
    assert(obj);
    // pop栈为空：倒数据
    if(STEmpty(&(obj->popst))){
        while(!STEmpty(&(obj->pushst))){
            STDataType top = STTop(&(obj->pushst));
            STPop(&(obj->pushst));
            STPush(&(obj->popst),top);
        }
    }
    return STTop(&(obj->popst));
}

bool myQueueEmpty(MyQueue* obj) {
    assert(obj);
    return STEmpty(&(obj->pushst))&&STEmpty(&(obj->popst));
}

void myQueueFree(MyQueue* obj) {
    assert(obj);
    STDestory(&(obj->popst));
    STDestory(&(obj->pushst));
    free(obj);
}


http://www.kler.cn/a/539964.html

相关文章：

  • 增量hdfs数据追平
  • 深度学习｜表示学习｜Instance Normalization 全面总结｜26
  • 打家劫舍3
  • ASP.NET Core JWT
  • Jetbrains IDE http客户端使用教程
  • DeepSeek在FPGA/IC开发中的创新应用与未来潜力
  • 深度学习 语音合成
  • Java并发编程笔记
  • C++使用Json保存配置参数
  • 【计算机网络基础】ACL
  • 【Redis keys命令有什么问题？】
  • Android内存性能优化量化指标
  • 深度卷积神经网络实战海洋动物图像识别
  • 网络基础知识与配置
  • 《ARM64体系结构编程与实践》学习笔记（三）
  • 7 使用 Pydantic 验证 FastAPI 的请求数据
  • 网站快速收录策略：提升爬虫抓取效率
  • 2025Stable Diffusion WebUI详细使用指南
  • Spring Boot Actuator EndPoints（官网文档解读)
  • Android Camera API 介绍
  • 【LLM】DeepSeek R1训练成本降低分析篇
  • c++ haru生成pdf输出饼图
  • 安卓基础（Okhttp3）
  • ZooKeeper 技术全解：概念、功能、文件系统与主从同步
  • 【SQL技术】不同数据库引擎 SQL 优化方案剖析
  • 软件测试之通用功能测试点