stackqueue.h

这是清华大学出版社的《数据结构》的电子文档讲义

//"stackqueue.h"
# include<assert.h>
# include "array.h"
# include "list.h"

template <class Type> class stack {							//栈的抽象数据类型
    public:
      	virtual void push(const Type&item)=0;				//将参数压人到栈的栈顶
		virtual Type pop()=0;								//弹出栈顶元素的值
      	virtual Type getTop()=0;							//读出栈顶元素的值
        virtual void makeEmpty()=0;							//清空栈
      	virtual int isEmpty()=0;							//判栈空
//        virtual int isFull()=0;	    						//判栈满
      	};

template <class Type> class stackArray : public stack<Type> {		//向量栈的类定义
	friend ostream& operator<<(ostream& out, stackArray<Type>&);
    public:
        stackArray(int=10);
        //~stackArray(){delete[]elements;}  //缺省的析构函数调用向量析构函数
      	void push(const Type&Item);
        Type pop();
      	Type getTop();
      	void makeEmpty() {top=-1;}
      	int isEmpty(){return top==-1;}
      	int isFull(){return top==(int)(elements.length()-1);}
    protected:
      	int top;							//在连续存储分配下是栈顶指针
      	array<Type> elements;				//在连续存储分配下是存放栈中元素的栈向量
      	//int elements.length()-1 ;			//栈最大可容纳元素个数  //即向量的大小elements.length()
    };
    
template<class Type>stackArray<Type>::stackArray(int s):elements(s){
	top=-1;									//构造函数,初始化时调用向量成员的构造函数
	}										//向量大小为s,top=-1将栈清空

template<class Type>Type stackArray <Type>::getTop(){ 		//返回栈顶元素的值
    assert (! isEmpty());					//断言:判栈空否,若非空则继续执行
    return elements [top]; 
	}

template<class Type>void stackArray<Type>::push(const Type&item){		//将Item压人栈顶
	if(isFull()) elements.reSize(elements.length()+5);				//栈满则加大向量大小
    elements[++top]=item ;							//栈顶指针先加1,然后按此地址进栈
	}

template<class Type>Type stackArray<Type>::pop(){					//弹出栈顶元素
    assert( ! isEmpty());							//断言:判栈空否,若非空则继续执行
    return elements [top--];						//返回栈顶元素的值,同时栈顶指针退1
    }

template<class Type>ostream& operator<<(ostream& out, stackArray<Type>& sa){					//弹出栈顶元素
	for(int i=sa.elements.length()-1; i>=0; i--) 
		out<<sa.elements[i]<<", ";
    out<<endl;
	return out;
    }

template <class Type> class stackList : public stack<Type>{			//链式栈类定义
	friend ostream& operator<<(ostream& out, stackList<Type>&);
	public:
      	stackList():elements(0) {};				//构造函数,调用链表构造函数,0放表头结点内
 //       ~stackList();							//缺省析构函数,调用链表析构函数
      	void push(const Type & item);
      	Type pop();
      	Type getTop();
      	void makeEmpty();							
       	int isEmpty(){return elements.length()==0;}		//链表长度为0即为栈空
    protected:
//      	stackListNode<Type> * top;      					//栈顶指针,即链头指针
		list<Type> elements;								//采用链表存放栈元素
	};

template<class Type>void stackList <Type>::push(const Type &item){		//将值item压栈
    elements.insertAtHead(item);								//将其插入链表作第1个元素,即栈顶
	}

template <class Type> Type stackList <Type>::pop() {				//弹出栈顶元素
    Type value=elements.removeAtHead();					//读出值再删除栈顶元素
	return value ;                 							//返回栈顶元素的值
	}

template <class Type> Type stackList <Type> ::getTop(){				//返回栈顶元素的值
    return elements.findValueIndex(1);						//读出栈顶元素的值
	}

template <class Type> void stackList <Type> ::makeEmpty(){			//清空堆栈
    elements.makeEmpty();									//即清空链表
	}

template<class Type>ostream& operator<<(ostream& out, stackList<Type>& sa){					//弹出栈顶元素
    out<<sa.elements;
	return out;
    }

