顺序栈以及双栈的设计与测试

---

返回目录

---

一、顺序栈

1、类设计

template<class T,int MAXSIZE>
class SeqStack
{
public:
	SeqStack();
	~SeqStack();
private:
	T data[MAXSIZE];		//数据域
	int top;				//栈顶标志
public:
	bool Push(T x);			//压栈
	T Pop();				//出栈
	T Top();				//取首元素
	bool IsEmpty();			//判空
	bool IsFull(void);		//判满
	int Size();				//返回个数
};

2、具体实现

#include "SeqStack.h"
/**
* 无参数构造函数
* 作用:栈顶置空，生成空栈
* @param[in] 无
* @param[out] 无
*/
template<class T, int MAXSIZE>
SeqStack<T,MAXSIZE>::SeqStack()
{
	top = -1;
}

/**
* 析构函数
* 作用:垃圾回收
* @param[in] 无
* @param[out] 无
*/
template<class T, int MAXSIZE>
SeqStack<T, MAXSIZE>::~SeqStack()
{
}

/**
* 压栈操作
* 作用:将元素压入栈顶
* @param[in] T x
* @param[out] 成功返回true
*/
template<class T, int MAXSIZE>
bool SeqStack<T, MAXSIZE>::Push(T x)
{
	if (top==MAXSIZE-1)
	{
		cerr << "上溢" << endl;
		return false;
	}
	top++;
	data[top] = x;
	return true;
}

/**
* 出栈操作
* 作用:将栈顶元素弹出
* @param[in] 
* @param[out]T x
*/
template<class T, int MAXSIZE>
T SeqStack<T, MAXSIZE>::Pop()
{
	if (!IsEmpty())
	{
		T x = data[top];
		top--;
		return x;
	}
	else
	{
		cerr << "下溢" << endl;
	}
}

/**
* 取出栈顶元素
* 作用:将栈顶元素取出
* @param[in]
* @param[out]T x
*/
template<class T, int MAXSIZE>
T SeqStack<T, MAXSIZE>::Top()
{
	if (!IsEmpty())
		return data[top];
	else
		cerr << "下溢" << endl;
}

/**
* 判空
* 作用:判断栈是否空
* @param[in]
* @param[out]  布尔值
*/
template<class T, int MAXSIZE>
bool SeqStack<T, MAXSIZE>::IsEmpty()
{
	return top==-1;
}

/**
* 判空
* 作用:判断栈是否满
* @param[in]
* @param[out]  布尔值
*/
template<class T, int MAXSIZE>
bool SeqStack<T, MAXSIZE>::IsFull()
{
	return top == maxSize - 1; 
}

/**
* 元素个数
* 作用:返回栈元素个数
* @param[in]
* @param[out]  返回元素个数
*/
template<class T, int MAXSIZE>
int SeqStack<T, MAXSIZE>::Size()
{
	if (top!=-1)
	{
		return top+1;
	}
	return 0;
}

3、测试

	SeqStack<int,100> a;
    //压入数据  
    for (int i = 0; i < 10; i++)  
    {  
        a.Push(i);  
    }  
  
    //栈的大小  
	cout<< "栈元素个数："<<a.Size()<<endl;

  	//栈顶元素
	cout << "栈顶元素：" << a.Top() << endl;

    //取栈项数据并将数据弹出栈  
    while (!a.IsEmpty())  
    {  
		cout << "顺序出栈：" << a.Pop() << endl;
    }  
``` 
测试截图：
![此处输入图片的描述][2]

### 4、总结
>+ 栈（statck）这种数据结构在计算机中是相当出名的。
>+ 栈中的数据是先进后出的（FILO）。
>+ 根据这个特性，可以很好的利用这种结构。
>+ top()、push()、pop()、empty()是比较常用的方法。


----------


----------
# **二、双栈**
## 1、类设计
```cpp
template<class T, int MaxSize>
class SeqStack
{
public:
	SeqStack();                         // 构造函数
	virtual ~SeqStack();				// 析构函数
	void Push(int i, T x);              // 对栈i压栈
	T Pop(int i);						// 对栈i出栈
	T Top(int i);						// 取栈i的栈顶元素
	int Size(int i);					//返回个数
	bool IsEmpty(int i);				// 判栈i是否空
	bool IsFull();					    // 判满
private:
	T data[MaxSize];					// 数据域
	int top1;							// 栈顶指针（栈1）
	int top2;							// 栈顶指针（栈2）
};
``` 


### 2、具体实现
```CPP
#include "SeqStack.h"

