草庐IT

详细介绍栈和队列，适合零基础小白反复使用【数据结构】

鄃鳕 2023-04-25 原文

文章目录

栈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底
栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则

压栈(Push)：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶
出栈(Pop)：栈的删除操作叫做出栈。出数据也在栈顶

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小

栈的初始化

typedef int  StackDataType;
typedef struct Stack
{
	StackDataType * a;
	int top; // 栈顶
	int capacity; 
}StackType;

void StackTypeInit(StackType* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0; // ps->top = -1 
}

栈初始化 ，top可以给-1 ，top可以给 0

如果top给的是 -1 , 意味着top 指向栈顶数据
top 先++ ，再放数据 ，此时top 指向栈顶的数据

初始化时 ，top 给的是0 ， 意味着top指向栈顶数据的下一个

压栈

压栈需要考虑容量的问题 ，如果容量已满 ，则需要扩容

void StackTypePush(StackType* ps, StackDataType x)
{
	// 容量已满  ,考虑增容 
	if (ps->capacity == ps->top)
	{
		int  newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

		StackType* tmp = (StackType*)realloc(ps->a, sizeof(StackType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		//增容成功 
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

销毁

void StackTypeDestory(StackType* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

出栈

当栈的数据为空时 此时注意不需要删除了

void StackTypePop(StackType* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;

}

栈中有效元素个数

int StackSize(StackType* ps)
{
	assert(ps);
	return ps->top;
}

判断栈是否为空

如果栈为空 ，此时就不需要进行出栈操作 ,否则会导致越界，形成非法访问

bool StackEmpty(StackType* ps)
{
	assert(ps);

	return ps->top == 0 ;   // 栈为空 返回true ，不为空 返回 false 
}

拿到栈顶数据

StackDataType StackTop(StackType* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));  //StackEmpty 是空 return true 不是空return false  
	return ps->a[ps->top - 1];  // 初始化是top = 0 是指向栈顶的下一个数据 top-1 即是栈顶数据

}

完整代码

Stack.c

#include"Stack.h"
void StackTypeInit(StackType* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0; // ps->top = -1 
}

void StackTypePush(StackType* ps, StackDataType x)
{
	// 容量已满  ,考虑增容 
	if (ps->capacity == ps->top)
	{
		int  newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

		StackType* tmp = (StackType*)realloc(ps->a, sizeof(StackType) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		//增容成功 
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

void StackTypeDestory(StackType* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackTypePop(StackType* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;

}

int StackSize(StackType* ps)
{
	assert(ps);
	return ps->top;
}

bool StackEmpty(StackType* ps)
{
	assert(ps);

	return ps->top; 
}

StackDataType StackTop(StackType* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));  //StackEmpty 是空 return true 不是空return false  
	return ps->a[ps->top - 1];  // 初始化是top = 0 是指向栈顶的下一个数据 top-1 即是栈顶数据

}

Stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int  StackDataType;

typedef struct Stack
{
	StackDataType * a;
	int top; // 栈顶
	int capacity; 
}StackType;

void StackTypeInit(StackType* ps);

void StackTypePush(StackType* ps, StackDataType x);

void StackTypeDestory(StackType* ps);


void StackTypePop(StackType* ps); 

int StackSize(StackType* ps);  // 栈中有效元素个数

bool StackEmpty(StackType* ps);  //判断栈是否为空  

StackDataType StackTop(StackType* ps);  //拿到栈顶数据

test.c

#include"Stack.h" 

void TestStack1()
{
	StackType ST;
	StackTypeInit(&ST);

	StackTypePush(&ST, 1);
	StackTypePush(&ST, 2);

	printf("%d", StackTop(&ST)); //拿到栈顶元素 
	StackTypePop(&ST);

	StackTypePush(&ST, 3);
	StackTypePush(&ST, 4);



	StackTypeDestory(&ST);
}

void TestStack2()
{
	StackType ST;
	StackTypeInit(&ST);

	StackTypePush(&ST, 1);
	StackTypePush(&ST, 2);
	StackTypePush(&ST, 3);
	StackTypePush(&ST, 4);
	StackTypePush(&ST, 5);

	//遍历 
	while (!StackEmpty(&ST))
	{
		printf("%d ", StackTop(&ST));
		StackTypePop(&ST);
	}

	StackTypeDestory(&ST);
}
void TestStack3()
{
	StackType ST;
	StackTypeInit(&ST);

	StackTypePush(&ST, 1);
	StackTypePush(&ST, 2);

	printf("%d ", StackTop(&ST));
	StackTypePop(&ST);

	StackTypePush(&ST, 3);
	StackTypePush(&ST, 4);

	printf("%d ", StackTop(&ST));
	StackTypePop(&ST);

	StackTypePush(&ST, 5);



	//遍历 
	while (!StackEmpty(&ST))
	{
		printf("%d ", StackTop(&ST));
		StackTypePop(&ST);
	}

	StackTypeDestory(&ST);

}
int main()
{
	//TestStack1();
	//TestStack2();
	TestStack3();


	return 0;
}

队列

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低

我们采用类似单链表来实现队列 ，但是队列要求队尾入队，队头出队 ，也就意味着需要频繁找尾指针 ，而单链表去找尾指针效率很低，所以定义一个头指针和尾指针，方便找尾节点，这样就会多两个指针 ，如果放进函数里当参数会很麻烦 ，干脆直接封装一个结构体

单链表不定义一个尾指针呢？如果我们给单链表定义了一个尾指针的话，尾插就不再需要去找尾节点了，但是尾删的话，定义的尾指针就显得很鸡肋，此时尾删依然需要找到尾节点的前一个节点，也就说如果单链表定义尾指针，也不能完美解决问题，所以单链表就不定义尾指针

typedef int   QueueNodeTypeData;

typedef struct  QueueNode
{
	struct  QueueNode* next;
	QueueNodeTypeData data;
}QueueNodeType;

typedef struct Queue
{
	QueueNodeType * tail; // 队尾
	QueueNodeType * head; //队头
	int size; 
} Queue;  // 链式结构：表示队列

队列的初始化

我们采用链表的形式来实现队列

将头和尾初始化为NULL

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

队尾入队列

和单链表尾插大致相同

void QueuePush(Queue* pq, QueueNodeTypeData x) // 入队 
{
	assert(pq);
	QueueNodeType* newnode =(QueueNodeType*) malloc( sizeof(QueueNodeType) );
	if (newnode == NULL)
	{
		printf(" malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//扩容成功

	//第一次入队
	if ( pq->head == NULL)
	{
		assert(pq->tail == NULL);   //pq->head ==NULL , pq->tail != NULL ,就是出问题了
		pq->tail = pq->head = newnode;
	}
	//非第一次入队
	else 
	{
		pq->tail->next = newnode; // 类似尾插
		pq->tail = newnode; // 更新tail 指针
	}
	pq->size++;
}


队列的销毁

需要注意的是保存下一个节点的地址

void QueueDestory(Queue* pq) //队列的销毁
{
	assert(pq);
	QueueNodeType * cur = pq->head;
	
	//遍历 
	while (cur)
	{
		QueueNodeType* next = cur->next;  //保存下一个节点的地址
		free(cur); //释放当前节点
		cur = next; //不能写成cur=cur->next 
	}
	  pq->tail = pq->head = NULL;
	pq->size = 0;
}



获取队列中有效元素个数

int QueueSize(Queue* pq)//获取队列中有效元素个数
{
	assert(pq);
	
	return pq->size;
}

判断队列是否为空

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

获取队列头部元素

QueueNodeTypeData QueueFront(Queue* pq) //获取队列头部元素
{
	assert(pq);
	assert(!QueueEmpty(pq)); //防止队列为空
	
	return pq->head->data;

}

获取队列尾部元素

QueueNodeTypeData QueueBack(Queue* pq) //获取队列尾部元素
{
	assert(pq);
	assert(!QueueEmpty(pq)); //防止队列为空

	return pq->tail->data;
}

完整代码

Queue.h

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>

typedef int   QueueNodeTypeData;

typedef struct  QueueNode
{
	struct  QueueNode* next;
	QueueNodeTypeData data;
}QueueNodeType;

typedef struct Queue
{
	QueueNodeType * tail; // 队尾
	QueueNodeType * head; //队头
	int size; 
} Queue;  // 链式结构：表示队列


void QueueInit(Queue* pq);  // 初始化  

void QueueDestory(Queue* pq); //队列的销毁

void QueuePush(Queue* pq , QueueNodeTypeData x );  // 队尾入队列

void QueuePop(Queue* pq); //队头出队列

int QueueSize(Queue* pq);//获取队列中有效元素个数

bool QueueEmpty(Queue* pq); // 判断队列是否为空 

QueueNodeTypeData QueueFront(Queue* pq); //获取队列头部元素

QueueNodeTypeData QueueBack(Queue* pq); //获取队列尾部元素

Queue.c

#include"Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueueDestory(Queue* pq) //队列的销毁
{
	assert(pq);
	QueueNodeType * cur = pq->head;
	
	//遍历 
	while (cur)
	{
		QueueNodeType* next = cur->next;  //保存下一个节点的地址
		free(cur); //释放当前节点
		cur = next; 
	}
	  pq->tail = pq->head = NULL;
	pq->size = 0;
}
void QueuePush(Queue* pq, QueueNodeTypeData x) // 入队 
{
	assert(pq);
	QueueNodeType* newnode =(QueueNodeType*) malloc( sizeof(QueueNodeType) );
	if (newnode == NULL)
	{
		printf(" malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//扩容成功

	//第一次入队
	if ( pq->head == NULL)
	{
   		assert(pq->tail == NULL);   //pq->head ==NULL , pq->tail != NULL ,就是出问题了
		pq->tail = pq->head = newnode;
	}
	else //非第一次入队
	{
		pq->tail->next = newnode; // 类似尾插
		pq->tail = newnode; // 更新tail 指针
	}
	pq->size++;
}
void QueuePop(Queue* pq) //队头出队列
{
	assert(pq);
	assert(pq->head != NULL); 

	//只有一个节点

	if (pq->head->next == NULL) 
	{
		free(pq->tail);  //出队
		pq->tail = pq->head = NULL;
	}
	// 多个节点
	else
	{
		QueueNodeType* next = pq->head->next; // 保存下一个节点的地址 
		free(pq->head); // 出队
		pq->head = NULL;
		pq->head = next;  //更新pq->head ，往后走 
	}
	pq->size--;
}


int QueueSize(Queue* pq)//获取队列中有效元素个数
{
	assert(pq);
	
	return pq->size;
}

//bool QueueEmpty(Queue* pq) // 判断队列是否为空 
//{
//	assert(pq);
//
//	if (pq->head == 0)
//	{
//		return true;
//	}
//	else
//	{
//		return false;
//	}
//}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

QueueNodeTypeData QueueFront(Queue* pq) //获取队列头部元素
{
	assert(pq);
	assert(!QueueEmpty(pq)); //防止队列为空
	
	return pq->head->data;

}

QueueNodeTypeData QueueBack(Queue* pq) //获取队列尾部元素
{
	assert(pq);
	assert(!QueueEmpty(pq)); //防止队列为空

	return pq->tail->data;
}

Test.c

#include"Queue.h"

void TestQueue1()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);


	QueueDestory(&q);

}
void TestQueue2()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);

	QueuePop(&q);
	QueuePop(&q);
	QueuePop(&q);


	QueueDestory(&q);
 }

void TestQueue3()
{
	Queue q; 
	QueueInit(&q); 
	QueuePush(&q, 1);
	
	QueueEmpty(&q);
	QueueDestory(&q);
}
void TestQueue4()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);

     QueueSize(&q);
	QueueDestory(&q);

 }
void TestQueue5()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);


	QueueFront(&q);

	QueueBack(&q);

	QueueDestory(&q);

}
int main()
{                  
	//TestQueue1();
	//TestQueue2();
	//TestQueue3();
	//TestQueue4();
	TestQueue5();


	return 0;
}

如果你觉得这篇文章对你有帮助，不妨动动手指给点赞收藏加转发，给鄃鳕一个大大的关注
你们的每一次支持都将转化为我前进的动力！！！

零基反复spanclasstoken数据结构链表算法

有关详细介绍栈和队列，适合零基础小白反复使用【数据结构】的更多相关文章

  1. ruby - 如何使用 Nokogiri 的 xpath 和 at_xpath 方法 - 2

    我正在学习如何使用Nokogiri，根据这段代码我遇到了一些问题:require'rubygems'require'mechanize'post_agent=WWW::Mechanize.newpost_page=post_agent.get('http://www.vbulletin.org/forum/showthread.php?t=230708')puts"\nabsolutepathwithtbodygivesnil"putspost_page.parser.xpath('/html/body/div/div/div/div/div/table/tbody/tr/td/div

  2. ruby - 使用 RubyZip 生成 ZIP 文件时设置压缩级别 - 2

    我有一个Ruby程序，它使用rubyzip压缩XML文件的目录树。gem。我的问题是文件开始变得很重，我想提高压缩级别，因为压缩时间不是问题。我在rubyzipdocumentation中找不到一种为创建的ZIP文件指定压缩级别的方法。有人知道如何更改此设置吗？是否有另一个允许指定压缩级别的Ruby库？ 最佳答案 这是我通过查看ruby​​zip内部创建的代码。level=Zlib::BEST_COMPRESSIONZip::ZipOutputStream.open(zip_file)do|zip|Dir.glob("**/*")d

  3. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  4. ruby-on-rails - 使用 Ruby on Rails 进行自动化测试 - 最佳实践 - 2

    很好奇，就使用ruby​​onrails自动化单元测试而言，你们正在做什么？您是否创建了一个脚本来在cron中运行rake作业并将结果邮寄给您？git中的预提交Hook？只是手动调用？我完全理解测试，但想知道在错误发生之前捕获错误的最佳实践是什么。让我们理所当然地认为测试本身是完美无缺的，并且可以正常工作。下一步是什么以确保他们在正确的时间将可能有害的结果传达给您？ 最佳答案 不确定您到底想听什么，但是有几个级别的自动代码库控制:在处理某项功能时，您可以使用类似autotest的内容获得关于哪些有效，哪些无效的即时反馈。要确保您的提

  5. ruby - 在 Ruby 中使用匿名模块 - 2

    假设我做了一个模块如下:m=Module.newdoclassCendend三个问题:除了对m的引用之外，还有什么方法可以访问C和m中的其他内容？我可以在创建匿名模块后为其命名吗(就像我输入“module...”一样)？如何在使用完匿名模块后将其删除，使其定义的常量不再存在？ 最佳答案 三个答案:是的，使用ObjectSpace.此代码使c引用你的类(class)C不引用m:c=nilObjectSpace.each_object{|obj|c=objif(Class===objandobj.name=~/::C$/)}当然这取决于

  6. ruby - 使用 ruby​​ 和 savon 的 SOAP 服务 - 2

    我正在尝试使用ruby​​和Savon来使用网络服务。测试服务为http://www.webservicex.net/WS/WSDetails.aspx?WSID=9&CATID=2require'rubygems'require'savon'client=Savon::Client.new"http://www.webservicex.net/stockquote.asmx?WSDL"client.get_quotedo|soap|soap.body={:symbol=>"AAPL"}end返回SOAP异常。检查soap信封，在我看来soap请求没有正确的命名空间。任何人都可以建议我

  7. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  8. ruby-on-rails - 'compass watch' 是如何工作的/它是如何与 rails 一起使用的 - 2

    我在我的项目目录中完成了compasscreate.和compassinitrails。几个问题:我已将我的.sass文件放在public/stylesheets中。这是放置它们的正确位置吗？当我运行compasswatch时，它不会自动编译这些.sass文件。我必须手动指定文件:compasswatchpublic/stylesheets/myfile.sass等。如何让它自动运行？文件ie.css、print.css和screen.css已放在stylesheets/compiled。如何在编译后不让它们重新出现的情况下删除它们？我自己编译的.sass文件编译成compiled/t

  9. ruby - 使用 ruby​​ 将 HTML 转换为纯文本并维护结构/格式 - 2

    我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h

  10. ruby - 在 64 位 Snow Leopard 上使用 rvm、postgres 9.0、ruby 1.9.2-p136 安装 pg gem 时出现问题 - 2

    我想为Heroku构建一个Rails3应用程序。他们使用Postgres作为他们的数据库，所以我通过MacPorts安装了postgres9.0。现在我需要一个postgresgem并且共识是出于性能原因你想要pggem。但是我对我得到的错误感到非常困惑当我尝试在rvm下通过geminstall安装pg时。我已经非常明确地指定了所有postgres目录的位置可以找到但仍然无法完成安装:$envARCHFLAGS='-archx86_64'geminstallpg--\--with-pg-config=/opt/local/var/db/postgresql90/defaultdb/po

随机推荐