一個數組實作兩個棧
棧（stack）,是限定在表尾進行插入或删除操作的線性表，對棧來說，表尾端稱為棧頂，表頭稱為棧底。
實作棧首先應該對棧中資料元素和棧頂指針的關系有清楚的認識
棧頂指針和棧中元素的關系
壓棧
用一個數組實作兩個棧，有多種方法，但基本思路就下面三種方法，下面我們分别介紹下各種算法，幾種算法的實作差別不大，主要在與擴容時的條件，下面我們主要側重于幾種算法的擴容
（1）、
我們可以采用兩個棧底分别在數組中間，棧頂向兩邊移動，當兩個棧頂任意一個到達數組的兩邊時，數組擴容。
此種算法有兩個擴容條件，二者滿足其一便擴容：
條件1：
條件2：
（2）、
兩個棧的棧底分别在數組的兩邊，壓棧時棧頂向中間靠攏，當兩個棧頂相遇時，數組擴容。
在代碼的實作時我們決定在拷貝構造和指派操作符的重載時采取隻對有資訊的部分進行開辟空間，進而節省了空間和時間。（在實際情形中，我們在使用拷貝構造和指派時往往隻在意是否拷貝到了自己想要的資訊，并不在乎空間的開辟，而且使用者根本也不知道内部是如何實作的，是以提高效率還是很有必要的）
為了節省空間，我們采取上述拷貝構造方式，隻拷貝有資訊的部分。
（3）、
采用交叉索引的方法，兩個棧分别擁有數組下标奇偶的空間，我們暫且把他們叫做奇數棧和偶數棧，我們把數組空間開辟為偶數（capacity），當偶數棧的棧頂到capacity-1或奇數棧的棧頂到達capaaity-2時數組擴容
此種算法擴容條件有兩個，滿足任意一個便擴容
條件1：
條件2：
下面我們分析下這幾種方法：
從代碼的實作上，幾種算法的難易程度相當，
我們分别從程式的效率、空間使用率以及可維護性幾方面進行對比
效率：過上面對幾種方法的介紹，在程式的效率方面幾種方法差別不是非常大，但第一種和第三種明顯在擴容時考慮的情況比較複雜，條件更多一些。
空間使用率：第一種和第三種方法在其中一個棧壓入比較多的資料而另外一個棧資料很少時，就存在非常大的空間浪費，但方案二就可以很好的避免這一情況，空間使用率比較高，而且這種方案在一個棧pop的空間另一個棧可以使用，可以在一些情況下減少開辟空間的次數（畢竟在c++中動态開辟空間還是很耗時的）
綜上
我們選擇第二種方案。
//（部落客現在才明白其實在程式設計的整個過程中，最重要的是對問題的了解以及對于各種算法的了解，在代碼的實作上，我們不能一步而蹴，先把簡單的實作，再逐漸優化，不要一開始被最優解把自己綁架了，什麼事情都有一個循序漸進的過程，我們在平時的學習中，就應該一層一層分析，直至最後得到我們認為的最優方案）（僅僅是個人學習這麼久的感悟）
以下我們把方案二的代碼簡單的實作下
template<class T>
class TwoStack
{
public:
TwoStack()
:_a(0)
,_top1(0)
,_top2(0)
,_capacity(0)
{
}
~TwoStack()
{
if(_a != NULL)
{
delete [] _a;
}
}
TwoStack( const TwoStack<T>& ts)
:_a(new T[ ts._capacity -ts._top2 +ts._top1])//size+1
,_top1(ts._top1)
,_top2(_top1)
,_capacity( ts._capacity -ts._top2 +ts._top1)
{
size_t j = ts._capacity - 1;
for(size_t i = 0; i<=_top1; i++)
{
_a[i] = ts._a[i];
}
for(size_t i = _capacity-1; i >_top2; i--,j--)
{
_a[i] = ts._a[j];
}
}
TwoStack<T>& operator= (TwoStack<T> ts)
{
_top1 = ts._top1;
_top2 = ts._top2;
_capacity = ts._capacity;
swap(_a,ts._a);
return *this;
}
void Push(const T& x,int choice)
{
_CheckCapacity();
if(choice == 0)
{
_a[_top1++] = x;
}
if(choice ==1)
{
_a[_top2--] = x;
}
}
void Pop(int choice)
{
if(choice == 0)
{
assert(_top1 > 0);
_top1--;
}
if(choice == 1)
{
assert(_top2 <_capacity-1);
_top2++;
}
}
T& Top(int choice)
{
if(choice == 0)
{
assert(_top1 > 0);
return _a[_top1-1];
}
if(choice == 1)
{
assert(_top2 <_capacity-1);
return _a[_top2+1];
}
}
bool Empty(int choice)
{
if(choice == 0)
{
return _top1 == 0;
}
if(choice == 1)
{
return _top2 ==_capacity-1;
}
}
size_t Size(int choice)
{
if(choice == 0)
{
return _top1;
}
if(choice == 1)
{
return _capacity-1-_top2;
}
}
void Print()
{
cout << "棧0為：";
for(size_t i = 0; i<_top1; i++)
{
cout << _a[i] <<" ";
}
cout<<endl;
cout << "棧1為：";
for(size_t j = _capacity-1; j>_top2; --j)
{
cout << _a[j] << " ";
}
cout <<endl<<endl;
}
protected:
void _CheckCapacity()
{
if(_a == NULL)
{
_capacity = 3;
_a = new T[_capacity];
_top2 = _capacity - 1;//此時不要忘了給_top2指派，構造時給的是0
return;
}
if(_top1 == _top2)
{
size_t j = 0;
size_t oldCapacity = _capacity;//記住原來的
_capacity = 2 * _capacity;
T* tmp = new T[_capacity];
for(size_t i = 0;i <_top1;i++)//正向拷貝
{
tmp[i] = _a[i];
}
for(size_t i = _capacity-1, j = oldCapacity-1; j >_top2; i--, j--)//反向拷貝
{
tmp[i] = _a[j];
}
delete [] _a;
_a = tmp;
_top2 = (_capacity-1) - (oldCapacity-1-_top2);// 最後一個下标-元素個數
}
}
protected:
T* _a;
size_t _top1;
size_t _top2;
size_t _capacity;
};
以下是測試代碼
#include"test.h"
void Test()
{
TwoStack<int> ts1;
ts1.Push(1,0);
ts1.Push(2,0);
ts1.Push(3,0);
ts1.Push(4,0);
ts1.Push(5,1);
ts1.Push(6,1);
ts1.Push(7,1);
ts1.Push(8,1);
TwoStack<int> ts2(ts1);
TwoStack<int> ts3 ;
ts3 = ts1;
cout<<"ts1"<<endl;
cout<<"棧0："<<endl;
cout << "ts1.Size(0):"<<ts1.Size(0) <<endl;
while( !ts1.Empty(0) )
{
cout<<ts1.Top(0)<<' ';
ts1.Pop(0);
}
cout<<endl<<"棧1："<<endl;
cout << "ts1.Size(1):"<<ts1.Size(1) <<endl;
while( !ts1.Empty(1) )
{
cout<<ts1.Top(1)<<' ';
ts1.Pop(1);
}
cout<<endl<<endl<<"拷貝構造的ts2"<<endl;
ts2.Print();
cout<<"指派後的ts3"<<endl;
ts3.Print();
}
int main()
{
Test();
getchar();
return 0;
}
轉載于:https://blog.51cto.com/10810196/1763372