1.介绍

在内存限制比较大的情况，我们需要用到栈结构。这时，要求栈的内存使用率要比普通的栈更高，该怎么办？

我们可以将两个栈合用一段连续的存储空间，如下图。

2.操作

（1）创建

开始创建时，初始化两个栈顶指针分别为-1和maxSize便于压栈函数统一。

template<typename T>
BdStack<T>::BdStack()
{
	maxSize = 10;
	top1 = -1;
	top2 = maxSize;
	data = new T[maxSize];
}

（2）判断栈满

由上图，我们可以发现当两个栈顶指针相邻，就说明栈已经满了。

template<typename T>
bool BdStack<T>::isFull()
{
	if (top2 - top1 == 1)
		return true;
	return false;
}

 （3）判空，这里我们需要分别判断。

template<typename T>
bool BdStack<T>::isEmpty1()
{
	if (top1 == -1)
		return true;
	return false;
}
template<typename T>
bool BdStack<T>::isEmpty2()
{
	if (top2 == maxSize)
		return true;
	return false;
}

（4）压栈

template<typename T>
bool BdStack<T>::push1(const T& val)
{
	if (isFull())
		return false;
	data[++top1] = val;
	return true;
}
template<typename T>
bool BdStack<T>::push2(const T& val)
{
	if (isFull())
		return false;
	data[--top2] = val;
	return true;
}

（5）退栈

template<typename T>
bool BdStack<T>::pop1()
{
	if (isEmpty1())
		return false;
	top1--;
	return true;
}
template<typename T>
bool BdStack<T>::pop2()
{
	if (isEmpty2())
		return false;
	top2++;
	return true;
}

 （6）查看栈顶元素

template<typename T>
const T& BdStack<T>::getTop1()
{
	if (isEmpty1())
		throw("error");
	return data[top1];
}
template<typename T>
const T& BdStack<T>::getTop2()
{
	if (isEmpty2())
		throw("error");
	return data[top2];
}

总的代码如下： 

#pragma once
template<typename T>
class BdStack
{
	T* data;
	int maxSize;
	int top1;
	int top2;
public:
	BdStack();
	~BdStack();
	void resize();
	bool isFull();
	bool isEmpty1();
	bool isEmpty2();
	bool push1(const T& val);
	bool push2(const T& val);
	bool pop1();
	bool pop2();
	const T& getTop1();
	const T& getTop2();
};
template<typename T>
void BdStack<T>::resize()
{
	T* p = data;
	data = new T[maxSize * 2];
	for (int i = 0; i < maxSize; i++)
		data[i] = p[i];
	maxSize *= 2;
	delete[]p;
}
template<typename T>
BdStack<T>::BdStack()
{
	maxSize = 10;
	top1 = -1;
	top2 = maxSize;
	data = new T[maxSize];
}
template<typename T>
BdStack<T>::~BdStack()
{
	delete[]data;
}
template<typename T>
bool BdStack<T>::isFull()
{
	if (top2 - top1 == 1)
		return true;
	return false;
}
template<typename T>
bool BdStack<T>::isEmpty1()
{
	if (top1 == -1)
		return true;
	return false;
}
template<typename T>
bool BdStack<T>::isEmpty2()
{
	if (top2 == maxSize)
		return true;
	return false;
}
template<typename T>
bool BdStack<T>::push1(const T& val)
{
	if (isFull())
		return false;
	data[++top1] = val;
	return true;
}
template<typename T>
bool BdStack<T>::push2(const T& val)
{
	if (isFull())
		return false;
	data[--top2] = val;
	return true;
}
template<typename T>
bool BdStack<T>::pop1()
{
	if (isEmpty1())
		return false;
	top1--;
	return true;
}
template<typename T>
bool BdStack<T>::pop2()
{
	if (isEmpty2())
		return false;
	top2++;
	return true;
}
template<typename T>
const T& BdStack<T>::getTop1()
{
	if (isEmpty1())
		throw("error");
	return data[top1];
}
template<typename T>
const T& BdStack<T>::getTop2()
{
	if (isEmpty2())
		throw("error");
	return data[top2];
}