#include<bits/stdc++.h>
using namespace std;
typedef struct Node{
int data;
struct Node *left;
struct Node *right;
}Node;
class LinkStack{
private:
Node *top;
public:
LinkStack();
~LinkStack();
void push(int x,string choice);
int pop(string choice);
int getTop(string choice);
bool isEmpty(string choice);
};
LinkStack::LinkStack()
{
top=new Node;
top->left=NULL;
top->right=NULL;
}
LinkStack::~LinkStack()
{
Node *q=top->left;
Node *p;
while(q!=NULL){
p=q->left;
delete q;
q=p;
}
Node *k=top->right;
Node *l;
while(k!=NULL){
l=k->right;
delete k;
k=l;
}
}
void LinkStack::push(int x,string choice)
{
Node *q=new Node;
if(choice=="left"){
q->data=x;
q->left=top->left;
top->left=q;
}
if(choice=="right"){
q->data=x;
q->right=top->right;
top->right=q;
}
}
int LinkStack::pop(string choice)
{
int x;
if(choice=="left"){
Node *q=top->left;
if(!isEmpty(choice)){
x=q->data;
top->left=q->left;
delete q;
return x;
}
}
if(choice=="right"){
Node *q=top->right;
if(!isEmpty(choice)){
x=q->data;
top->right=q->right;
delete q;
return x;
}
}
}
int LinkStack::getTop(string choice)
{
if(choice=="left"){
if(!isEmpty(choice)){
return top->left->data;
}
}
if(choice=="right"){
if(!isEmpty(choice)){
return top->right->data;
}
}
}
bool LinkStack::isEmpty(string choice)
{
if(choice=="left"){
if(top->left==NULL){
return true;
}
else{
return false;
}
}
if(choice=="right"){
if(top->right==NULL){
return true;
}
else{
return false;
}
}
}
int main()
{
LinkStack T;
int i,x;
string choice;
for(i=1;i<=10;i++){
cin>>x>>choice;
T.push(x,choice);
}
cout<<"左栈是否为空（空为1,非空为0):"<<T.isEmpty("left")<<endl;
cout<<"左栈栈顶元素:"<<T.getTop("left")<<endl;
cout<<"左栈出栈元素:"<<T.pop("left")<<endl;
cout<<"右栈是否为空（空为1,非空为0):"<<T.isEmpty("right")<<endl;
cout<<"右栈栈顶元素:"<<T.getTop("right")<<endl;
cout<<"右栈出栈元素:"<<T.pop("right")<<endl;
return 0;
}
|
