栈和队列（第二次数据结构作业）

栈和队列（第二次数据结构作业）

#include <iostream> #include <cstdlib> #include <assert.h> using namespace std; template <typename DataType> class SeqStack { //顺序栈类定义 private: int maxSize; //栈最大容量 void overflowProcess(); //栈的溢出处理 public: DataType *data; //栈元素存放数组 int top;//栈顶指针 SeqStack(int sz =50); //构造函数 ~SeqStack() { delete []data; } //析构函数 void Push( DataType x ); bool Pop(DataType &x ); bool GetTop(DataType &x ); bool Empty() const { return top == -1; } bool Full() const { return top == maxSize-1; } template <typename D> friend ostream& operator<<(ostream& out,SeqStack < DataType >& s); }; template <class DataType > void SeqStack< DataType >::overflowProcess() {//私有函数：当栈满则执行扩充栈存储空间处理 DataType *newArray = new DataType[2*maxSize]; //创建更大的数组 for (int i = 0; i <= top; i++) newArray[i] = data[i]; maxSize += maxSize; delete [ ] data; data = newArray; //改变data指针 } template <class DataType > bool SeqStack< DataType >::GetTop(DataType & x) { //若栈不空则获取栈顶元素 if (Empty() == true) return false; x = data[top]; return true; } template <class DataType > SeqStack< DataType >::SeqStack(int sz) { if (sz>0) { maxSize = sz; top=-1; data = new DataType[maxSize]; if(data==NULL) { cerr << "存储分配出错 " << endl; exit(1); } } } template <class DataType > void SeqStack< DataType >::Push(DataType x) { //若栈不满, 则将元素x插入该栈栈顶, 否则溢出处理 if (Full() == true) overflowProcess(); //栈满 data[++top] = x; //栈顶指针先加1, 再进栈 } template <class DataType > bool SeqStack< DataType >::Pop(DataType & x) { //函数退出栈顶元素并返回栈顶元素的值 if (Empty() == true) return false; x = data[top--]; //栈顶指针退1 return true; //退栈成功 } template <class DataType > ostream& operator<<(ostream& out,SeqStack < DataType >& s) { int i=s.top; while (i>=0) {out<<s.top-i+1<< ":"<< s.data[i]<< endl; i--; } return out; } template<class T> class SeqQueue{ //循环队列定义 protected: int rear,front; T *elements; int maxSize; public: SeqQueue(int sz=50);//初始化队列 ~SeqQueue(){delete[] elements;} bool EnQueue(const T &x); //入队 bool DeQueue(T &x); //出队 bool getFront(T &x) const; //获取队头元素 void makeEmpty(){front=rear=0;} //设置为空队列 bool IsEmpty() const{return (front==rear)?true:false;} bool IsFull() const{return ((rear+1)%maxSize==front)?true:false;} int getSize() const{return (rear-front+maxSize)%maxSize;} int min(); void inorder(); void input(int n); void output(); }; template<class T> SeqQueue<T>::SeqQueue(int sz){ rear=0; front=0; maxSize=sz; elements=new T[maxSize]; assert(elements!=NULL); } template<class T> bool SeqQueue<T>::EnQueue(const T&x){ if(IsFull()) return false; elements[rear]=x; rear=(rear+1)%maxSize; return true; } template<class T> bool SeqQueue<T>::DeQueue(T &x){ if(IsEmpty()) return false; x=elements[front]; front=(front+1)%maxSize; return true; } template<class T> bool SeqQueue<T>::getFront(T &x) const{ if(IsEmpty()) return false; x=elements[front]; return true; } template<class T> void SeqQueue<T>::input(int n){ if(n>maxSize-1) cout<<"输入错误！"<<endl; else { T data; for(int i=0;i<n;i++) { cin>>data; elements[rear]=data; rear=(rear+1)%maxSize; } } } template<class T> void SeqQueue<T>::output(){ int i=0; for(i=front;i<front+getSize();i++) cout<<elements[i%maxSize]<<" "; } template<class T> int SeqQueue<T>::min(){ T a=elements[front]; int i,k=(front+1)%maxSize,j; for(i=1;i<this->getSize();i++){ if(elements[k]<a){ a=elements[k]; j=k; } k=(k+1)%maxSize; } return j; } template <class T> struct LinkNode { T data; LinkNode<T> *next; }; template <class T> class LinkList { protected: LinkNode<T> *first; public: LinkList() { first = new LinkNode<T>;first->next=NULL; first->data = 0; } LinkList(LinkList<T>& L); ~LinkList(){ } void makeEmpty(); int Length() const; LinkNode<T> *Search(T x); LinkNode<T> *Locate(int i); bool Reverse(); //逆置函数的声明 void setData(int i, T x); bool Insert (int i, T x); bool Remove(int i, T& x); bool Remove(T x); bool IsEmpty() const { return first->next == NULL ? true : false; } LinkNode<T> *getFirst() const { return first; } void setFirst(LinkNode<T> *f ) { first = f; } void output() {LinkNode<T> *p=first->next; while(p!=NULL) {cout<<p->data<<" "; p=p->next; } cout<<endl; } }; template <class T> void LinkList<T>::makeEmpty() { LinkNode<T> *q; while (first->next != NULL) { q = first->next; first->next = q->next; delete q; } } template <class T> int LinkList<T> :: Length ( ) const { LinkNode<T> *p = first->next; int count = 0; while ( p != NULL ) {p = p->next; count++; } return count; } template <class T> LinkNode<T> *LinkList<T>::Locate ( int i ) { if (i < 0) return NULL; LinkNode<T> *current = first; int k = 0; while ( current != NULL && k < i ) { current = current->next; k++; } return current; } template <class T> bool LinkList<T>::Insert (int i, T x) { LinkNode<T> *current = Locate(i); if(current == NULL) return false; LinkNode<T> *newNode=new LinkNode<T>; newNode->data=x; newNode->next = current->next; current->next = newNode; return true; } //1.栈的复制 template <class DataType > void Duplicate(SeqStack< DataType >& s1,SeqStack< DataType >& s2){ SeqStack< DataType > s3; DataType x; while(!s1.Empty()){ s1.Pop(x); s3.Push(x); } while(!s3.Empty()){ s3.Pop(x); s2.Push(x); s1.Push(x); } } //2.队列的升序 template<class T> void SeqQueue<T>::inorder(){ SeqQueue<T> L; int i,k=this->front,n=this->getSize(); T t; while(this->IsEmpty()==false){ if(this->front==this->min()){ DeQueue(t); L.EnQueue(t); } else{ DeQueue(t); EnQueue(t); } } for(i=1;i<=n;i++){ L.DeQueue(t); this->EnQueue(t); } } //3.利用栈实现单向列表的逆置 template<class T> void nizhi(LinkList<T>& L1){ SeqStack<T> S; LinkNode<T> *p=L1.getFirst()->next; int n,i; T m; n=L1.Length(); for(i=0;i<n;i++){ m=p->data; S.Push(m); p=p->next; } L1.makeEmpty(); for(i=0;i<n;i++){ S.Pop(m); L1.Insert(i,m); } } int main(){ SeqStack<int> S1,S2,S3; int i,x; for(i=0;i<10;i++)S1.Push(10-i); //1.栈的复制的检测 cout<<"S1:\n"; cout<<S1<<endl; Duplicate(S1,S2); cout<<"将S1复制到S2"<<endl; cout<<S2<<endl; //2.队列的升序 int n; cin>>n;//构造长度为n的数列 SeqQueue<int> S; S.input(n);//输入n个数 cout<<"队列S为:"; S.output(); cout<<endl; S.inorder(); cout<<"队列S为:"; S.output(); cout<<endl; //3.利用栈实现单向列表的逆置 LinkList<int>LA; for(int i=0;i<=10;i++)LA.Insert(i,i); LA.output(); nizhi(LA); LA.output(); return 0; }