数据结构【三】:栈和队列（C++）

顺序栈

---

#include<iostream>
using namespace std;
const int stackIncreament=20;		//栈满时增加空间大小 
template<class T>
class Stack
{
	public:
		Stack(int num);					//构造函数 产生数据空间为num的栈 
		~Stack(){delete []data;};	//析构函数 
		void push(T &x);			//将数据x压栈 
		bool pop(T &x);				//将顶端数据出栈 
		bool getTop(T &x);			//只是获取顶端数据 
		bool isEmpty()const;		//判空函数 
		bool isFull()const;			//判满函数 
		int getSize()const;			//获取栈中元素个数 
		void makeEmpty(){top=-1;};			//置空栈 
		void output();				//输出 
	protected:
		T *data;
		int maxSize;
		int top;
		void overflowProcess();
} ;
template<class T>
Stack<T>::Stack(int num)
{
	top=num;
	data=new T[top--];
	if(data==NULL)
	{
		cerr<<"申请空间失败";
		exit(1); 
	}
	for(int i=0;i<=top;i++)
		cin>>data[i];
}
template<class T>
void Stack<T>::push(T &x)
{
	if(isFull())			//判满设置 
	overflowProcess();		//扩容设置 
	data[++top]=x;
}
template<class T>
void Stack<T>::overflowProcess()
{
	T *newData=new T[maxSize+stackIncreament]; 
	if(newData==NULL)
	{
		cerr<<"申请空间失败";
		exit(1); 
	}
	for(int i=0;i<=top;i++)
	newData[i]=data[i];
	maxSize+=stackIncreament;
	delete []data;
	data=newData;
}
template<class T>
bool  Stack<T>::pop(T &x)
{
	if(isEmpty())
	return false;
	x=data[top--];
	return true;	
} 
template<class T>
bool Stack<T>::getTop(T &x)
{
	if(isEmpty())
	return false;
	x=data[top];
	return true;
}
template<class T>
bool Stack<T>::isFull()const
{
	if(top==maxSize-1)			//注意判满条件 
	return true;
	else
	return false; 
}
template<class T>
bool Stack<T>::isEmpty()const
{
	if(top==-1)
	return true;
	else
	return false;
}
template<class T>
int Stack<T>::getSize()const
{
	return top+1;
}
template<class T>
void Stack<T>::output()
{
	int i;
	for( i=top;i>0;i--)
	cout<<data[i]<<",";
	cout<<data[i]<<endl;
}
int main()
{
	int num;
	cout<<"输入数据个数"; 
	cin>>num;
	Stack<int> test(num);
	test.output();
	cout<<"输入扩充数据";
	cin>>num; 
	test.push(num);
	test.output();
	test.pop(num);
	test.output();
}

/*
1、压栈的时候注意判满扩容设置 
*/

顺序双栈

头和位同时存储数据，向中间靠拢。

链栈（带头节点）

---

