スタックとキューに関する面接問題(3)

5、一つの配列は二つのスタック構想を実現する:双方向成長法二つのスタックのスタック底はそれぞれ配列の両端を指し、スタック頂は絶えず別のスタックのスタック底に近い.プロセス:1、仮に配列の先頭をスタックの底とするスタックをStack 1と呼び、配列の末尾をスタックの底とするスタックStack 2とすると、Stack 1のスタックトップポインタがStack 2のスタックトップポインタより大きい場合、2を拡張する必要があり、PushとPop操作を実現するには、どのスタックを操作するかを決定するためにパラメータflagを複数送信する必要がある
考え方2:交互索引法/クロス索引-->欠点:空間の浪費、もし一つのスタックがいっぱいで、もう一つのスタックがまだ物を保存していないならば、この時ももともと配列の中に物を保存することができて、しかしスタックがいっぱいになったスタックに要素を挿入するならば、それでは空間が足りないため空間を開拓することができて、これが空間の浪費の利点です:1つの配列で2つのスタックを実現するだけではなくて、また複数のスタックを実現することができます
 
 
StackAndQueue.h

#pragma once

#include 
#include 
using namespace std;

template
class ArrayForTwoStack
{
public:
	ArrayForTwoStack()
		:_array(NULL)
		,_capacity(0)
		,top1(-2)
		,top2(-1)
	{}

	ArrayForTwoStack(const ArrayForTwoStack& stack)
	{
		_array = new T[stack._capacity];
		_capacity = stack._capacity;
		top1 = stack.top1;
		top2 = stack.top2;
		int count = top1 > top2 ? top1 : top2;

		for (size_t index = 0;index < count; ++index)
		{
			_array[index] = stack._array[index];
		}
	}

	~ArrayForTwoStack()
	{
		if (_array)
		{
			delete[] _array;
			_array = NULL;
		}
	}

	void Push(size_t flag,const T& data)
	{
		CheckCapacity();
		// flag             
		if (flag == 1)//flag 1 ，        1   
		{
			top1 += 2;
			_array[top1] = data;
		} 
		else// flag  1 ，        2   
		{
			top2 += 2;
			_array[top2] = data;
		}
	}

	void Pop(size_t flag)
	{
		if (flag == 1)
		{
			assert(top1 != -2);
			top1 -= 2;
		} 
		else
		{
			assert(top2 != -1);
			top2 -= 2;
		}
	}

	T& Top(size_t flag)
	{
		if (flag == 1)
		{
			assert(top1 != -2);
			return _array[top1];
		} 
		else
		{
			assert(top2 != -1);
			return _array[top2];
		}
	}

	bool Empty(size_t flag)
	{
		if (flag == 1)
		{
			if (top1 == -2)
			{
				return true;
			} 
			else
			{
				return false;
			}
		} 
		else
		{
			if (top2 == -1)
			{
				return true;
			} 
			else
			{
				return false;
			}
		}
	}

	size_t Size(size_t flag)
	{
		if (flag == 1)
		{
			assert(top1 != -2);
			return top1/2 + 1;
		} 
		else
		{
			assert(top2 != -1);
			return (top2 + 1)/2;
		}
	}
protected:
	void CheckCapacity()
	{
		if (((top1 + 2) >= _capacity) || ((top2 + 2) >= _capacity))
		{
			_capacity = _capacity * 2 + 3;
			T* tmp = new T[_capacity];

			int count = top1 > top2 ? top1 : top2;
			for (int index = 0;index <= count; ++index)
			{
				tmp[index] = _array[index];
			}

			delete[] _array;
			_array = tmp;
		}
	}
private:
	T* _array;
	size_t _capacity;
	int top1;//stack1     
	int top2;//stack2     
};

 
test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include "StackAndQueue.h"

void Test5()
{
	//         
	ArrayForTwoStack stack;
	stack.Push(1,1);
	stack.Push(1,2);
	stack.Push(1,3);
	stack.Push(1,4);
	stack.Push(1,5);
	cout<