用队列实现栈

  • 开发
  • 50

问题描述：

请你仅用两个队列实现一个后入先出（LIFO）的栈，并支持普通队列的全部四种操作（push、top、pop和empty）。

实现MyStack类：

  • void push(int x) 将元素x压入栈顶。
  • int pop()移除并返回栈顶元素。
  • int top()返回栈顶元素。
  • boolean empty()如果栈是空的，返回true；否则，返回false。

解题思路： 

 

1. 入数据，往不为空的队列入

2. 出数据，把不为空的队列数据导入为空，直至只剩最后一个

解决本题之前，要先将队列的各类接口函数准备好，队列的接口函数我上一篇中提到了喔：

#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

//删除数据和插入数据需要记录头结点和尾结点
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
//队尾入
void QueuePush(Queue* pq, QDataType x);
//队头出
void QueuePop(Queue* pq);
//取队头的数据
QDataType QueueFront(Queue* pq);
//取队尾的数据
QDataType QueueBack(Queue* pq);
//取数据的个数
int QueueSize(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;//返回初始状态
}
//队尾入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

}
//队头出
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);//断言队列是否为空，为空就不可删除，会有野指针
	if (pq->head->next == NULL)//当只有一个节点时，tail可能为野指针，tail指向已释放的空间
		pq->tail = NULL;
	QNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;

}
//取队头的数据
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;
}
//取数据的个数
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

通过队列创建栈：

typedef struct
{
	Queue q1;
	Queue q2;
}MyStack;
MyStack* myStackCreate()
{
	MyStack* ps = (MyStack*)malloc(sizeof(MyStack));
	if (ps == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	QueueInit(&ps->q1);//对队列进行初始化
	QueueInit(&ps->q2);
	return ps;
}

在栈顶添加数据：

添加数据时，要在不为空的队列里添加：

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

从栈顶处删除数据并返回第一个数据：

int myStackPop(MyStack* obj)
{
	Queue* emptyQ = &obj->q1;
	Queue* nonemptyQ = &obj->q2;
	if (!QueueEmpty(&obj->q1))
	{
		emptyQ=&obj->q2;
		nonemptyQ=&obj->q1;
	}
	//倒数据
	while (QueueSize(nonemptyQ) > 1)
	{
		//将不空的队列的头拷贝至空队列中
		QueuePush(emptyQ, QueueFront(nonemptyQ));
		QueuePop(nonemptyQ);//删除头数据
	}
	int top = QueueFront(nonemptyQ);
	QueuePop(nonemptyQ);//删除最后一个数据，实现了后进先出
	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);
}

整体代码：

#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

//删除数据和插入数据需要记录头结点和尾结点
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
//队尾入
void QueuePush(Queue* pq, QDataType x);
//队头出
void QueuePop(Queue* pq);
//取队头的数据
QDataType QueueFront(Queue* pq);
//取队尾的数据
QDataType QueueBack(Queue* pq);
//取数据的个数
int QueueSize(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;//返回初始状态
}
//队尾入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

}
//队头出
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);//断言队列是否为空，为空就不可删除，会有野指针
	if (pq->head->next == NULL)//当只有一个节点时，tail可能为野指针，tail指向已释放的空间
		pq->tail = NULL;
	QNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;

}
//取队头的数据
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;
}
//取数据的个数
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
typedef struct
{
	Queue q1;
	Queue q2;
}MyStack;
MyStack* myStackCreate()
{
	MyStack* ps = (MyStack*)malloc(sizeof(MyStack));
	if (ps == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	QueueInit(&ps->q1);
	QueueInit(&ps->q2);
	return ps;
}
void myStackPush(MyStack* obj, int x)
{
	if (!QueueEmpty(&obj->q1))
	{
		QueuePush(&obj->q1,x);
	}
	else
	{
		QueuePush(&obj->q2, x);
	}
}
//删除数据且返回栈顶
int myStackPop(MyStack* obj)
{
	Queue* emptyQ = &obj->q1;
	Queue* nonemptyQ = &obj->q2;
	if (!QueueEmpty(&obj->q1))
	{
		emptyQ=&obj->q2;
		nonemptyQ=&obj->q1;
	}
	//倒数据
	while (QueueSize(nonemptyQ) > 1)
	{
		//将不空的队列的头拷贝至空队列中
		QueuePush(emptyQ, QueueFront(nonemptyQ));
		QueuePop(nonemptyQ);//删除头数据
	}
	int top = QueueFront(nonemptyQ);
	QueuePop(nonemptyQ);//删除最后一个数据，实现了后进先出
	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);
}

阅读全部

相关推荐

  2. 用栈实现队列

    2023-12-09 10:44:02       39 阅读

  5. leetcode-用队列实现栈

    2023-12-09 10:44:02       62 阅读

  6. leetcode-用栈实现队列

    2023-12-09 10:44:02       53 阅读

  7. 232.用栈实现队列

    2023-12-09 10:44:02       39 阅读

  8. 用队列实现栈（C）

    2023-12-09 10:44:02       32 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2023-12-09 10:44:02       94 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2023-12-09 10:44:02       100 阅读

  9. 在Django里面运行非项目文件

    2023-12-09 10:44:02       82 阅读

  19. Python语言-面向对象

    2023-12-09 10:44:02       91 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2023-12-09 10:44:02       85 阅读

热门阅读

  4. Docker 安装 Centos和宝塔

    2023-12-09 10:44:02       57 阅读

  6. Linux中用bash写脚本

    2023-12-09 10:44:02       39 阅读

  9. 关于torch.nn.Embedding的浅显理解

    2023-12-09 10:44:02       58 阅读

  11. pytorch中的loss.backward()和optimizer.step()中的使用的梯度方向问题

    2023-12-09 10:44:02       55 阅读

  14. Docker 的基本概念和优势，以及在应用程序开发中的实际应用。

    2023-12-09 10:44:02       54 阅读

  16. jenkins中“Jenkins Plot Plugin”的使用方法，比较两个excel的数据差异

    2023-12-09 10:44:02       56 阅读

  18. C++11多线程基本知识点

    2023-12-09 10:44:02       48 阅读

  19. 《C++新经典设计模式》之第21章 解释器模式

    2023-12-09 10:44:02       42 阅读

  21. 自动补全的 select antd react

    2023-12-09 10:44:02       59 阅读

  25. 机器学习实验三：支持向量机模型

    2023-12-09 10:44:02       64 阅读

  27. CSS video控件去掉视频播放条

    2023-12-09 10:44:02       54 阅读

  30. Element-UI 数字类型输入框

    2023-12-09 10:44:02       64 阅读