（8）顺序栈和链栈

顺序栈

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

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

#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 = %d\n", 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 = %d\n", nData);
	//ShowStack(rkStack);
	GetTop(rkStack, &nData);
	printf("GetTop = %d\n", nData);
	int Size = StackLength(rkStack);
	printf("StackLength = %d\n", Size);
	ClearStack(&rkStack);
	bool nFlag = StackEmpty(rkStack);
	if (nFlag)
	{
		printf("Empty\n");
	}
	system("pause");
	return 0;
}

链栈

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

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


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 = %d\n", 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 = %d\n", nData);
	ShowStack(rkStack);

	GetTop(rkStack, &nData);
	printf("Get top value = %d\n", nData);

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

区别

顺序栈和链栈区别如下：

1. 存储结构不同，顺序栈是静态分配的，而链栈则是动态分配的，链栈可以将很多零碎的空间利用起来，容量可变，节省空间，顺序栈则固定内存空间，容量不变。
2. 使用方面，顺序栈查询速度快，链栈添加删除数据更快。