（浙大MOCC學習筆記）堆棧的鍊式存儲

堆棧的鍊式存儲與單連結清單類似，但其操作收到限制，插入和删除都僅僅在鍊棧的棧頂進行。

棧頂指針Top，就是表頭結點後的第一個結點，我們将它定位棧頂結點

棧底結點的Next為NULL，可依據此關系對堆棧進行周遊

下面是堆棧的鍊式存儲主要操作的基本實作

包括：

1）Stack CreateStack(Stack S):生成空堆棧

2）bool Push(Stack S,ElementType X):将元素X壓入堆棧，即壓入表頭的後一個結點

3）bool IsEmpty(Stack S):鍊式存儲的堆棧隻存在空這個狀态，不存在滿（我也不知道這話對不對，感覺并不嚴謹）

4）ElementType Pop(Stack S):删除并傳回棧頂元素（涉及棧頂結點的釋放）

5）int StackLength(Stack S):傳回堆棧中元素的個數

6）Stack StackPrint(Stack S):從棧頂到棧底輸出堆棧中的各個元素

代碼如下：

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

#define Error -1
typedef int ElementType;
typedef struct SNode* PtrToNode;
struct SNode
{
	ElementType Data;
	PtrToNode Next;
};

typedef PtrToNode Stack;

Stack CreateStack()
{
	Stack S = (Stack)malloc(sizeof(struct SNode));
	S->Next = NULL;
	return S;
}

bool Push(Stack S, ElementType X)
{
	Stack TmpCell = (Stack)malloc(sizeof(struct SNode));
	TmpCell->Data = X;
	TmpCell->Next = S->Next;
	S->Next = TmpCell;
	return true;
}

bool IsEmpty(Stack S)
{
	return (S->Next == NULL);
}

ElementType Pop(Stack S)
{
	if (IsEmpty(S))
	{
		printf("堆棧空\n");
		return Error;
	}

	Stack TmpCell = (Stack)malloc(sizeof(struct SNode));
	ElementType X;
	TmpCell = S->Next;
	X = TmpCell->Data;
	S->Next = TmpCell->Next;
	free(TmpCell);
	return X;
}

int StackLength(Stack S)
{
	Stack TempCell = (Stack)malloc(sizeof(struct SNode));
	TempCell = S;
	int cnt = 0;
	while (TempCell->Next != NULL)
	{
		TempCell = TempCell->Next;
		cnt++;
	}
	return cnt;
}
void StackPrint(Stack S)
{
	if (S->Next == NULL)
	{
		printf("堆棧是空的\n");
		return;
	}
	printf("堆棧内從棧頂到棧底的元素分别為\n");
	Stack TempCell = (Stack)malloc(sizeof(struct SNode));
	TempCell = S->Next;
	while (TempCell != NULL)
	{
		printf("%d ", TempCell->Data);
		TempCell = TempCell->Next;
	}
	printf("\n");
}

int main()
{
	Stack S = CreateStack();

	StackPrint(S);

	printf("請輸入要壓進堆棧的元素的個數：\n");
	int num;
	scanf("%d", &num);
	printf("請輸入要壓進堆棧的各個元素： \n");
	while (num--)
	{
		int number;
		scanf("%d", &number);
		Push(S, number);
	}
	printf("彈入後堆棧内的元素的個數為：%d\n", StackLength(S));
	StackPrint(S);

	printf("此時堆棧内的元素的個數為：%d\n", StackLength(S));

	int length = StackLength(S);
	printf("從棧頂到棧底依次彈出的元素為： \n");
	while (length--)
	{
		int elem;
		printf("%d ", Pop(S));
	}
	printf("\n");
	printf("彈出後堆棧内的元素的個數為：%d\n", StackLength(S));
	printf("\n");
	return 0;
}