一、实验目的

1、   熟练掌栈和队列的结构特点，掌握栈和队列的顺序存储和链式存储结构和实现。

2、      学会使用栈和队列解决实际问题。

二、实验内容

1、自己确定结点的具体数据类型和问题规模：

分别建立一个顺序栈和链栈，实现栈的压栈和出栈操作。

分别建立一个顺序队列和链队列，实现队列的入队和出队操作。

2、设计算法并写出代码，实现一个将一个十进制转换成二进制数。

一.顺序栈

#include<iostream.h>
const int SeqList=10;
class SeqStack
{
public:
SeqStack();//构造
~SeqStack();
void Push(int x);//入
int Pop();//弹
int Get();//取
private:
int data[SeqList];
int top;
};


SeqStack::SeqStack()
{top=-1;}


SeqStack::~SeqStack(){}


void SeqStack::Push(int x)
{
if(top==SeqList-1)throw "上溢";
top++;
data[top]=x;
}


int SeqStack::Pop()
{
int x;
if(top==-1)throw "下溢";
x=data[top];
top--;
return x;
}


int SeqStack::Get()
{if(top!=-1)return data[top];}


int main()
{
SeqStack S;
cout<<"请对15、18、9进行入栈操作："<<endl;
S.Push(15);
S.Push(18);
S.Push(9);
cout<<"执行一次出栈操作"<<endl;
S.Pop();
cout<<"栈顶元素"<<S.Get()<<endl;
return 0;

}

二.链栈

#include<iostream.h>
struct Node
{
int data;
struct Node *next;
};
class LinkStack
{
public:
LinkStack();
~LinkStack(){}
void Push(int x);
int Pop();
int Get();
private:
Node *top;
};
LinkStack::LinkStack()
{top=NULL;}
void LinkStack::Push(int x)
{   Node *s;
s=new Node;
s->data=x;
s->next=top;
top=s;
}
int LinkStack::Pop()
{ int x;
Node *p;
if(top==NULL)throw"上溢";
x=top->data;
p=top;
top=top->next;
delete p;
return x;
}
int LinkStack::Get()
{
return top->data;
}




int main()
{LinkStack L;
cout<<endl<<"链栈操作"<<endl;
cout<<"请对7、8、1进行入栈操作："<<endl;
L.Push(7);
L.Push(8);
L.Push(1);
cout<<"执行一次出栈操作"<<endl;
L.Pop();
cout<<"栈顶元素"<<L.Get()<<endl;
return 0;
}

三.队列

#include<iostream>  
using namespace std;  
const int Queuesize=100;  
class Cirqueue{  
public:  
Cirqueue()
{front=rear=Queuesize-1;}
~Cirqueue(){}
void EnQueue(int x);//入
int DeQueue();//删
int GetQueue();//取
void PrintQueue();
private:  
int data[Queuesize];
int front,rear;   
}; 


void Cirqueue::EnQueue(int x)  
{  
    if((rear+1)%Queuesize==front) throw"上溢";  
    rear=(rear+1)%Queuesize;
    data[rear]=x;  
} 


int Cirqueue::DeQueue()  
{  
    if(rear==front) throw"下溢";  
    front=(front+1)%Queuesize;  
    return data[front];  
}


int Cirqueue::GetQueue()  
{  
    int i;  
    if(rear==front) throw"下溢";  
    i=(front+1)%Queuesize;  
    return data[i];  
}  


void Cirqueue::PrintQueue()  
{  
    int p=(front+1)%Queuesize;    
    while(p!=rear)
{    
        cout<<data[p]<<" ";    
        p=(p+1)%Queuesize;    
    }
    cout<<data[p]<<endl;  //
}  


int main()  
{  
    Cirqueue c; 
int n;
    for(int i=1;i<=5;i++)  
    {
cout<<"请输入进队列的数"<<endl;
cin>>n;
c.EnQueue(n);}  
    cout<<"队列如下："<<endl;  
    c.PrintQueue();  
    cout<<"出队一个元素"<<c.DeQueue()<<"结果如下："<<endl;  
    c.PrintQueue();  
    cout<<"现在对头元素为："<<c.GetQueue()<<endl;  
return 0;
}  

四.链队列

#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, *rear;
};


LinkQueue::LinkQueue()
{
Node *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;
int x;
if(rear==front)throw"下溢";
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 Q;
if(Q.Empty())
cout<<"队列为空"<<"\n"<<endl;
else
cout<<"队列非空"<<"\n"<<endl;
cout<<"元素10、15和20执行入队操作"<<"\n"<<endl;
try
{
Q.EnQueue(10);
Q.EnQueue(15);
Q.EnQueue(20);
}
catch(char *wrong)
{
cout<<wrong<<"\n"<<endl;
}
cout<<"查看队头元素："<<"\n"<<endl;
cout<<Q.GetQueue()<<"\n"<<endl;
cout<<"执行出队操作："<<"\n"<<endl;
try
{Q.DeQueue();}
catch(char *wrong)
{cout<<wrong<<endl;}
cout<<"查看队头元素："<<endl;
cout<<Q.GetQueue()<<endl;

}

五.十进制转二进制 

#include<iostream>
using namespace std;
const int StackSize=50;
class SeqStack
{
public:
SeqStack()
{top=-1;}
~SeqStack(){}
void Push(int x)
{
if(top==StackSize-1) throw"上溢";
top++;
data[top]=x;
}
int  Pop()
{
int x;
if(top==-1)throw"下溢";
x=data[top];
top--;
return x;
}
int Empty()
{
if(top==-1) return 0;
else return 1;
}
private:
int data[StackSize];
int top;
};


int main()
{
    int n;
    SeqStack s;
cout<<"输入十进制数:";
    cin>>n;
    while(n)
    {
        s.Push(n%2);
        n/=2;
    }
cout<<"十进制换为二进制:";
    while(s.Empty())
    {
        cout<<s.Pop()<<" ";
    }
cout<<endl;
return 0;
}