双端堆栈（两栈共享存储空间）

优点：提高空间利用率

c 写法： stack.hpp

代码语言：javascript复制

#include<iostream>
#include<string>
#include<cstdlib>
using namespace std;
#define MAX 100
//双端堆栈:一个是数组前面，一个从数组后面算起
template<class Data>
class stack {
private:
	int size;//栈的大小（不是栈中当前元素个数）
	int top1;//第一个栈中的栈顶，可以理解为当前栈中元素个数
	int top2;//第二个栈中的栈顶
	Data* data;//指向栈数组
public:
	stack();
	stack(int size);
	~stack();
	void push(int top, Data data);
	void pop(int top);
	Data getTop(int top);//top表示是栈1还是栈2
	bool isEmpty(int top);
	class empty{};
	class full{};
};
template<class Data>
stack<Data>::stack() 
{
	size = MAX;
	top1 = -1;
	top2 = size;
	data = new Data[size];
}
template<class Data>
stack<Data>::stack(int size)
{
	this->size = size;
	top1 = -1;
	top2 = size;
	data = new Data[size];
}
template<class Data>
stack<Data>::~stack()
{
	delete[] data;
}
template<class Data>
void stack<Data>::push(int top,Data d)
{
	//判断堆栈是否已满
	if (top1 == top2 - 1)
	{
		throw full();
	}
	//如果是栈1（数组前面的部分插入）
	if (top == 1)
	{
		//改变了top的值，并且完成了赋值操作
		data[  top1] = d;
	 }
	//如果是栈2（数组后面的部分插入）
	if (top == 2)
	{
		data[--top2] = d;
	}
}
template<class Data>
bool stack<Data>::isEmpty(int top)
{
	if (top == 1)
	{
		if (top1 == -1)
		{
			return true;
		}
		return false;
	}
	if (top == 2)
	{
		if (top2 ==size)
		{
			return true;
		}
		return false;
	}
}
template<class Data>
void stack<Data>::pop(int top)
{
	 //判断堆栈是否为空
	if (top == 1)
	{
		if (isEmpty(1))
		{
			//匿名对象
			throw empty();
		}
	}
	if (top == 2)
	{
		if (isEmpty(2))
		{
			//匿名对象
			throw empty();
		}
	}
	//从栈1出栈
	if (top == 1)
	{
		top1--;
	}
	//栈2出栈
	if (top == 2)
	{
		top2  ;
	}
}
template<class Data>
Data stack<Data>::getTop(int top)
{
     //如果栈1为空，返回NULL
	if (top ==1&&top1==-1)
	{
		return NULL;
	}
	if (top == 2 && top2 ==size)
	{
		return NULL;
	}
	if (top == 1)
	{
		return data[top1];
	}
	if (top == 2)
	{
		return data[top2];
	}
}

main,cpp

代码语言：javascript复制

#include<iostream>
#include<string>
#include<cstdlib>
using namespace std;
#include"stack.hpp"
//测试代码--------------------------------
void test()
{
	stack<int> s(10);
	//向栈1中输入元素
	try {
		s.push(1, 1);
		s.push(1, 2);
		s.push(1, 3);
		//向栈2中输入元素
		s.push(2, 4);
		s.push(2, 9);
		s.push(2, 6);
	}
	catch (stack<int>::full) 
	{
		cout << "堆栈空间已满，无法插入数据" << endl;
	}
	try {
		//进行打印:栈1和栈2都不为空才进行打印
		while (!s.isEmpty(2))
		{
			int temp = s.getTop(2);
			cout << temp << " ";
			s.pop(2);
		}
	}
	catch (stack<int>::empty)
	{
		cout << "当前堆栈为空，删除失败" << endl;
	}
}
int main()
{
	test();
	system("pause");
	return 0;
}

没有异常抛出

存在异常抛出的情况

c++ stack 异常

0 人点赞