鍊棧的基本運算

//main.cpp
#include"linkstack.h"
int main()
{
	linkstack top;
	int i = 0;
	int data = 0;
	top = creat_stack();
	for (i = 5; i > 0; i--)
	{
		push_stack(top, i);
	}
	show_stack(top);
	/*while (empty_stack(top))
    {
		printf("目前棧内元素為:%-4d", top->next->data);
	}*/	
	data=get_stack(top);
	printf("目前棧頂元素為:%d\n", data);

	pop_stack(top);

	show_stack(top);

	data = get_stack(top);
	printf("目前棧頂元素為:%d\n", data);

	//printf("目前棧内元素為:%-4d", top->next->data);
	celar_stack(top);
	if (empty_stack(top))
	{
		printf("目前棧為空:\n");
	}
	free_stack(top);
	system("pause");
	return 0;
}
//linkstack.cpp
#include"linkstack.h"
/*
 * @file      linkstack.cpp
 * @function  建立一個空鍊棧函數
 * @author    酸菜。
 * @date      2019-10-29
*/
linkstack creat_stack()
{
	linkstack s = NULL;
	s = (linkstack)malloc(sizeof(linknode));
	if (s == NULL)
	{
		printf("鍊棧建立失敗:\n");
		return NULL;
	}

	s->data = 0;
	s->next = NULL;
	return s;
}
/*
 * @file      linkstack.cpp
 * @function  釋放鍊棧函數
 * @author    酸菜。
 * @date      2019-10-29
*/
void free_stack(linkstack top)
{
	linkstack p = NULL;

	p = top;
	while (p)
	{
		top = top->next;
		free(p);
		p = top;
	}
	return;
}
/*
 * @file      linkstack.cpp
 * @function  清空鍊棧函數
 * @author    酸菜。
 * @date      2019-10-29
*/
void celar_stack(linkstack top)
{
	linkstack p = NULL;

	p = top->next;
	while (p)
	{
		top->next = p->next;
		free(p);
		p = top->next;
	}
	return;
}
/*
 * @file      linkstack.cpp
 * @function  判斷鍊棧是否為空
 * @author    酸菜。
 * @date      2019-10-29
*/
int empty_stack(linkstack top)
{

	return (top->next == NULL ? 1 : 0);

}
/*
 * @file      linkstack.cpp
 * @function  出棧函數
 * @author    酸菜。
 * @date      2019-10-29
*/
int pop_stack(linkstack top)
{
	linkstack p;
	int data = 0;

	p = top->next;
	top->next = p->next;

	data = p->data;
	free(p);
	p = NULL;

	return data;
}
/*
 * @file      linkstack.cpp
 * @function  進棧函數
 * @author    酸菜。
 * @date      2019-10-29
*/
int push_stack(linkstack top, int value)
{
	linkstack p = NULL;

	p = (linkstack)malloc(sizeof(linknode));
	if (p == NULL)
	{
		printf("壓棧失敗:\n");
		return -1;
	}
	p->data = value;

	p->next = top->next;
	top->next = p;

	return 1;
}
/*
 * @file      linkstack.cpp
 * @function  擷取棧頂元素
 * @author    酸菜。
 * @date      2019-10-29
*/
int get_stack(linkstack top)
{
	if (top->next == NULL)
	{
		printf("棧為空:無法擷取棧頂元素\n");
		return -1;
	}

	return top->next->data;
}
/*
 * @file      linkstack.cpp
 * @function  周遊棧函數
 * @author    酸菜。
 * @date      2019-10-29
*/
void show_stack(linkstack top)
{
	while (top&&top->next)
	{
		printf("目前棧内元素為:%-4d\n", top->next->data);
		top = top->next;
	}
}

//linkstack.h
#ifndef   linkstack_h
#define   linkstack_h

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
typedef struct linknode
{
	int data;
	struct linknode* next;
}linknode,*linkstack;

extern linkstack creat_stack();
extern void free_stack(linkstack top);
extern void celar_stack(linkstack top);
extern int empty_stack(linkstack top);
extern int pop_stack(linkstack top);
extern int push_stack(linkstack top, int value);
extern int get_stack(linkstack top);
extern void show_stack(linkstack top);

#endif // !linkstack_h

           

注：和順序棧相比，鍊棧沒有判斷棧滿的操作。

順序棧：實作需要使用數組，數組的元素在記憶體中的存儲位置是連續的；且需要知道數組的長度才可以使用；無法避免溢出問題；當系統給數組配置設定了記憶體空間，其他的任務是不能使用這個記憶體空間的；存儲密度=1；順序棧的top指針指向的是棧頂的空元素處，top-1才是指向棧頂元素；不易實作插入和删除操作。

鍊棧：實作使用連結清單，連結清單的元素存儲在不同的位址；動态申請位址，即可以以非常小的記憶體空間開始；當某項不使用記憶體時，可以将記憶體返還給系統；存儲密度<1；鍊棧的top指針相當于連結清單中的head指針，即指向實在的元素；相比于順序棧易實作插入和删除操作且不易出現棧滿的情況。

鍊棧存儲示意圖：