《征服数据结构》双端栈

摘要：

1，双端栈的介绍

2，双端栈的代码实现

1，双端栈的介绍

双端栈主要利用了“栈底位置不变，栈顶位置动态变化” 的特点，可以让两个栈共享一块存储空间。在前面我们讲到用数组实现栈的时候，如果把数组的两端都当做栈底，就可以构造出两个栈。

双端栈是指将一个线性表的两端当做栈底分别进行入栈和出栈操作，如下图所示：

1，当 lTop==-1 时 表示左端栈为空，左端栈的有效元素个数为 lTop + 1 。

2，当 rTop==data.length 时，表示右端栈为空，右端栈的有效元素个数为 data.length - rTop 。

3，当 lTop+1==rTop 时，表示双端栈满 。

双端栈的常见函数相比普通栈的函数要多，因为双端栈要操作左右两个栈。