C++数据结构笔记（6）栈的链式存储结构

对于栈的链式存储结构，实现原理本质上是受限的链表；此外与顺序存储不同的是，链式结构选用左边（头结点）作为栈的顶部，这样的好处是只要找到头结点即可实现插入元素等操作。

LinkStack.h头文件

#ifndef LINKSTACK_H
#define LINKSTACK_H

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

//结点 
typedef struct LinkNode{
	struct LinkNode* next;
}LinkNode;
//链式栈 
typedef struct LinkStack{
	LinkNode head;
	int size;
}LinkStack;
//初始化
LinkStack* Init_LinkStack(); 
//入栈 
void Push_LinkStack(LinkStack* stack,LinkNode* data);
//出栈 
void Pop_LinkStack(LinkStack* stack);
//返回栈顶元素 
LinkNode* Top_LinkStack(LinkStack* stack);
//返回栈元素的个数 
int Size_LinkStack(LinkStack* stack);
//清空栈
void Clear_LinkStack(LinkStack* stack); 
//销毁栈 
void FreeSpace_LinkStack(LinkStack* stack);


#endif 

LinkStack.c文件

初始化

LinkStack* Init_LinkStack(){
	
	LinkStack* stack =(LinkStack*)malloc(sizeof(LinkStack));
	stack->head.next=NULL;
	stack->size=0;
	
	return stack;
} 

入栈 

void Push_LinkStack(LinkStack* stack,LinkNode* data){
	if(stack==NULL)
		return;
	if(data==NULL)
		return;
	data->next=stack->head.next;
	stack->head.next=data;
	stack->size++;
}

出栈 

void Pop_LinkStack(LinkStack* stack){
	if(stack==NULL)
		return;
	
	if(stack->size==0)
		return; 
	//直接跃迁到第二个结点即可	
	LinkNode* pNext=stack->head.next;
	stack->head.next=pNext->next;
	stack->size--;
}

返回栈顶元素 
 

LinkNode* Top_LinkStack(LinkStack* stack){
	if(stack==NULL)
		return NULL;
	return stack->head.next;
}

返回栈元素的个数 

int Size_LinkStack(LinkStack* stack){
	if(stack==NULL)
		return 0;
	return stack->size;
}

清空栈

void Clear_LinkStack(LinkStack* stack){
	if(stack==NULL)
		return;
	stack->head.next=NULL;
	stack->size=0;
	//只需要清零即可，不需要关心内存的问题 
}

销毁栈 
 

void FreeSpace_LinkStack(LinkStack* stack){
	if(stack==NULL)
		return;
	free(stack); 
}

main.cpp文件

#include <iostream>
#include <string.h>
#include "LinkStack.h"
using namespace std;

typedef struct test{
	LinkNode node;
	int num;
	string name;
}test;


int main(int argc, char** argv) {
	
	LinkStack* stack =Init_LinkStack();
	test t1,t2;
	t1.name="JSL";
	t1.num=7371;
	t2.name="HYH";
	t2.num=7166;

	Push_LinkStack(stack,(LinkNode*)&t1);
	Push_LinkStack(stack,(LinkNode*)&t2);
	
	cout<<"栈中元素的个数为："<<(Size_LinkStack(stack))<<endl;
	
	while(Size_LinkStack(stack)>0)
	{
		test* tt=(test*)Top_LinkStack(stack);
		cout<<(tt->name)<<"is"<<(tt->num)<<endl;
		Pop_LinkStack(stack);
	}

	FreeSpace_LinkStack(stack);
	
	return 0;
}

运行结果如下：