leetcode：用队列实现栈（后进先出）

用户10925563

发布于 2024-06-04 13:01:18

720

发布于 2024-06-04 13:01:18

文章被收录于专栏：c/c++&&linux

题目描述

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

题目分析

我们先把之前写的队列实现代码搬过来

用队列实现栈最主要的是实现栈后进先出的特点，而队列的特点是先进先出，那么我们可以用两个队列来实现

一个队列存数据
另一个队列在出数据的时候导数据

具体的接口有下面几个

初始化

我们先创建一个结构体来封装两个队列

初始化两个队列

销毁

我们要分析清楚这个结构，pst存q1,q2两个队列，需要先销毁q1和q2，然后释放pst

入栈

入栈我们入到不为空的队列中去，当q1不为空则入队列q1，否则入队列q2

出栈

出栈的时候就需要导数据了，比如数据都在q1中，q2为空，这时我们先判断空队列是哪一个，然后将非空队列前n-1个数据导入到空队列中，最后留一个数据就是栈顶数据，也是队列的队头数据，可以用QFront接口，先用top保存这个数据，接着pop掉这个数据，返回top

判空

返回栈顶元素

直接取不为空队列的队尾数据

代码示例

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
//创建
typedef int QDataType;
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;
 
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;
//把队列的头尾封装在一个结构体中
 
//初始化
void QInit(Queue* pq);
//销毁
void QDestroy(Queue* pq);
 
//入队列
void QPush(Queue* pq, QDataType x);
//出队列
void QPop(Queue* pq);
//取队头数据
QDataType QFront(Queue* pq);
//取队尾数据
QDataType QBack(Queue* pq);
//判空
bool QEmpty(Queue* pq);
//返回队列有效元素个数
int QSize(Queue* pq);

//初始化
void QInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
//销毁
void QDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
//入队列
void QPush(Queue* pq, QDataType x)
{
	assert(pq);
	//创建newnode
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}
//出队列
void QPop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	QNode* del = pq->phead;
	pq->phead = pq->phead->next;
	free(del);
	del = NULL;
	if (pq->phead == NULL)
	{
		pq->ptail = NULL;
		//防止ptail成为野指针
	}
	pq->size--;
}
//取队头数据
QDataType QFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}
//取队尾数据
QDataType QBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);
	return pq->ptail->val;
}
//判空
bool QEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}
//返回队列有效元素个数
int QSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

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


MyStack* myStackCreate() {
	MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
	QInit(&(pst->q1));
	QInit(&(pst->q2));
	return pst;
}

void myStackPush(MyStack* obj, int x) {
	if (!QEmpty(&(obj->q1)))
	{
		QPush(&(obj->q1), x);
	}
	else
	{
		QPush(&(obj->q2), x);
	}
}

int myStackPop(MyStack* obj) {
	Queue* empty = &(obj->q1);
	Queue* nonempty = &(obj->q2);
	if (!QEmpty(&(obj->q1)))
	{
		empty = &(obj->q2);
		nonempty = &(obj->q1);
	}
	while (QSize(nonempty) > 1)
	{
		QPush(empty, QFront(nonempty));
		QPop(nonempty);
	}
	int top = QFront(nonempty);
	QPop(nonempty);
	return top;

}

int myStackTop(MyStack* obj) {
	if (!QEmpty(&(obj->q1)))
	{
		return QBack(&(obj->q1));
	}
	else
	{
		return QBack(&(obj->q2));
	}
}

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

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