?
#pragma once
#include<iostream>
using namespace std;
template<class T>
class double_stack
{
//来一波双向的栈,因为有的栈要的空间大,有的栈要的空间小。
// 因此,就是比普通的栈,空间利用率高一点。
int top1;
int top2;
T* data;
unsigned size;
void resize();
public:
enum which{first,second};
double_stack(unsigned num=10);
~double_stack();
bool empty()const;
bool full()const;
void push(const T& obj, which tmp);
bool pop(which tmp);
T top(which tmp)const;
};
template<class T>
void double_stack<T>::resize()
{
T* p = data;
data = new(std::nothrow) T[size * 2];
if (data)
{
for (unsigned i = 0; i < size; i++)
data[i] = p[i];
size = size * 2;
top2 = size - (size / 2 - top2);
delete[]p;
}
else std::cerr << "bad new" << std::endl;
}
template<class T>
double_stack<T>::double_stack(unsigned num)
{
top1 = -1;
top2 = num;
data = new T[num];
size = num;
}
template<class T>
double_stack<T>::~double_stack()
{
delete[]data;
}
template<class T>
bool double_stack<T>::empty()const
{
return top1 == - 1&&top2==size;
}
template<class T>
bool double_stack<T>::full()const
{
return top1 == top2 - 1;
}
template<class T>
void double_stack<T>::push(const T& obj, which tmp)
{
if (full())
resize();
if (tmp == first)
data[++top1] = obj;
else data[--top2] = obj;
}
//为啥push返回void,而pop返回bool呢?
//因为空间不够,不能push,我能resize,返回值肯定是true没意思
//但没有元素,我又不能变出来,也用不着返回异常。
template<class T>
bool double_stack<T>::pop(which tmp)
{
if (empty()|| (tmp == first && top1 == -1) || (tmp == second && top2 == size))
return false;
else if (tmp == first)
top1--;
else top2++;
}
template<class T>
T double_stack<T>::top(which tmp)const
{
if (empty() || (tmp==first&&top1 == -1) || (tmp==second&&top2 == size))
throw ("get top error");
else if (tmp == first)
return data[top1];
else return data[top2];
}
|