大魔王（已黑化）

大魔王（已黑化）

关注
发信
关注(28)粉丝(399)

用队列实现栈——数据结构与算法

用队列实现栈——数据结构与算法-LMLPHP
用队列实现栈——数据结构与算法-LMLPHP

一、题目

二、思路

用队列实现栈——数据结构与算法-LMLPHP

用队列实现栈——数据结构与算法-LMLPHP

三、代码

1、队列代码

#include <stdlib.h>

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

void QInit(Queue* q)
{
	assert(q);
	q->head = q->tail = NULL;
	q->size = 0;
}

void QDestroy(Queue* q)
{
	assert(q);
	while (q->head)
	{
		QNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
	q->tail = NULL;
	q->size = 0;
}

QNode* BuyNewnode(QDataType x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc error");
		assert(newnode);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

void QPush(Queue* q, QDataType x)
{
	assert(q);
	QNode* newnode = BuyNewnode(x);
	if (q->head == NULL)
	{
		assert(q->head == q->tail);
		q->head = q->tail = newnode;
	}
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
	q->size++;
}

void QPop(Queue* q)
{
	assert(q);
	assert(q->head && q->tail);
	if (q->head->next == NULL)
	{
		assert(q->head == q->tail);
		free(q->head);
		q->head = q->tail = NULL;
	}
	else
	{
		QNode* newhead = q->head->next;
		free(q->head);
		q->head = newhead;
	}
	q->size--;
}

int QSize(Queue* q)
{
	assert(q);
	return q->size;
}

bool QEmpty(Queue* q)
{
	assert(q);
	//-------------------------1------------------------------------------------
	//1这里的报错，但是其实根本没错，是在下面的2处错的，所以在哪个地方报错可以重点看那个地方，但并不一定就是这个部分错了。
	return q->size == 0;
}

QDataType QFront(Queue* q)
{
	assert(q);
	assert(q->head);
	return q->head->data;
}

QDataType QBack(Queue* q)
{
	assert(q);
	assert(!QEmpty(q));
	return q->tail->data;
}

2、创建两个队列模拟的栈

//匿名结构体，创建一个结构体是我的栈，因为我们使用队列模拟栈，所以里面放两个队列。
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


//创建我的栈，前面我们的模拟栈的结构体已经创建好了，现在就是要创建一个指针指向我们开辟出的该结构体的空间，并使其初始化。因为这是创建好后用的返回值传给别的函数，所以不能直接创建变量，要malloc，否则除该作用域就销毁了。
MyStack* myStackCreate() {
    MyStack* creat = (MyStack*)malloc(sizeof(MyStack));
    if(creat == NULL)
    {
        perror("malloc error");
        assert(creat);
    }
    QInit(&creat->q1);
    QInit(&creat->q2);
    return creat;
}

3、入栈

用队列实现栈——数据结构与算法-LMLPHP

void myStackPush(MyStack* obj, int x) {
	Queue* EmptyQ = &obj->q1;
	Queue* nonEmptyQ = &obj->q2;
	//if (QEmpty(&EmptyQ) == 0)-------------------------2(错的)----------------------------------
	if (QEmpty(EmptyQ) == 0)
	{
		EmptyQ = &obj->q2;
		nonEmptyQ = &obj->q1;
	}
	QPush(nonEmptyQ, x);
}

4、出栈

用队列实现栈——数据结构与算法-LMLPHP

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

5、访问栈顶元素

//方法1.访问栈顶元素
int myStackTop(MyStack* obj) {
    if(!QEmpty(&obj->q1))
    {
        return QBack(&obj->q1);
    }
    else
    	return QBack(&obj->q2);
}

//方法2.访问栈顶元素
// 力扣检查比较严格，就算最后的那个return没用，但有返回值的函数结尾还是要加上return 的。
int myStackTop(MyStack* obj) {
	int ret = 0;
		Queue* EmptyQ = &obj->q1;
		Queue* nonEmptyQ = &obj->q2;
		if(!QEmpty(EmptyQ))
		{
				EmptyQ = &obj->q2;
				nonEmptyQ = &obj->q1;
		}
		while(QSize(nonEmptyQ)>0)
		{
			if(QSize(nonEmptyQ) == 1)
			{
				ret = QFront(nonEmptyQ);
				QPush(EmptyQ,QFront(nonEmptyQ));
				QPop(nonEmptyQ);
				return ret;
			}
			QPush(EmptyQ,QFront(nonEmptyQ));
			QPop(nonEmptyQ);
		}
		return ret;
}

6、判断栈是否为空

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

7、释放空间

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

8、总代码

#include <stdlib.h>

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

void QInit(Queue* q)
{
	assert(q);
	q->head = q->tail = NULL;
	q->size = 0;
}

void QDestroy(Queue* q)
{
	assert(q);
	while (q->head)
	{
		QNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
	q->tail = NULL;
	q->size = 0;
}

QNode* BuyNewnode(QDataType x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc error");
		assert(newnode);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

void QPush(Queue* q, QDataType x)
{
	assert(q);
	QNode* newnode = BuyNewnode(x);
	if (q->head == NULL)
	{
		assert(q->head == q->tail);
		q->head = q->tail = newnode;
	}
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
	q->size++;
}

void QPop(Queue* q)
{
	assert(q);
	assert(q->head && q->tail);
	if (q->head->next == NULL)
	{
		assert(q->head == q->tail);
		free(q->head);
		q->head = q->tail = NULL;
	}
	else
	{
		QNode* newhead = q->head->next;
		free(q->head);
		q->head = newhead;
	}
	q->size--;
}

int QSize(Queue* q)
{
	assert(q);
	return q->size;
}

bool QEmpty(Queue* q)
{
	assert(q);
	//-------------------------1------------------------------------------------
	//1这里的报错，但是其实根本没错，是在下面的2处错的，所以在哪个地方报错可以重点看那个地方，但并不一定就是这个部分错了。
	return q->size == 0;
}

QDataType QFront(Queue* q)
{
	assert(q);
	assert(q->head);
	return q->head->data;
}

QDataType QBack(Queue* q)
{
	assert(q);
	assert(!QEmpty(q));
	return q->tail->data;
}

//匿名结构体，创建一个结构体是我的栈，因为我们使用队列模拟栈，所以里面放两个队列。
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


//创建我的栈，前面我们的模拟栈的结构体已经创建好了，现在就是要创建一个指针指向我们开辟出的该结构体的空间，并使其初始化。因为这是创建好后用的返回值传给别的函数，所以不能直接创建变量，要malloc，否则除该作用域就销毁了。
MyStack* myStackCreate() {
    MyStack* creat = (MyStack*)malloc(sizeof(MyStack));
    if(creat == NULL)
    {
        perror("malloc error");
        assert(creat);
    }
    QInit(&creat->q1);
    QInit(&creat->q2);
    return creat;
}

void myStackPush(MyStack* obj, int x) {
	Queue* EmptyQ = &obj->q1;
	Queue* nonEmptyQ = &obj->q2;
	//if (QEmpty(&EmptyQ) == 0)-------------------------2----------------------------------
	if (QEmpty(EmptyQ) == 0)
	{
		EmptyQ = &obj->q2;
		nonEmptyQ = &obj->q1;
	}
	QPush(nonEmptyQ, x);
}

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

// //方法1.访问栈顶元素
// int myStackTop(MyStack* obj) {
//     if(!QEmpty(&obj->q1))
//     {
//         return QBack(&obj->q1);
//     }
//     else
//         return QBack(&obj->q2);
// }

//方法2.访问栈顶元素
// 力扣检查比较严格，就算最后的那个return没用，但有返回值的函数结尾还是要加上return 的。
int myStackTop(MyStack* obj) {
	int ret = 0;
		Queue* EmptyQ = &obj->q1;
		Queue* nonEmptyQ = &obj->q2;
		if(!QEmpty(EmptyQ))
		{
				EmptyQ = &obj->q2;
				nonEmptyQ = &obj->q1;
		}
		while(QSize(nonEmptyQ)>0)
		{
			if(QSize(nonEmptyQ) == 1)
			{
				ret = QFront(nonEmptyQ);
				QPush(EmptyQ,QFront(nonEmptyQ));
				QPop(nonEmptyQ);
				return ret;
			}
			QPush(EmptyQ,QFront(nonEmptyQ));
			QPop(nonEmptyQ);
		}
		return ret;
}

//方法3.访问栈顶元素
// int myStackTop(MyStack* obj) {
// 	Queue* EmptyQ = &obj->q1;
// 	Queue* nonEmptyQ = &obj->q2;
// 	if (!QEmpty(EmptyQ))
// 	{
// 		EmptyQ = &obj->q2;
// 		nonEmptyQ = &obj->q1;
// 	}
// 	while (QSize(nonEmptyQ) != 1)
// 	{
// 		QPush(EmptyQ, QFront(nonEmptyQ));
// 		QPop(nonEmptyQ);
// 	}
// 	int ret = QFront(nonEmptyQ);
// 	QPush(EmptyQ,QFront(nonEmptyQ));
// 	QPop(nonEmptyQ);
// 	return ret;
// }

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

void myStackFree(MyStack* obj) {
    QDestroy(&obj->q1);
    QDestroy(&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-----这两个地方是一个错误，因为在2多写了个取地址，然后在1处报错，结果检查了大半天也检查不出来，因为1处报错很难想出来是2处的问题。所以：报错的地方重点检查，如果真的没错误，可能是其他地方的问题。
  • 分别指向空队列和非空队列时别弄混了，有点绕。
  • 博主长期更新，博主的目标是不断提升阅读体验和内容质量，如果你喜欢博主的文章，请点个赞或者关注博主支持一波，我会更加努力的为你呈现精彩的内容。

用队列实现栈——数据结构与算法-LMLPHP

08-08 11:55
Powered by LMLPHP ©2024 大魔王（已黑化） 0.009957