棧的鍊式存儲結構——C語言

鍊式存儲結構最大的好處就是沒有空間的限制，通過指針指向将結點像一個鍊子一樣把結點連結，那麼棧的同樣可以用于鍊式存儲結構。

棧因為隻是棧頂來做插入和删除操作，是以比較好的方法就是将棧頂放在單連結清單的頭部（與順序棧相反），棧頂指針和單連結清單的頭指針合二為一。

另外棧頂在頭部了，那麼單連結清單的頭結點也就失去了意義，通常對于鍊棧來說，是不需要頭結點的。

同樣對于鍊棧來說，基本不存在棧滿的情況，除非記憶體已經沒有可用的空間了。

下面是鍊棧的指向圖：

同樣鍊棧中最重要的算法是壓棧和彈棧。

代碼實作：

//棧頂放在連結清單的頭部，棧頂指針和頭指針合二。
//另外棧頂在頭部，單連結清單的頭結點也就失去了意義。
//對于鍊棧來說，基本不存在棧滿的情況，除非記憶體已經沒有可用的空間了。
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef int ElemType;
typedef struct Node
{
	ElemType data;
	struct Node *next;
}StackNode, *LinkStackpoi;

typedef struct LinkStack
{
	LinkStackpoi top;
	int count; //元素個數
}LinkStack;

//鍊棧的初始化
bool InitLinkStack(LinkStack *s)
{
	if (!s)
	{
		return false;
	}
	s->top = NULL;
	s->count = 0;
	return true;
}

//壓棧
void push(LinkStack *s, ElemType e)
{
	if (!s)
	{
		exit(0);
	}
	StackNode *p = (StackNode*)malloc(sizeof(StackNode));
	p->next = s->top;
	s->top = p;
	p->data = e;
	s->count++;
	//頭插法
}

//出棧
void pop(LinkStack *s, ElemType &e)
{
	if (!(s && s->count))
	{
		exit(0);
	}
	StackNode *p = s->top;
	e = p->data;
	s->top = p->next;
	free(p);
	s->count--;
}

//清空棧
void clear(LinkStack *s)
{
	if (!(s && s->count))
	{
		printf("棧原本已清空\n");
		exit(0);
	}
	while (s->count)
	{
		StackNode *p = s->top;
		s->top = p->next;
		free(p);
		s->count--;
	}
}

//顯示站内元素
void display(LinkStack *s)
{
	if (!(s && s->count))
	{
		exit(0);
	}
	StackNode* p = s->top;
	while (p)
	{
		printf("%d,", p->data);
		p = p->next;
	}
}

int main()
{
	int c, countsize;
	ElemType elem;
	LinkStack stack;
	InitLinkStack(&stack);
	printf("輸傳入連結棧的元素個數為:\n");
	scanf("%d", &countsize);
	for (int i = 0; i < countsize; i++)
	{
		printf("輸入元素:\n");
		scanf("%d", &c);
		push(&stack, c);
	}
	printf("棧内的元素為：\n");
	display(&stack);
	pop(&stack, elem);
	printf("出棧的元素為:%d\n", elem);
	printf("棧内的元素為：\n");
	display(&stack);
	clear(&stack);
	system("pause");
	return 0;
}
           

運作結果：