template <class Type> class queue{					//队列框架类定义
	public:
//      Queue(int=10);							//构造函数
      virtual void enQueue(const Type & item)=0; 	// etem进队
      virtual Type deQueue()=0;					//出队
      virtual Type getFront()=0;					//返回队头元素的值
      virtual void makeEmpty()=0;				//置空队列
      virtual int isEmpty()=0;					//判队列空
//      virtual int IsFudl()=0;						//判队列满
	};

template<class Type> class queueArray : public queue<Type> {		//循环队列的类定义
	friend ostream& operator<<(ostream& out, queueArray<Type>&);
	public:
  		queueArray(int=10);
//    	~Queue(){delete[]elements;}
    	void enQueue(const Type& item );
    	Type deQueue();
    	Type getFront();
  		void makeEmpty(){front=rear=0;}					//队首指针和队尾指针置。
  		int isEmpty(){return front==rear;}					//判队列空否
  		int isFull(){return (rear+1)%maxSize==front;}			//判队列满否
  		int length()const{return (rear-front+maxSize)%maxSize ;}	//求队列元素个数
	private:
  		int rear,front;									//队尾与队首指针
    	array<Type> elements;							//存放队列元素的向量
  		int maxSize;									//队列最大可容纳元素个数
	};

template<class Type>queueArray<Type>::queueArray(int sz)
	:front(0),rear(0),maxSize(sz), elements(sz){};
										//建立一个最大具有maxSize个元素的空向量队列。
//  	elements=new Type[maxSize];			//创建队列空间
//  	assert(elements !=0);				//断言:动态存储分配成功与否
//	}

template<class Type>void queueArray<Type>::enQueue(const Type&item){
  	assert(! isFull());									//断言:队列不满则继续执行
	rear=(rear+1)%maxSize ;                    		//队尾指针加1      
	elements[rear]=item ;								//在队尾插人item
    }
template<class Type>Type queueArray<Type>::deQueue(){
    assert(! isEmpty());								//断言:队列不空继续执行
    front=(front+1)%maxSize ;							//队首指针加1
    return elements[front];								//返回队首元素的值
    }
template<class Type>Type queueArray <Type>::getFront(){	//队列不空则返回队首元素的值。
    assert(!isEmpty());									//断言:队列不空继续执行
    return elements [(front+1)%maxSize] ;				//返回队首元素的值
	}

template<class Type>ostream& operator<<(ostream& out, queueArray<Type>& sa){					//弹出栈顶元素
	out<<sa.elements;
	return out;
    }

template <class Type> class queueList : public queue<Type>{			//链式队列类定义
	friend ostream& operator<<(ostream& out, queueList<Type>&);
	public:
  		queueList():elements(0){};				//构造函数,调用链表构造函数,0用于头结点
//  		queueList():rear(NULL), front(NULL){}		//构造函数
//    		~queueList();								//缺省析构函数,自动调用链表析构函数
  		void enQueue( const Type & item);					//将item加人队尾
  		Type deQueue();										//删除并返回队首元素
  		Type getFront();									//查看队首元素的值
  		void makeEmpty();									//置空队列
  		int isEmpty(){return elements.length()==0;}			//判队列空
	private:
//    		queueListNode <Type>*front, *rear;			//队首、队尾指针
		list<Type> elements;
	};

template<class Type>void queueList<Type>::enQueue(const Type& item){
	elements.insertAtTail(item);
	}

template<class Type>Type queueList<Type>::deQueue(){
  	Type retvalue=elements.removeAtHead();				//取出并保存队首结点的数据域
	return retvalue;										//返回数据
	}

template<class Type>Type queueList<Type>::getFront(){
	return elements.findValueIndex(1);						//取队首元素中的数据值
	}

template<class Type>void queueList<Type>::makeEmpty(){
    elements.makeEmpty();									//即清空链表
	}

template<class Type>ostream& operator<<(ostream& out, queueList<Type>& sa){					//弹出栈顶元素
    out<<sa.elements;
	return out;
    }