栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

(8)顺序栈和链栈

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

(8)顺序栈和链栈

顺序栈

顺序栈是指利用顺序存储结构实现的栈,即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时设有指针top指示栈顶元素在顺序栈中的位置;另设指针base指示栈底元素在顺序栈中的位置。当top和base的值相等时,表示空栈。

#include 
#include 
#include 

#define MAXSIZE 20

typedef struct {
	int nData[MAXSIZE];
	int nTop;
}RkStack;

//初始化栈
bool InitStack(RkStack * Stack)
{
	Stack->nTop = -1;
	return true;
}

//清理栈
bool ClearStack(RkStack * Stack)
{
	Stack->nTop = -1;
	return true;
}

// 判断栈是否为空
bool StackEmpty(RkStack Stack)
{
	if (Stack.nTop == -1)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//或取栈的长度
int StackLength(RkStack Stack)
{
	return Stack.nTop + 1;
}

//栈顶
int GetTop(RkStack Stack, int * nData)
{
	if (Stack.nTop == -1)
	{
		return false;
	}
	else
	{
		*nData = Stack.nData[Stack.nTop]; 
	}
}

//push
bool push(RkStack * Stack, int nData)
{
	if (Stack->nTop == MAXSIZE - 1)
	{
		return false;
	}
	else
	{
		Stack->nTop++;
		Stack->nData[Stack->nTop] = nData;
		return true;
	}
}
//pop
bool pop(RkStack * Stack, int *nData)
{
	if (Stack->nTop == -1)
	{
		return false;
	}
	else
	{
		*nData = Stack->nData[Stack->nTop];
		Stack->nTop--;
		return true;
	}
}

//打印数据
bool ShowStack(RkStack Stack)
{
	if (Stack.nTop == -1)
	{
		return false;
	}
	for (size_t i = 0; i < Stack.nTop; i++)
	{
		printf("Stack value = %dn", Stack.nData[i]);
	}
	return true;
}
int main()
{
	RkStack rkStack;
	InitStack(&rkStack);
	for (size_t i = 0; i < 10; i++)
	{
		push(&rkStack, i);
	}
	ShowStack(rkStack);
	int nData = 0;
	pop(&rkStack, &nData);
	printf("pop value = %dn", nData);
	//ShowStack(rkStack);
	GetTop(rkStack, &nData);
	printf("GetTop = %dn", nData);
	int Size = StackLength(rkStack);
	printf("StackLength = %dn", Size);
	ClearStack(&rkStack);
	bool nFlag = StackEmpty(rkStack);
	if (nFlag)
	{
		printf("Emptyn");
	}
	system("pause");
	return 0;
}
链栈

链栈是指采用链式存储结构实现的栈,通常链栈用单链表表示。
没有特殊要求,顺序栈比链栈更实用。

#include 
#include 
#include 


typedef struct _StackNode
{
	int nData;
	struct _StackNode *next;
}StackNode,*PStackNdoe;

typedef struct RkStack {
	PStackNdoe top;
	int count;
};

//初始化栈
bool InitStack(struct RkStack * Stack)
{
	Stack->top = (PStackNdoe)malloc(sizeof(StackNode));
	if (!Stack->top)
	{
		return false;
	}
	Stack->top = NULL;
	Stack->count = 0;
	return true;
}

//清理栈
bool ClearStack(struct RkStack * Stack)
{
	PStackNdoe TempNode1;
	PStackNdoe TempNode2;
	TempNode1 = Stack->top;
	while (TempNode1)
	{
		TempNode2 = TempNode1;
		TempNode1 = TempNode1->next;
		free(TempNode2);
	}
	Stack->count = 0;
}

// 判断栈是否为空
bool StackEmpty(struct RkStack Stack)
{
	if (Stack.count == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//或取栈的长度
int StackLength(struct RkStack Stack)
{
	return Stack.count;
}

//栈顶
int GetTop(struct RkStack Stack, int * nData)
{
	if (Stack.top == NULL)
	{
		return false;
	}
	else
	{
		*nData = Stack.top->nData;
		return true;
	}
}

//push
bool push(struct RkStack * Stack, int nData)
{
	PStackNdoe mStackNode = (PStackNdoe)malloc(sizeof(StackNode));
	mStackNode->nData = nData;
	mStackNode->next = Stack->top;
	Stack->top = mStackNode;
	Stack->count++;
	return true;
}
//pop
bool pop(struct RkStack * Stack, int *nData)
{
	PStackNdoe mStackNode;
	if (StackEmpty(*Stack))
	{
		return false;
	}
	else
	{
		*nData = Stack->top->nData;
		mStackNode = Stack->top;
		Stack->top = Stack->top->next;
		free(mStackNode);
		Stack->count--;
		return true;
	}
}

//打印数据
bool ShowStack(struct RkStack Stack)
{
	PStackNdoe mStackNode;
	mStackNode = Stack.top;
	while (mStackNode)
	{
		printf("value = %dn", mStackNode->nData);
		mStackNode = mStackNode->next;
	}
	return true;
}
int main()
{
	struct RkStack rkStack;
	int nData;
	InitStack(&rkStack);
	for (size_t i = 0; i < 10; i++)
	{
		push(&rkStack, i);
	}
	ShowStack(rkStack);

	pop(&rkStack, &nData);
	printf("pop value = %dn", nData);
	ShowStack(rkStack);

	GetTop(rkStack, &nData);
	printf("Get top value = %dn", nData);

	ClearStack(&rkStack);
	if (StackEmpty(rkStack))
	{
		printf("Empty!n");
	}
	system("pause");
	return 0;
}
区别

顺序栈和链栈区别如下:

  1. 存储结构不同,顺序栈是静态分配的,而链栈则是动态分配的,链栈可以将很多零碎的空间利用起来,容量可变,节省空间,顺序栈则固定内存空间,容量不变。
  2. 使用方面,顺序栈查询速度快,链栈添加删除数据更快。
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/985444.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号