本程序主要体现了线性表的链式存储结构,主要实现了以下几个功能:
//压栈
//出栈
//取栈顶
//判断栈是否为空
下面是代码,如有不足的地方还请各位大佬多多指正:
//数据结构学习笔记(C++):栈的链式存储结构
#include<iostream>
using namespace std;
class linkStack{
public:
struct Node
{
int data;
Node *next;
};
public:
linkStack();//构造函数
~linkStack();//析构函数
public:
void Push(int x);//压栈
int Pop();//弹栈
int getTop();//取栈顶
bool isEmpty();//判空函数
private:
Node *top;//栈帧
};
//1
linkStack::linkStack()//构造函数
{
//因为链栈是不具有头节点的,所以直接让栈帧为空即可
top = NULL;
}
//2
linkStack::~linkStack()//析构函数
{
Node* p = NULL;//定义工作指针
while(top!=NULL)
{
p = top;
top = top->next;
delete p;
}
}
//3
void linkStack::Push(int x)//压栈操作
{
Node *s = NULL;
s = new Node;
s->data = x;
s->next = top;
top = s;
}
//4
int linkStack::Pop()//弹栈操作
{
Node *p = NULL;
int x;
if(top == NULL) throw "下溢";
x = top->data;
p = top;
top = top->next;
delete p;
return x;
}
//5
int linkStack::getTop()//取栈顶
{
return top->data;
}
//6
bool linkStack::isEmpty()//判断栈是否为空
{
if(top == NULL)
return true;
else
return false;
}
int main()
{
linkStack stack;
char command;
int x;
try{
while(cin>>command)
{
if(command == 'Q')
return 0;
switch(command)
{
case 'P'://压栈
cout<<"输入要压入的元素";
cin>>x;
stack.Push(x);
cout<<"压栈完成。"<<endl;
break;
case 'C'://出栈
cout<<stack.Pop()<<endl;
break;
case 'G'://取栈顶
cout<<stack.getTop()<<endl;
break;
case 'E'://判断栈是否为空
cout<<(stack.isEmpty()?"yes":"no")<<endl;
break;
}
}
}catch(const char * str)
{
cout<<str<<endl;
}
return 0;
}