/**
* 无参数构造函数
* 作用:栈顶置空，生成空栈，栈1从头开始，栈2从底开始
* @param[in] 无
* @param[out] 无
*/
template<class T, int MaxSize>
SeqStack<T, MaxSize>::SeqStack()
{
	top1 = -1;
	top2 = MaxSize;
}

/**
* 析构函数
* 作用:垃圾回收
* @param[in] 无
* @param[out] 无
*/
template<class T, int MaxSize>
SeqStack<T, MaxSize>::~SeqStack()
{
}

/**
* 压栈操作
* 作用:将元素压入栈顶，根据标志i判断栈号
* @param[in] T x	int i
* @param[out] 
*/
template<class T, int MaxSize>
void SeqStack<T, MaxSize>::Push(int i,T x)
{
	if (IsFull())
	{
		cerr << "上溢！" << endl;
		exit(1);
	}
	if (i == 1)
	{
		top1++;
		data[top1] = x;
	}
	else if (i == 2)
	{
		top2--;
		data[top2] = x;
	}
	else
	{
		cout << "栈选择错误！默认存入栈1" << endl;
		top1++;
		data[top1] = x;
	}
}

/**
* 出栈操作
* 作用:将栈i顶部元素弹出
* @param[in] 
* @param[out]T x
*/
template<class T, int MaxSize>
T SeqStack<T, MaxSize>::Pop(int i)
{
	if (IsEmpty(i))
	{
		cerr << "下溢！" << endl;
		exit(1);
	}
	T x;
	if (i == 1)
	{
		x = data[top1];
		top1--;
	}
	else if (i == 2)
	{
		x = data[top2];
		top2++;
	}
	return x;
}

/**
* 取出栈顶元素
* 作用:将栈顶元素取出
* @param[in]
* @param[out]T x
*/
template<class T, int MaxSize>
T SeqStack<T, MaxSize>::Top(int i)
{
	if (IsEmpty(i))
	{
		cerr << "下溢！" << endl;
		exit(1);
	}
	if (i == 1)
	{
		return data[top1];
	}
	else if (i == 2)
	{
		return data[top2];
	}
		
}

/**
* 判空
* 作用:判断栈是否空
* @param[in]
* @param[out]  布尔值
*/
template<class T, int MaxSize>
bool SeqStack<T, MaxSize>::IsEmpty(int i)
{
	if (i == 1)
		return top1 == -1;
	if (i == 2)
		return top2 == MaxSize;
	return false;
}

/**
* 判空
* 作用:判断栈是否满
* @param[in]
* @param[out]  布尔值
*/
template<class T, int MaxSize>
bool SeqStack<T, MaxSize>::IsFull()
{
	return top1 + 1 == top2; 
}

/**
* 元素个数
* 作用:返回栈元素个数
* @param[in]
* @param[out]  返回元素个数
*/
template<class T, int MAXSIZE>
int SeqStack<T, MAXSIZE>::Size(int i)
{
	if (i==1)
	{
		return top1+1;
	} 

	else if (i==2)
	{
		return MAXSIZE-top2;
	}
	else
	{
		cerr<<"error"<<endl;
		exit(1);
	}
}

3、测试

int main()
{

	SeqStack<int, 100> a;
    //压入数据  
	for (int i=0;i<5;i++)
	{
		a.Push(1,i);
		a.Push(2,10-i);
	}
	

	//栈的大小  
	cout<< "栈1元素个数："<<a.Size(1)<<endl;
	cout<< "栈2元素个数："<<a.Size(2)<<endl;


	//栈顶元素
	cout << "栈1栈顶元素：" << a.Top(1) << endl;
	cout << "栈2栈顶元素：" << a.Top(2) << endl;


	// 出栈
	while (!a.IsEmpty(1))
	{
		cout << "栈1出栈：" << a.Pop(1) << endl;
	}

	while (!a.IsEmpty(2))
	{
		cout << "栈2出栈：" << a.Pop(2) << endl;
	}

	return 0;
}
``` 
测试截图：
![此处输入图片的描述][3]
错误测试：
```CPP
	//错误数据的测试
	a.Push(3,10);
	a.Push(3,11);

![此处输入图片的描述][4]

4、总结

• 与数组单栈相比，双栈更加节省空间
• 注意错误情况的处理

[4glb.clouddn.com/%E5%8F%8C%E6%A0%8801.png
3: http://7xi4ge.com1.z0.glb.clouddn.com/%E5%8F%8C%E6%A0%8802.png