这一节涉及到栈，队列，双端队列及一些组合形式，为了突出重点，简化问题，令元素类型一律为int，物理存储结构一律采用定长数组。
例题1 :栈
下面的代码就实现了一个简单的栈，栈内可容纳元素个数有上限。在实现每个类型的时候都应该问问自己，为什么需要维护这些数据成员，多一个会不会更好？少一个可行吗？
因为栈是一种逻辑数据结构，而每种逻辑数据结构的实现都需要依赖一种物理存储结构的支持，这里我选择了数组，所以我需要维护一个数组及其总长度（m_array和m_totalLength）。
由于Push、Pop、Top方法中待处理元素的位置信息，不是由参数给定的，而是由栈自身维护的，所以我还需要记录当前待处理元素（这里指的是栈顶元素）的下标(m_top)，其取值范围是[-1, m_totalLength-1]。
m_top的作用之一是用来计算栈顶元素所对应的数组元素的下标f(m_top)，从而将逻辑层操作转化成存储层的操作，这里我将映射法则定义为f(m_top) = m_top。
m_top的作用之二是计算:当前栈内元素个数 = m_top + 1，从而判断栈是否为空或已满。
这已经是数据成员最精简的版本，一个也不能少，多一个也没必要。
class Stack { public: Stack(int len); //len表示栈的最大长度 void Push(int val); //压栈，若栈已满，报错”Overflow“ void Pop(); //出栈，若栈为空，报错”Underflow“ int Top() const; //读取栈顶，若栈为空，报错”Empty“ bool IsEmpty() const; //栈是否为空 bool IsFull() const; //栈是否已满 private: int* m_array; //数组 const int m_totalLength; //栈的最大长度，也是数组的总长度 int m_top; //栈顶元素下标 }; Stack::Stack(int len) :m_totalLength(len), m_array(new int[len]), m_top(-1) {} void Stack::Push(int val) { if(IsFull()) cerr << "Overflow" << endl; else m_array[++m_top] = val; } void Stack::Pop() { if(IsEmpty()) cerr << "Underflow" << endl; else --m_top; } int Stack::Top() const { if(IsEmpty()) { cerr << "Empty" << endl; return -1; } else return m_array[m_top]; } bool Stack::IsEmpty() const { return m_top == -1; } bool Stack::IsFull() const { return m_top == m_totalLength - 1; }例题2：队列
同样的，队列可同时容纳元素个数有上限。我都需要保存哪些数据成员呢？
数组及其总长度（m_array, m_totalLength）
入队，出队方法中待处理元素位置信息，这里指的是队头和队尾元素的下标，同样需要由方法内部维护（m_begin, m_end）。
m_begin, m_end的作用之一是计算队头、队尾所对应数组元素下标，依据逻辑含义应是只增不减的，而依据环形队列的映射法则计算出的数组元素下标是在[0, m_totalLength)区间内循环取值的。
m_begin, m_end的作用之二是计算当前容纳元素个数，作为判断操作合法性的边界条件。
具体实现中，在不影响上述两作用的前提下，必须对m_begin,m_end的值加以限制。（见方法Dequeue）
由于入队，出队方法的被调用频率不同且无关，必须被记录至两个变量中，所以数据成员不能更少了。
class Queue { public: Queue(int len); void Enqueue(int val); void Dequeue(); int Front() const; int Back() const; bool IsEmpty() const; bool IsFull() const; private: int IndexInArray(indexInQueue) const; private: int* m_array; const int m_totalLength; int m_begin; //index of front element int m_end; //index of the one next to back element }; Queue::Queue(int len) : m_totalLength(len), m_array(new int[len]), m_begin(0), m_end(0) { } void Queue::Enqueue(int val) { if(IsFull()) cerr << "Overflow" << endl; else { m_array[IndexInArray(m_end)] = val; ++m_end; } } void Queue::Dequeue() { if(IsEmpty()) cerr << "Underflow" << endl; else { ++m_begin; //限制m_begin,m_end取值范围 if(m_begin >= m_totalLength) { m_begin -= m_totalLength; m_end -= m_totalLength; } } } int Queue::Front() const { if(IsEmpty()) { cerr << "Empty" << endl; return -1; } return m_array[IndexInArray(m_begin)]; } int Queue::Back() const { if(IsEmpty()) { cerr << "Empty" << endl; return -1; } return m_array[IndexInArray(m_end - 1)]; } bool Queue::IsEmpty() const { return m_begin == m_end; } bool Queue::IsFull() const { return m_end - m_begin == m_totalLength; } int Queue::IndexInArray(indexInQueue) const { assert(indexInQueue >= 0); return indexInQueue % m_totalLength; }习题10.1-2
不失一般性，把数组视为环形数组。
因为需要把一个数组分给两个栈使用，所以我们需要设置一个分界线，两个栈分别以分界线处两个相邻元素为起点，分别向左右两个方向生长，直到二者总长度达到数组总长度为止。
如此说来，除了数组和总长度外，还需要保存一个常量（分界线的位置m_divide）和两个变量（两个栈顶元素下标m_top[A],m_top[B]）。
m_top[A]和m_top[B]保存的是逻辑层的栈内下标，它的作用和Stack::m_top以及Queue::m_begin，Queue::m_end都是一样的，一是计算对应的数组元素下标，二是计算边界条件，判断调用合法性。
以上三个类型的实现有一些共同的逻辑。是时候来总结一下了。