#include<iostream>
using namespace std;
template <class T>
struct LinkNode
{
	T data;
	LinkNode<T> *next=NULL;	
	LinkNode()
	{
		next=NULL;
	}
	LinkNode(T x)
	{
		data=x;
	};
	LinkNode(LinkNode<T> *p)
	{
		next=p;
	}
	LinkNode(T x,LinkNode<T> *p)
	{
		data=x;
		next=p;
	}
};
template <class T>
class Stack
{
	public:
		Stack();					//构造函数 
		~Stack(){makeEmpty();};	//析构函数 
		void push(T &x);			//将数据x压栈 
		bool pop(T &x);				//将顶端数据出栈 
		bool getTop(T &x);			//只是获取顶端数据 
		bool isEmpty()const;		//判空函数 
		int getSize()const;			//获取栈中元素个数 
		void makeEmpty();			//置空栈 
		void output();				//输出 
	protected:
		LinkNode<T> *head;
};
template<class T>
Stack<T>::Stack()
{
	head=new LinkNode<T>;
}
template<class T>
void Stack<T>::push(T &x)
{
	
	LinkNode<T> *newNode=new LinkNode<T>(x);				//使用前插法构建 
	if(newNode==NULL)
	{
		cerr<<"储存分配错误"<<endl;
		exit(1); 
	}
	newNode->next=head->next;
	head->next=newNode;
}
template<class T>
bool Stack<T>::isEmpty()const
{
	if(head->next==NULL)
	return true;
	else
	return false;
}
template<class T>
bool  Stack<T>::pop(T &x)
{
	LinkNode<T> *p;
	if(isEmpty())
	return false;
	else
	{
		p=head->next;
		x=p->data;
		head->next=p->next;
		delete p;
		return true;
	}	
} 
template<class T>
bool Stack<T>::getTop(T &x)
{
	if(isEmpty())
	return false;
	x=head->next->data;
	return true;
}
template<class T>
int Stack<T>::getSize()const
{
	LinkNode<T> *p=head->next;
	int num=0;
	while(p!=NULL)
	{
		num++;
		p=p->next;
	}
	return num;
}
template<class T>
void Stack<T>::makeEmpty()
{
	LinkNode<T> *p=head->next;
	while(head->next!=NULL)
	{
		head->next=p->next;
		delete p;
		p=head->next;
	}
}
template<class T>
void Stack<T>::output()
{
	LinkNode<T> *p=head->next;
	while(p!=NULL)
	{
		cout<<p->data<<",";
		p=p->next;
	}
}
int main()
{
	int num,x;
	cout<<"输入数据个数"; 
	cin>>num;
	Stack<int> test;
	while(num--)
	{
		cin>>x; 
		test.push(x);
	}
	test.output();
	test.pop(x);
	cout<<x<<endl;
	test.pop(x);
	test.pop(x);
	cout<<test.getSize();
	test.output();
}
/*
//使用前插法构建栈
*/

顺序（循环）队列

---

#include<iostream>
using namespace std;
template <class T>
class Queue
{
	public:	
		Queue(int size);					//构造函数 
		~Queue(){delete []data;};			//析构函数 
		bool enQueue(T &x);					//入队函数 
		bool deQueue(T &x);					//出队函数 
		bool getFront(T &x);				//获取队头的元素函数 
		void makeEmpty();					//置空 
		bool isEmpty()const;				//判空 
		bool isFull()const;					//判满 
		int getSize()const;					//获取队列元素数量 
	protected:
		T *data;
		int front,rear;
	 	int maxSize;
};
template<class T>
Queue<T>::Queue(int size)
{
	maxSize=size+1;              //因为需要空出一个作为判断空满状态的空间 
	data=new T[size];
	front=rear=0;
}
template<class T>
bool Queue<T>::isEmpty()const
{
	if(rear==front)								//注意判空条件 
	return true;
	else
	return false;
}
template<class T>
bool Queue<T>::isFull()const
{
	if((rear+1)%maxSize==front)					//注意判满条件 
	return true;
	else
	return false;
}
template<class T>
int Queue<T>::getSize()const
{
	return (rear-front+maxSize)%maxSize;		//注意队列长度如何计算 
} 
template<class T>
bool Queue<T>::enQueue(T &x)
{
	if(isFull())
	return false;
	else
	{
		data[rear]=x; 
		rear=(rear+1)%maxSize;					//注意每次进数后 rear+1 并且求余数 
		return true;
	}
}	
template<class T>
bool Queue<T>::deQueue(T &x)
{
	if(isEmpty())
	return false;
	x=data[front];
	front=(front+1)%maxSize;					//注意每次取数后 rear+1 并且求余数 
	return true; 
} 
template<class T>
bool Queue<T>::getFront(T &x)
{
	if(isEmpty())
	return false;
	x=data[front];
	return true; 
}
template<class T>
void Queue<T>::makeEmpty()
{
	front=rear=0;
}
int main()
{
	int num,x;
	Queue<int> test1(3);
	cout<<"输入需要的数据数量";
	cin>>num; 
	for(int i=0;i<num;i++)
	{
		cin>>x;
		test1.enQueue(x);
	}
	for(int i=0;i<num;i++)
	{
		if(test1.deQueue(x))
		cout<<x<<","; 
	}
} 
/*
1、顺序循环表的判空满有很多种方法，这里我们使用一种方法申请的空间中要有一个空间空出来，用来判断空满状态。 
2、rear=front为空
3、（rear+1）%maxSize==front 避免如:max=8,7+1!=0判为不满的情况
4、入队列 每次都要rear=（rear+1）%maxSize，保存下标在范围内循环
5、同理，出队列每次也要front=（front+1）%maxSize
6、计算队列长为（rear-front+maxSize）%maxSize，避免负数计算错误
*/

