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

一．.实验目的

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

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

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

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

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

二．实验时间

准备时间为第5周到第6周，具体集中实验时间为6周第2次课。2个学时。

三．实验内容

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

3.编程实现一个十进制数转换成二进制数。要求，要主程序中输出一个10进度数，输出其对应的2进制数序列。

四. 实验代码：

（1）栈的实现

# ifndef Seqstack_H
# define Seqstack_H
const int StackSize=10;
template <class DataType>
class SeqStack
{
       public:
              SeqStack();
              ~SeqStack(){}
              void Push(DataType x);
              DataType pop();
              DataType GetTop();
              int empty();
       private:
              DataType data[StackSize];
              int top;
};
# endif

# include<iostream>
using namespace std;

template<class Datatype>
SeqStack<Datatype>::SeqStack()
{
       top=-1;
}
template<class DataType>
void SeqStack<DataType>::Push(DataType x)
{
       if (top==StackSize-1)throw"上溢";
       top++;
       data[top]=x;
}
template <class DataType>
DataType SeqStack<DataType>::pop()
{
       DataType x;
       if(top==-1)throw"下溢";
       x=data[top--];
       return x;
}
template<class DataType>
DataType SeqStack<DataType>::GetTop()
{
       if(top==-1)
       return data[top];
}
template<class DataType>
int SeqStack<DataType>::empty()
{
       if(top==-1) return 1;
       else return 0;
}
void main()
{
       SeqStack<int>S;
       if(S.empty())
              cout<<"栈为空"<<endl;
       else
              cout<<"栈为空"<<endl;
       cout<<"对8和15进行入栈操作:"<<endl;
       S.Push(8);
       S.Push(15);
       cout<<"栈顶元素为:"<<endl;
       cout<<S.GetTop()<<endl;
       cout<<"执行第一次出栈操作:"<<endl;
       S.pop();
       cout<<"栈顶元素为:"<<endl;
       cout<<S.GetTop()<<endl;
}

（2）链队列的实现

# ifndef LinkQueue_H
# define LinkQueue_h
template <class DataType>
struct Node
{
       DataType data;
       Node<DataType>*next;
};
template <class DataType>
class LinkQueue
{
public:
      
       LinkQueue();
       ~LinkQueue();
       void EnQueue(DataType x);
       DataType DeQueue();
       DataType GetQueue();
       int empty();
private:
       Node<DataType>*front,*rear;
};
# endif
# include<iostream>
using namespace std;
template <class DataType>
LinkQueue<DataType>::LinkQueue()
{
       Node<DataType>*s=NULL;
       s=new Node<DataType>;
       s->next=NULL;
       front=rear=s;
}
template<class DataType>
LinkQueue<DataType>::~LinkQueue()
{
       Node<DataType>*p=NULL;
       while(front !=NULL)
       { 
          p=front ->next;
          delete front;
       front=p;
       }
}
template<class DataType>
void LinkQueue<DataType>::EnQueue(DataType x)
{
       Node<DataType>*s=NULL;
       s=new Node<DataType>;
       s->data=x;
       s->next=NULL;
       rear->next=s;rear=s;
}
template <class DataType>
DataType LinkQueue<DataType>::DeQueue()
{
       Node<DataType>*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;
}
template<class DataType>
DataType LinkQueue<DataType>::GetQueue()
{
       if (front !=rear)
              return front->next->data;
}
template <class DataType>
int LinkQueue<DataType>::empty ()
{
       if(front==rear)
              return 1;
       else
              return 0;
}
void main()
{
       LinkQueue<int>Q;
       if (Q.empty ())
              cout<<"队列为空"<<endl;
    else
              cout<<"队列为空"<<endl;
       cout<<"元素为8和17执行入队操作:"<<endl;
       try
       {
              Q.EnQueue(10);
              Q.EnQueue(15);
       }
       catch(char *wrong)
       {
              cout<<wrong<<endl;
       }
       cout<<"查看队头元素:"<<endl;
       cout<<Q.GetQueue ()<<endl;
       cout<<"执行出队操作:"<<endl;
       try
       {
              Q.DeQueue ();
       }
       catch(char*wrong)
       {
              cout<<wrong<<endl;
       }
       cout<<"查看队头元素:"<<endl;
       cout<<Q.GetQueue <<endl;
}