// zhan.cpp : 定义控制台应用程序的入口点。
// #include "stdafx.h"
#include <iostream>
using namespace std;
typedef struct stacknode
{
int data;
struct stacknode *next;
}stacknode,*LinkStack; //判断栈为空
int StackEmpty(LinkStack &top)
{
if(top ->next == NULL)
return ;
else
return ;
} //入栈函数
LinkStack push(LinkStack &top,int value)
{
LinkStack p = new stacknode;
if(p != NULL)
{
p ->data = value;//可以理解为在链表尾部插入一个节点。
p ->next = top ->next;
top ->next = p;
}
else
cout << "没有内存可分配" << endl;
return top;
} //出栈函数
int pop(LinkStack &top)
{
LinkStack temp = new stacknode;
int data;
if(StackEmpty(top))
cout << "该栈为空！" << endl;
else
{
temp = top ->next;//可以理解为删除一个节点
data = temp ->data;
top ->next = temp ->next;
delete(temp);
}
return data;
} //打印函数
void Print(LinkStack &top)
{
LinkStack top1 = top; //时刻要注意，我们不可以改变链表本身的值及指向，不过我们可以找别人来完成此事。
if(top1 ->next == NULL)
cout << "该栈为空！"<< endl;
else
{
while(top1 ->next != NULL)
{
cout << top1->next ->data<< " ";//top本身data为0，此为不带头节点的链表
top1 = top1 ->next;
}
}
} //取栈顶元素
int StackTop(LinkStack &top)
{
LinkStack p = top;
if(StackEmpty(p))
cout << "该栈为空！" << endl;
else
{
return p ->next ->data;
} } //获得栈的长度
int StackLength(LinkStack &top)
{
int length = ;
LinkStack q = top;
while(q ->next != NULL)
{
length ++;
q = q ->next;
}
return length;
} //销毁栈
void DestroyStack(LinkStack &top)
{
LinkStack p;
while(top)
{
p = top ->next;//保存top的下一个位置。
delete top;
top = p;
}
cout << "销毁成功！" << endl;
} //栈的初始化
void InitStack(LinkStack &top)
{
top = new stacknode;
top ->next = NULL;
} //前导函数
void printscreen(void)
{
cout<<"0------退出程序"<<endl
<<"1------入栈操作"<<endl
<<"2------出栈操作"<<endl
<<"3------取栈顶元素"<<endl
<<"4------判断栈是否为空"<<endl
<<"5------返回栈的元素个数"<<endl
<<"6------初始化栈"<<endl
<<"7------显示栈"<<endl
<<"8------销毁栈"<<endl
<<"9------退出程序"<<endl;
} int main()
{
LinkStack top = NULL;
InitStack(top);
printscreen();
int n,value;
cin >> n;
while(n) //输入0也可以退出循环
{
switch(n)
{
case : //入栈操作
cout << "请输入一个整数" <<endl;
cin >> value;
while(value!=) //以0作为结束条件
{
push(top,value);
cin >> value;
}
Print(top); //打印栈
cout << endl;
break;
case : //出栈操作
if(top ->next != NULL)
cout << "弹出的元素是："<< pop(top) << endl;
break;
case : //取栈顶元素
cout << StackTop(top) << endl;
break;
case : //判断栈是否为空
if(StackEmpty(top))
cout << "该栈为空！" << endl;
else
cout << "该栈不为空！" << endl;
break;
case : //返回栈的元素个数
if(StackEmpty(top) == )
cout << StackLength(top)<<endl;
break;
case : //初始化栈
InitStack(top);
cout << endl;
break;
case ://显示栈
Print(top); //打印栈
cout << endl;
break;
case : //销毁栈
DestroyStack(top);
cout << endl;
break;
case :
goto end;
default:
cout << "不合法的输入，请重新输入"<< endl;
}
printscreen();
cin >> n;
}
end: ;
return ;
}
实验二
实验名称：栈的基本操作
实验目的：掌握栈的结构特点并熟悉栈的基本操作。
实验要求：编程实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成如下功能：
1、 采用链式存储实现栈的初始化、判空、入栈、出栈操作。
实验步骤及内容：
1、首先建立一个定义多项式的结构体stacknode，及结构体指针LinkStack，该结构体包含一个数据域data，一个指向下一项的指针*next,代码如下：
typedef struct stacknode
{
int data;
struct stacknode *next;
}stacknode,*LinkStack;
2、栈的初始化，代码如下：
//栈的初始化
void InitStack(LinkStack &top)
{
top = new stacknode;
top ->next = NULL;
}
3、入栈，首先开辟内存空间，并将新开辟的结点插入在此栈的后面。具体的代码如下：
//入栈函数
LinkStack push(LinkStack &top,int value)
{
LinkStack p = new stacknode;
if(p != NULL)
{
p ->data = value;//可以理解为在链表尾部插入一个节点。
p ->next = top ->next;
top ->next = p;
}
else
cout << "没有内存可分配" << endl;
return top;
}
5、出栈，从栈中删除一个结点。首先我们必须开辟一个结点用来存储top结点的下一个结点，然后将top->next 执行下下一个结点，这样就删除了一个结点。
int pop(LinkStack &top)
{
LinkStack temp = new stacknode;
int data;
if(StackEmpty(top))
cout << "该栈为空！" << endl;
else
{
temp = top ->next;//可以理解为删除一个节点
data = temp ->data;
top ->next = temp ->next;
delete(temp);
}
return data;
}
6、打印栈，此函数用来对栈进行输出验证。
//打印函数
void Print(LinkStack &top)
{
LinkStack top1 = top; //时刻要注意，我们不可以改变链表本身的值及指向，不过我们可以找别人来完成此事。
if(top1 ->next == NULL)
cout << "该栈为空！"<< endl;
else
{
while(top1 ->next != NULL)
{
cout << top1->next ->data<< " ";//top本身data为，此为不带头节点的链表
top1 = top1 ->next;
}
}
}
7、去栈顶元素，如果不为空则取出栈顶元素。
//取栈顶元素
int StackTop(LinkStack &top)
{
LinkStack p = top;
if(StackEmpty(p))
cout << "该栈为空！" << endl;
else
{
return p ->next ->data;
}
}
8、获取栈的长度，必须临时开辟一个新的结构体指针，作为top的副本，这样就不会破坏top本身的结构了，而且对于top的副本，我们也不能对其空间进行释放，不然top的最后一个next不会为NULL，而是一个不确定的值，这样对以后的操作造成破坏。
//获得栈的长度
int StackLength(LinkStack &top)
{
int length = 0;
LinkStack q = top;
while(q ->next != NULL)
{
length ++;
q = q ->next;
}
return length;
}
9、销毁栈，就是从栈顶开始一个节点一个节点的释放。
//销毁栈
void DestroyStack(LinkStack &top)
{
LinkStack p;
while(top)
{
p = top ->next;//保存top的下一个位置。
delete top;
top = p;
}
cout << "销毁成功！" << endl;
}
链表可以往后插，也可以往前插。
如果我们用 每次往后用p - > next = NULL;叫做 往后插。