描述2.txt

5、顺序栈 SeqStack.h Test.cpp 6、链式栈 StackNode.h LinkStack.h Test.cpp 7、顺序队列 SeqQueue.h T

5、顺序栈
SeqStack.h	
Test.cpp	
6、链式栈	
StackNode.h	
LinkStack.h
Test.cpp	
7、顺序队列	
SeqQueue.h	
Test.cpp	
8、链式队列	
QueueNode.h	
LinkQueue.h	
Test.cpp	



5、	顺序栈

SeqStack.h

template<typename Type> class SeqStack{
public:
	SeqStack(int sz):m_ntop(-1),m_nMaxSize(sz){
		m_pelements=new Type[sz];
		if(m_pelements==NULL){
			cout<<"Application Error!"<<endl;
			exit(1);
		}
	}
	~SeqStack(){
		delete[] m_pelements;
	}

public:

	void Push(const Type item); //push data
	Type Pop();                 //pop data
	Type GetTop() const;        //get data
    void Print();               //print the stack
	void MakeEmpty(){           //make the stack empty
		m_ntop=-1;
	}
	bool IsEmpty() const{
		return m_ntop==-1;
	}
	bool IsFull() const{
		return m_ntop==m_nMaxSize-1;
	}
	

private:
	int m_ntop;
	Type *m_pelements;
	int m_nMaxSize;

};

template<typename Type> void SeqStack<Type>::Push(const Type item){
	if(IsFull()){
		cout<<"The stack is full!"<<endl;
		return;
	}
	m_pelements[++m_ntop]=item;
}

template<typename Type> Type SeqStack<Type>::Pop(){
	if(IsEmpty()){
		cout<<"There is no element!"<<endl;
		exit(1);
	}
	return m_pelements[m_ntop--];
}

template<typename Type> Type SeqStack<Type>::GetTop() const{
	if(IsEmpty()){
		cout<<"There is no element!"<<endl;
		exit(1);
	}
	return m_pelements[m_ntop];
}

template<typename Type> void SeqStack<Type>::Print(){
	cout<<"bottom";
	for(int i=0;i<=m_ntop;i++){
		cout<<"--->"<<m_pelements[i];
	}
	cout<<"--->top"<<endl<<endl<<endl;
}

Test.cpp

#include<iostream>
using namespace std;

#include "SeqStack.h"

int main(){
	SeqStack<int> stack(10);
	int init[10]={1,2,6,9,0,3,8,7,5,4};
	for(int i=0;i<10;i++){
		stack.Push(init[i]);
	}
	stack.Print();

	stack.Push(88);

	cout<<stack.Pop()<<endl;
	stack.Print();
	
	stack.MakeEmpty();
	stack.Print();

	stack.Pop();
	return 0;
}

6、	链式栈

StackNode.h

template<typename Type> class LinkStack;

template<typename Type> class StackNode{
private:
	friend class LinkStack<Type>;
	StackNode(Type dt,StackNode<Type> *next=NULL):m_data(dt),m_pnext(next){} 

private:
	Type m_data;
	StackNode<Type> *m_pnext;
};

LinkStack.h

#include "StackNode.h"

template<typename Type> class LinkStack{
public:
	LinkStack():m_ptop(NULL){}
	~LinkStack(){
		MakeEmpty();
	}

public:
	void MakeEmpty();           //make the stack empty
	void Push(const Type item); //push the data
	Type Pop();                 //pop the data
	Type GetTop() const;        //get the data
    void Print();               //print the stack
        
	bool IsEmpty() const{
		return m_ptop==NULL;
	}
	
private:
	StackNode<Type> *m_ptop;
};

template<typename Type> void LinkStack<Type>::MakeEmpty(){
	StackNode<Type> *pmove;
	while(m_ptop!=NULL){
		pmove=m_ptop;
		m_ptop=m_ptop->m_pnext;
		delete pmove;
	}
}

template<typename Type> void LinkStack<Type>::Push(const Type item){
	m_ptop=new StackNode<Type>(item,m_ptop);
}

template<typename Type> Type LinkStack<Type>::GetTop() const{
	if(IsEmpty()){
		cout<<"There is no elements!"<<endl;
		exit(1);
	}
	return m_ptop->m_data;
}

template<typename Type> Type LinkStack<Type>::Pop(){
	if(IsEmpty()){
		cout<<"There is no elements!"<<endl;
		exit(1);
	}
	StackNode<Type> *pdel=m_ptop;
	m_ptop=m_ptop->m_pnext;
	Type temp=pdel->m_data;
	delete pdel;
	return temp;
}

template<typename Type> void LinkStack<Type>::Print(){
	StackNode<Type> *pmove=m_ptop;
	cout<<"buttom";
	while(pmove!=NULL){
		cout<<"--->"<<pmove->m_data;
		pmove=pmove->m_pnext;
	}
	cout<<"--->top"<<endl<<endl<<endl;
}

Test.cpp

#include <iostream>
using namespace std;

#include "LinkStack.h"

int main(){
	LinkStack<int> stack;
	int init[10]={1,3,5,7,4,2,8,0,6,9};
	for(int i=0;i<10;i++){
		stack.Push(init[i]);
	}
	stack.Print();

	cout<<stack.Pop()<<endl;
	stack.Print();
	
	cout<<stack.GetTop()<<endl;
	stack.Print();

	cout<<stack.Pop()<<endl;
	stack.Print();

	stack.MakeEmpty();
	stack.Print();
	
	stack.Pop();


	return 0;
}

7.顺序队列

SeqQueue.h

