《数据结构》实验三： 栈和队列实验

一．.实验目的

???? 巩固栈和队列数据结构，学会运用栈和队列。

1.回顾栈和队列的逻辑结构和受限操作特点，栈和队列的物理存储结构和常见操作。

2.学习运用栈和队列的知识来解决实际问题。

3.进一步巩固程序调试方法。

4.进一步巩固模板程序设计。

二．实验内容

1.自己选择顺序或链式存储结构，定义一个空栈类，并定义入栈、出栈、取栈元素基本操作。然后在主程序中对给定的N个数据进行验证，输出各个操作结果。

源代码：

#include<iostream>
using namespace std;


struct node
{
int data;
node *next;
};


class linkstack
{
public:
linkstack(){top=NULL;}
~linkstack(){}
void push (int x);
int pop();
int gettop()
{
if(top!=NULL)
return top->data;
else
return 0;
}
int empty()
{
if(top==NULL)
return 1;
else
return 0;
}
private:
node *top;
node *s;
int x;
};


void linkstack::push (int x)
{
s=new node;s->data=x;
s->next=top;
top=s;
}
int linkstack::pop()
{
if(top==NULL)throw"down";
x=top->data;s=top;
top=top->next;
delete s;
return x;
}


void main()
{
linkstack a;
int a1,b1;
cout<<"push2 "<<endl;
cin>>a1>>b1;
a.push(a1);
a.push(b1);
cout<<"gettop"<<endl;
cout<<a.gettop()<<endl;
cout<<"pop"<<endl;
cout<<a.pop()<<endl;
cout<<"gettop:"<<endl;
cout<<a.gettop()<<endl;
if(a.empty())
cout<<"null"<<endl;
else
cout<<"not null"<<endl;
}

2.自己选择顺序或链式存储结构，定义一个空栈队列，并定义入栈、出栈、取栈元素基本操作。然后在主程序中对给定的N个数据进行验证，输出各个操作结果。

源代码：

#include<iostream>
using namespace std;


struct node
{
int data;
node *next;
};


class linkqueue
{
public:
linkqueue();
~linkqueue();
void enqueue (int x);
int dequeue();
int getqueue();
int empty();
private:
node *front;
node *rear;
node *s;
int next;
int x;
};
linkqueue::linkqueue()
{
s=NULL;
s=new node;
s->next=NULL;
front=rear=s;
}
linkqueue::~linkqueue()
{
node*p=NULL;
while(front!=NULL)
{
p=front->next;
delete front;
front=p;
}
}
void linkqueue::enqueue (int x)
{
node *s=NULL;
s=new node;
s->data=x;
s->next=NULL;
rear->next=s;rear=s;
}


int linkqueue::dequeue()
{
node*p=NULL;
if(rear==front)throw"down";
p=front->next;
x=p->data;
front->next=p->next;
if(p->next==NULL)rear=front;
delete p;
return x;
}
int linkqueue::getqueue()
{
if(front!=rear)
return front->next->data;
}
int linkqueue::empty()
{
if(front==rear)
return 1;
else
return 0;
}


void main()
{
linkqueue a;
int a1,b1;
cout<<"push2 "<<endl;
cin>>a1>>b1;
try
{
a.enqueue(a1);
a.enqueue(b1);
}
catch(char*wrong)
{
cout<<wrong<<endl;
}
cout<<"getqueue"<<endl;
cout<<a.getqueue()<<endl;
cout<<"dequeue"<<endl;
try
{
a.dequeue();
}
catch(char*wrong)
{
cout<<wrong<<endl;
}
cout<<"getqueue:"<<endl;
cout<<a.getqueue()<<endl;
if(a.empty())
cout<<"null"<<endl;
else
cout<<"not null"<<endl;
}