栈与队列的性质互换

这篇具有很好参考价值的文章主要介绍了栈与队列的性质互换。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

栈与队列的性质互换

本期内容:栈,队列的定义性质,性质转换

认识栈

栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
就像是向水杯里放入乒乓球,然后逐一取出来。
栈与队列的性质互换
栈因为本身的结构,所以接口实现时就只有数据的插入(栈顶),删除(栈顶),栈顶元素的获取。对于栈来说栈内的数据容易被遍历数据,遍历时就比较耗时。所以决定了栈就是先进后出FILO

实现栈

头文件包含:

typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;
	int _top; // 栈顶
	int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);


实现:

#include"SL.h"

// 初始化栈
void StackInit(Stack* ps)
{
	STDataType* new = (STDataType*)malloc(10*sizeof(STDataType));
	if (new == NULL)
	{
		perror("malloc fail");
	}
	ps->_a = new;
	ps->_capacity = 10;
	ps->_top = 0;//相当于顺序表size。有效个数
}

// 销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = ps->_top = 0;
}



// 入栈
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->_top == ps->_capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->_a, sizeof(STDataType) * 2 * ps->_capacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
		}
		ps->_a = tmp;
		ps->_capacity *= 2;
	}
	ps->_a[ps->_top] = data;//数据入栈
	ps->_top++;
}

// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0);

	ps->_a[ps->_top--];
	/*ps->_top--;*/
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0);

	return ps->_a[ps->_top - 1];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);

	return ps->_top;
}
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
bool StackEmpty(Stack* ps)
{
	assert(ps);
	
	return ps->_top==0;
}

队列

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。
栈与队列的性质互换
结构决定算法,所以队列就是先进先出FIFO。实现时选择链表结构实现。链表可以实现对于头部删除和尾部插入效率十分的高。数组实现需要挪动数据时间复杂度O(n)。

实现

// 初始化队列
void QueueInit(Queue* q)
{
	assert(q);

	q->size = 0;
	q->_phead = NULL;
	q->_tail = NULL;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* node = (QNode*)malloc(sizeof(QNode));
	if (node == NULL)
	{
		perror("malloc fail");
	}
	node->_data = data;
	node->_pNext = NULL;


	if (q->_tail == NULL)
	{
		q->_phead=q->_tail =  node;
	}
	else
	{
		q->_tail->_pNext = node;
		 q->_tail=node;
	}
	q->size++;
}

// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
bool QueueEmpty(Queue* q)
{
	assert(q);

	return q->_phead && q->_tail;
}

// 队头出队列
void QueuePop(Queue* q)
{
	assert(q);
	assert(QueueEmpty(q));

	if (q->_phead->_pNext == NULL)
	{
		free(q->_phead);
		q->_phead = q->_tail = NULL;
	}
	else
	{
		QNode* del = q->_phead;
		q->_phead = q->_phead->_pNext;
		free(del);
	}
	q->size--;
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
	assert(q);

	return q->_phead->_data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
	assert(q);

	return q->_tail->_data;

}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
	assert(q);

	return q->size;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
	assert(q);

	QNode* cur = q->_phead;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->_pNext;
		free(del);
	}
	q->_phead = NULL;
	q->_tail = NULL;
	q->size = 0;
}

性质转换

用队列实现栈
栈与队列的性质互换

思路
对于使用队列的来说先进先出,栈是后进先出。这里实现时就是对于数据的输出顺序做调整。按照题目要求使用数定义栈,
1、push让一个队列不为空,一个队列始终为空。空队列用来存储push的值。不为空的用来模拟栈。
2、对于pop时有着一个队列没有pop空,这时就需要做一个假设,假设q1为空,q2不为空。判断假设是否正确,不正确就更换。
3、对于不为空的队列连续push前面n-1个数值到空队列中。不为空的队列最后一个就是栈顶元素。(比较灵活的一步)

代码参考;

typedef struct {
    Queue Inqueue;
    Queue Outqueue;
} MyStack;

MyStack* myStackCreate() {
	MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
	QueueInit(&obj->Inqueue);
	QueueInit(&obj->Outqueue);

	return obj;
}

void myStackPush(MyStack* obj, int x) {

   if(!QueueEmpty(&obj->Inqueue))
	 {
		 QueuePush(&obj->Inqueue,x);
	 }
	 else{
		 QueuePush(&obj->Outqueue,x);
	 }
}

int myStackPop(MyStack* obj) {

    Queue* EmptyQ=&obj->Inqueue;
		Queue* NoemptyQ=&obj->Outqueue;
		if(!QueueEmpty(&obj->Inqueue))
		{
			EmptyQ=&obj->Outqueue;
			NoemptyQ=&obj->Inqueue;
		}

		while(QueueSize(NoemptyQ)>1)
		{
			QueuePush(EmptyQ,QueueFront(NoemptyQ));
			QueuePop(NoemptyQ);
		}

		int top=QueueFront(NoemptyQ);
		QueuePop(NoemptyQ);

		return top;
}

int myStackTop(MyStack* obj) {
   if(!QueueEmpty(&obj->Inqueue))
	 {
		 return QueueBack(&obj->Inqueue);
	 }
	 else{
		 return QueueBack(&obj->Outqueue);
	 }
}

bool myStackEmpty(MyStack* obj) {

    return (QueueEmpty(&obj->Inqueue)) && (QueueEmpty(&obj->Outqueue));

}