template<typename Type> class SeqQueue{
public:
	SeqQueue(int sz):m_nrear(0),m_nfront(0),m_ncount(0),m_nMaxSize(sz){
		m_pelements=new Type[sz];
		if(m_pelements==NULL){
			cout<<"Application Error!"<<endl;
			exit(1);
		}
	}
	~SeqQueue(){
		delete[] m_pelements;
	}
	void MakeEmpty();               //make the queue empty
	bool IsEmpty();
	bool IsFull();
	bool Append(const Type item);   //insert data
	Type Delete();                  //delete data
	Type Get();                     //get data
	void Print();                   //print the queue

private:
	int m_nrear;
	int m_nfront;
	int m_ncount;
	int m_nMaxSize;
	Type *m_pelements;
	
};

template<typename Type> void SeqQueue<Type>::MakeEmpty(){
	this->m_ncount=0;
	this->m_nfront=0;
	this->m_nrear=0;
}

template<typename Type> bool SeqQueue<Type>::IsEmpty(){
	return m_ncount==0;
}

template<typename Type> bool SeqQueue<Type>::IsFull(){
	return m_ncount==m_nMaxSize;
}

template<typename Type> bool SeqQueue<Type>::Append(const Type item){
	if(IsFull()){
		cout<<"The queue is full!"<<endl;
		return 0;
	}
	m_pelements[m_nrear]=item;
	m_nrear=(m_nrear+1)%m_nMaxSize;
	m_ncount++;
	return 1;
}

template<typename Type> Type SeqQueue<Type>::Delete(){
	if(IsEmpty()){
		cout<<"There is no element!"<<endl;
		exit(1);
	}
	Type temp=m_pelements[m_nfront];
	m_nfront=(m_nfront+1)%m_nMaxSize;
	m_ncount--;
	return temp;
}

template<typename Type> Type SeqQueue<Type>::Get(){
	if(IsEmpty()){
		cout<<"There is no element!"<<endl;
		exit(1);
	}
	return m_pelements[m_nfront];
}

template<typename Type> void SeqQueue<Type>::Print(){
	cout<<"front";
	for(int i=0;i<m_ncount;i++){
		cout<<"--->"<<m_pelements[(m_nfront+i+m_nMaxSize)%m_nMaxSize];
	}
	cout<<"--->rear"<<endl<<endl<<endl;
}

Test.cpp

#include <iostream>
using namespace std;

#include "SeqQueue.h"

int main(){
	SeqQueue<int> queue(10);
	int init[10]={1,6,9,0,2,5,8,3,7,4};
	for(int i=0;i<5;i++){
		queue.Append(init[i]);
	}
	queue.Print();

	cout<<queue.Delete()<<endl;
	queue.Print();

	for(int i=5;i<10;i++){
		queue.Append(init[i]);
	}
	queue.Print();

	cout<<queue.Get()<<endl;

	queue.MakeEmpty();
	queue.Print();

	queue.Append(1);
	queue.Print();

	return 0;
}

8、链式队列

QueueNode.h

template<typename Type> class LinkQueue;

template<typename Type> class QueueNode{
private:
	friend class LinkQueue<Type>;
	QueueNode(const Type item,QueueNode<Type> *next=NULL)
		:m_data(item),m_pnext(next){}
private:
	Type m_data;
	QueueNode<Type> *m_pnext;
};

LinkQueue.h

#include "QueueNode.h"

template<typename Type> class LinkQueue{
public:
	LinkQueue():m_prear(NULL),m_pfront(NULL){}
	~LinkQueue(){
		MakeEmpty();
	}
	void Append(const Type item);   //insert data
	Type Delete();                  //delete data
	Type GetFront();                //get data
	void MakeEmpty();               //make the queue empty
    void Print();                   //print the queue

	bool IsEmpty() const{
		return m_pfront==NULL;
	}

private:
	QueueNode<Type> *m_prear,*m_pfront;
};

template<typename Type> void LinkQueue<Type>::MakeEmpty(){
	QueueNode<Type> *pdel;
	while(m_pfront){
		pdel=m_pfront;
		m_pfront=m_pfront->m_pnext;
		delete pdel;
	}
}

template<typename Type> void LinkQueue<Type>::Append(const Type item){
	if(m_pfront==NULL){
		m_pfront=m_prear=new QueueNode<Type>(item);
	}
	else{
		m_prear=m_prear->m_pnext=new QueueNode<Type>(item);
	}
}

template<typename Type> Type LinkQueue<Type>::Delete(){
	if(IsEmpty()){
		cout<<"There is no element!"<<endl;
		exit(1);
	}
	QueueNode<Type> *pdel=m_pfront;
	Type temp=m_pfront->m_data;
	m_pfront=m_pfront->m_pnext;
	delete pdel;
	return temp;
}

template<typename Type> Type LinkQueue<Type>::GetFront(){
	if(IsEmpty()){
		cout<<"There is no element!"<<endl;
		exit(1);
	}
	return m_pfront->m_data;
}

template<typename Type> void LinkQueue<Type>::Print(){
	QueueNode<Type> *pmove=m_pfront;
	cout<<"front";
	while(pmove){
		cout<<"--->"<<pmove->m_data;
		pmove=pmove->m_pnext;
	}
	cout<<"--->rear"<<endl<<endl<<endl;
}

Test.cpp

#include <iostream>

using namespace std;

#include "LinkQueue.h"

int main(){
	LinkQueue<int> queue;
	int init[10]={1,3,6,8,9,2,0,5,4,7};

	for(int i=0;i<10;i++){
		queue.Append(init[i]);
	}
	queue.Print();

	queue.Delete();
	queue.Print();

	cout<<queue.GetFront()<<endl;
	queue.Print();

	queue.MakeEmpty();
	queue.Print();

	queue.Delete();

	return 0;
}