目录

前言

一.链栈的定义 

二、链栈的c++语言结构描述表示

三、链栈中基本操作的实现 

3.1链栈的初始化

3.2判断链栈是否为空 

3.3求链栈的长度 

3.4 链栈的入栈

3.4 链栈的出栈

3.5求栈顶元素 

3.6销毁栈

四.链栈的具体实现 

五.测试结果

六、总结 

---

前言

本文参考王卓老师的数据结构视频和严蔚敏老师的《数据结构》

一.链栈的定义 

栈：操作受限的线性表，限定仅在表尾进行插入和删除操作的线性表，即后进先出。这一端被称为栈顶，相对地，把另一端称为栈底。

链栈：用链式结构存储的栈（我实际用的是不带头结点的单链表）

例子：类似子弹压入弹夹，后放入的子弹可以先从弹夹弹出来。

二、链栈的c++语言结构描述表示

代码如下（示例）：

注意：我使用的是不带头节点的单链表

typedef struct LinkNode{
    int data;//数据域
    struct LinkNode *next;//指针域 
}stackNode,*LinkStack; 

三、链栈中基本操作的实现 

3.1链栈的初始化

无需new，因为我是不带头结点的单链表

void initStack(LinkStack &s)
{
	s=NULL;//不需要头节点 
}

3.2判断链栈是否为空 

当s==NULL时，栈为空，则返回1；否则，返回0 

int stackEmpty(LinkStack s)
{
	if(s==NULL)
		return 1;
	return 0;
}

3.3求链栈的长度 

长度表示有多少个节点

int stackLength(LinkStack s)
{
	int sum=0;
	stackNode *temp=s;
	while(temp!=NULL)
	{
		sum++;
		temp=temp->next;
	}
	return sum;
}

3.4 链栈的入栈

p是新节点

关键处在于当栈为空的时候，p就是第一个节点；而当栈不为空时，则让p的next指针指向s，而s更新到p节点，相当于还是让p作为第一个节点

void push(LinkStack &s,int e)
{
	stackNode *p=new stackNode;
	p->data=e;
	p->next=NULL;
	if(s==NULL)
		s=p;
	else
	{
		p->next=s;
		s=p;
	}
}

3.4 链栈的出栈

当栈为空的时候，是无法弹出的

new一个p节点

而当栈不空时，则让p指向s的第一个节点，更新s，使s指向下一个节点，在删掉p

void pop(LinkStack &s,int &e)
{
	stackNode *p=new stackNode;
	if(s==NULL)
	{
		cout<<"栈为空，无法弹出"<<endl;
	}
	else
	{
		p=s;
		e=p->data;
		s=s->next;
		delete p;
		cout<<"成功弹出栈顶元素"<<endl;
	}
}

3.5求栈顶元素 

 当栈不空时，返回第一个节点的数据

int top(LinkStack s)
{
	if(s==NULL)
		return -1;
	return s->data;
}

3.6销毁栈

void DestoryStack(LinkStack &S)
{
	stackNode *p;
	while(S)
	{
		p=S;
		S=S->next;
		delete p;
	}
	S=NULL;
	cout<<"成功销毁"<<endl;
}

四.链栈的具体实现 

#include <iostream>
using namespace std;
//不带头节点的 
typedef struct LinkNode{
	int data;//数据域
	struct LinkNode *next;//指针域 
}stackNode,*LinkStack;
void initStack(LinkStack &s)
{
	s=NULL;//不需要头节点 
}
int stackEmpty(LinkStack s)
{
	if(s==NULL)
		return 1;
	return 0;
}
int stackLength(LinkStack s)
{
	int sum=0;
	stackNode *temp=s;
	while(temp!=NULL)
	{
		sum++;
		temp=temp->next;
	}
	return sum;
}
void push(LinkStack &s,int e)
{
	stackNode *p=new stackNode;
	p->data=e;
	p->next=NULL;
	if(s==NULL)
		s=p;
	else
	{
		p->next=s;
		s=p;
	}
}
void pop(LinkStack &s,int &e)
{
	stackNode *p=new stackNode;
	if(s==NULL)
	{
		cout<<"栈为空，无法弹出"<<endl;
	}
	else
	{
		p=s;
		e=p->data;
		s=s->next;
		delete p;
		cout<<"成功弹出栈顶元素"<<endl;
	}
}
int top(LinkStack s)
{
	if(s==NULL)
		return -1;
	return s->data;
}

//销毁栈 
//所有节点
void DestoryStack(LinkStack &S)
{
	stackNode *p;
	while(S)
	{
		p=S;
		S=S->next;
		delete p;
	}
	S=NULL;
	cout<<"成功销毁"<<endl;
}

void menu()
{
	cout<<"**************************"<<endl;
	cout<<"1.初始化"<<endl;
	cout<<"2.判断栈是否为空"<<endl;
	cout<<"3.求栈的长度"<<endl;
	cout<<"4.销毁栈"<<endl;
	cout<<"5.入栈"<<endl;
	cout<<"6.出栈"<<endl;
	cout<<"7.求栈顶元素"<<endl;
	cout<<"8.退出"<<endl;
	cout<<"**************************"<<endl;
}
int main()
{
	int choice;
	LinkStack s;
	int e1,e2;
	while(1)
	{
		menu();
		cin>>choice;
		switch(choice)
		{
			case 1:
				initStack(s);
				cout<<"初始化成功"<<endl;
				break;
			case 2:
				if(stackEmpty(s))
					cout<<"栈为空"<<endl;
				else
					cout<<"栈不为空"<<endl; 
				break;
			case 3:
				cout<<"栈的长度为"<<stackLength(s)<<endl;
				break;
			case 4:
				DestoryStack(s);
				break;
			case 5:
				cout<<"请输入想要入栈的元素值："<<endl;
				cin>>e1;
				push(s,e1);
				cout<<"入栈成功"<<endl; 
				break;	
			case 6:
				pop(s,e2);
				cout<<"弹出的元素为"<<e2<<endl;
				break;
			case 7:
				if(top(s)!=-1)
					cout<<"栈顶元素为"<<top(s)<<endl;
				else
					cout<<"栈为空"<<endl;
				break;
			case 8:
				cout<<"成功退出"<<endl;
				exit(0);
			default:
				cout<<"输入有误，请重新输入"<<endl;
				break;			
		}	
	}
}

五.测试结果

        图一

 

        图二 

 

         图三

        图四

 

        图五

 

        图六

 

        图七

六、总结 

        栈是一种操作受限的线性表，虽然操作受限，但是与线性表有点类似，只不过栈的插入和删除都在表尾而已。我实现的链栈其实与不带头节点的链表有很大关系，各位也可以参考下链表来学习链栈。