1、顺序循环表的判空满有很多种方法，这里我们使用一种方法申请的空间中要有一个空间空出来，用来判断空满状态。

2、rear=front为空

3、（rear+1）%maxSize==front 避免如:max=8,7+1!=0判为不满的情况

4、入队列 每次都要rear=（rear+1）%maxSize，保存下标在范围内循环

5、同理，出队列每次也要front=（front+1）%maxSize

6、计算队列长为（rear-front+maxSize）%maxSize，避免负数计算错误

链（循环）队列（带头节点）

---

#include<iostream>
using namespace std;
template <class T>
struct LinkNode
{
	T data;
	LinkNode *next; 
	LinkNode()
	{
		next=NULL;
	}
	LinkNode(T x)
	{
		data=x;
	}
	LinkNode(LinkNode<T> *p)
	{
		next=p;
	}
	LinkNode(T x,LinkNode<T> *p)
	{
		data=x;
		next=p;
	}	
};
template<class T>
class Queue
{
	public:	
		Queue();					//构造函数 
		~Queue(){makeEmpty();};			//析构函数 
		bool enQueue(T &x);					//入队函数 
		bool deQueue(T &x);					//出队函数 
		bool getFront(T &x);				//获取队头的元素函数 
		void makeEmpty();					//置空 
		bool isEmpty()const;				//判空 
		int getSize()const;					//获取队列元素数量 
		void output();
	protected:
		LinkNode<T> *head,*rear;			//多定义一个rear,入队列时方便后续插入 
};
template<class T>
Queue<T>::Queue()
{
	head=rear=new LinkNode<T>;
	head->next=head;
}
template<class T>
bool Queue<T>::isEmpty()const
{
	if(head->next==head)	
	return true;					
	else
	return false;
}
template<class T>
int Queue<T>::getSize()const
{
	LinkNode<T> *p=head->next;
	int num=0;
	while(p!=head)     
	 {
	 	num++;
	 	p=p->next;
	 }
	 return num;
}
template<class T>
bool Queue<T>::enQueue(T &x)
{
	LinkNode<T> *newNode=new LinkNode<T>(x);
	if(newNode==NULL)
	{
		cerr<<"申请空间失败";
		exit(1); 
	}
	newNode->next=rear->next;
	rear->next=newNode;
	rear=newNode;			//移动队尾 
	return true;
}	
template<class T>
bool Queue<T>::deQueue(T &x)
{	
	LinkNode<T> *p;
	if(isEmpty())
	return false;
	else
	{
		p=head->next;
		x=p->data;
		head->next=p->next;
		delete p;
		return true;
	}	
}
template<class T>
bool Queue<T>::getFront(T &x)
{
	if(isEmpty())
	return false;
	x=head->next->data;
	return true;
} 
template<class T>
void Queue<T>::makeEmpty()
{
	LinkNode<T> *p=head->next;
	while(head->next!=head)
	{
		head->next=p->next;
		delete p;
		p=head->next;
	}
}
template<class T>
void Queue<T>::output()
{
	LinkNode<T> *p=head->next;
	while(p!=head)
	{
		cout<<p->data;
		p=p->next; 	
	}
}
int main()
{
	int num,x;
	Queue<int> test1;
	cout<<"输入需要的数据数量";
	cin>>num; 
	for(int i=0;i<num;i++)
	{
		cin>>x;
		test1.enQueue(x);
	}
	test1.output();
	
	for(int i=0;i<num;i++)
	{
		test1.deQueue(x);
		cout<<x<<","; 
	}
} 
/*
1、因为是单向循环不是双向循环所以多定义一个rear,入队列时方便后续插入
2、后插法创建队列
*/

1、因为是单向循环不是双向循环所以多定义一个rear,入队列时方便后续插入

2、后插法创建队列