void myStackFree(MyStack* obj) {

	QueueDestroy(&obj->Inqueue);
	QueueDestroy(&obj->Outqueue);
	free(obj);

}

栈实现队列
栈与队列的性质互换

思路:
通过创建2个栈来对于数据进行数据倒序。需要确定栈的使用。push栈,pop栈需要明确,方便后面进行数据转换使用,
1、对于一个栈用来push,一个栈来使用pop。对于push栈来说始终对于数据插入,一个栈模拟出数据。
2、对于pop栈的栈顶元素,就是队列数据出栈。

typedef struct {
    Stack ist;
    Stack ost;

} MyQueue;

bool myQueueEmpty(MyQueue* obj);
MyQueue* myQueueCreate() {
        MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
        StackInit(&obj->ist);
        StackInit(&obj->ost);

        return obj;
}

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

int myQueuePop(MyQueue* obj) {

   assert(obj);
	 assert(!myQueueEmpty(obj));

	 int top=myQueuePeek(obj);
	 StackPop(&obj->ost);

    return top;
}

int myQueuePeek(MyQueue* obj) {
 assert(obj);
	 assert(!myQueueEmpty(obj));
//倒数据
	 if(StackEmpty(&obj->ost))
	 {
		 while(!StackEmpty(&obj->ist))
		 {
			 StackPush(&obj->ost,StackTop(&obj->ist));
			 StackPop(&obj->ist);
		 }
	 }
	 return StackTop(&obj->ost);
}

bool myQueueEmpty(MyQueue* obj) {
	assert(obj);
    return StackEmpty(&obj->ist)&&StackEmpty(&obj->ost);
}

void myQueueFree(MyQueue* obj) {
	assert(obj);
    StackDestroy(&obj->ist);
    StackDestroy(&obj->ost);
    free(obj);
}

上面就是只栈与队列的基本性质定义,还有相互转换使用各自的特性实现。文章来源地址https://www.toymoban.com/news/detail-458148.html

到了这里,关于栈与队列的性质互换的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 栈与队列详解

      本文章属于原创,其中参考了程杰老师《大话数据结构》行文结构和内容,侵删。    栈(Stack):是限定仅在表尾进行插入和删除操作的线性表。   我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何元素的栈称为空栈。栈又称为后进

    2024年02月02日
    浏览(26)
  • C#中的栈与队列/练习

    用双向链表实现一个队列 使用双向链表实现栈

    2024年02月08日
    浏览(34)
  • Leetcode的AC指南 —— 栈与队列:232.用栈实现队列

    摘要: **Leetcode的AC指南 —— 栈与队列:232.用栈实现队列 **。题目介绍:请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int

    2024年01月20日
    浏览(41)
  • 算法训练day4:栈与队列

    那么我这里再列出四个关于栈的问题,大家可以思考一下。以下是以C++为例,使用其他编程语言的同学也对应思考一下,自己使用的编程语言里栈和队列是什么样的。 C++中stack 是容器么? 我们使用的stack是属于哪个版本的STL? 我们使用的STL中stack是如何实现的? stack 提供迭

    2024年02月01日
    浏览(35)
  • 数据结构和算法(4):栈与队列

    栈(stack)是存放数据对象的一种特殊容器,其中的数据元素按线性的逻辑次序排列,故也可定义首、末元素。 尽管栈结构也支持对象的插入和删除操作,但其操作的范围仅限于栈的某一特定端。 也就是说,若约定新的元素只能从某一端插入其中,则反过来也只能从这一端删

    2024年02月09日
    浏览(47)
  • 数据结构之栈与队列详解

    栈和队列是一种特殊的线性结构,他与之前学的线性结构不同,栈和队列是拥有一种特殊规则的线性结构,虽然它是用数组或者链表实现,但是只有符合这种规则才能被称作栈或者队列 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和

    2024年01月16日
    浏览(44)
  • 【数据结构】 栈与队列的相互实现

    队列与栈的操作算法是笔试面试中较为常见的题目。 本文将着重介绍平时面试中常见的关于队列与栈的应用题目,马上要进行秋招了。希望对你们有帮助 _😀 请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。 实现

    2024年02月10日
    浏览(44)
  • 代码随想录笔记--栈与队列篇

    目录 1--用栈实现队列 2--用队列实现栈 3--有效的括号 4--删除字符串中的所有相邻重复项 5--逆波兰表达式求值 6--滑动窗口的最大值 7--前k个高频元素 利用两个栈,一个是输入栈,另一个是输出栈 ; 主要思路:         弹出栈顶元素时,需要将队列前 size - 1 个元素先弹出再

    2024年02月10日
    浏览(45)
  • 【数据结构经典题目】—两个队列实现栈与两个栈实现队列

    ​                                           食用指南:本文在有C基础的情况下食用更佳                                            🔥 这就不得不推荐此专栏了: C语言                                         🍀

    2024年02月13日
    浏览(44)
  • LeetCode 热题100——栈与队列专题(三)

    20.有效的括号(题目链接) 思路: 1)括号的顺序匹配:用栈实现,遇到左括号入,遇到右括号出(保证所出的左括号与右括号对应),否则顺序不匹配。 2)括号的数量匹配: 1左括号大于右括号:用栈实现,遇到左括号入,遇到右括号出,遍历完字符数组,此时栈不为空,

    2024年02月04日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包