栈的使用非常广泛,常常会出现在一个程序中需要 同时使用多个栈的情形。为了不因栈上溢而产生错 误中断,要给每个栈预分较大空间,但各个栈实际 所用最大空间很难估计。而且各个栈的实际容量在 使用期间是变化的,往往会出现某个栈发生上溢, 而另一个栈还是空的。 试设想,若令多个栈共享空间,则将提高空间的使 用效率,并减少发生栈上溢的可能性
栈的使用非常广泛，常常会出现在一个程序中需要 同时使用多个栈的情形。为了不因栈上溢而产生错 误中断，要给每个栈预分较大空间，但各个栈实际 所用最大空间很难估计。而且各个栈的实际容量在 使用期间是变化的，往往会出现某个栈发生上溢， 而另一个栈还是空的。 试设想，若令多个栈共享空间，则将提高空间的使 用效率，并减少发生栈上溢的可能性
假设在程序中需设两个栈,并共享一维数组空间v[m]。 则利用“栈底位置不变”的特性,可将两个栈的栈底分 别设在数组空间的两端,然后各自向中间伸展(如图3.3 所示),仅当两个栈的栈顶相遇时才可能发生上溢。由 于两个栈之间可以做到互补余缺,使得每个栈实际可利 用的最大空间大于m/2。显然,两个栈顶的初值分别为-1 和m 平栈1底 栈1顶 平栈2顶 栈2底 图3.3两个顺序栈共享空间示意图
假设在程序中需设两个栈，并共享一维数组空间v[m]。 则利用“栈底位置不变”的特性，可将两个栈的栈底分 别设在数组空间的两端，然后各自向中间伸展（如图3.3 所示），仅当两个栈的栈顶相遇时才可能发生上溢。由 于两个栈之间可以做到互补余缺，使得每个栈实际可利 用的最大空间大于m/2。显然，两个栈顶的初值分别为-1 和m
313栈的链式存储结构 栈的链式存储结构称为链栈,它是运算受限的单链表, 其插入和删除操作仅限制在表头位置上进行。 由于只能在链表头部进行操作 top 故链栈没有必要象单链表那样 附加上头结点。栈顶指针就是 链表的头指针,如图3.4所示, 链栈就是无头结点的单链表 (头指针改称栈顶指针),因图3.4链栈示意图 此不再重新讨论
栈的链式存储结构称为链栈，它是运算受限的单链表， 其插入和删除操作仅限制在表头位置上进行。 3.1.3 栈的链式存储结构 由于只能在链表头部进行操作， 故链栈没有必要象单链表那样 附加上头结点。栈顶指针就是 链表的头指针，如图3.4所示， 链栈就是无头结点的单链表 （头指针改称栈顶指针），因 此不再重新讨论
32栈的应用举例 栈的应用非常广泛,只要问题满足LIFO原则,均可使 用栈做数据结构。 ∥/顺序栈的模板类接口定义以及基本运算的实现代码 template <class T> class sqstack i protected int*elem;∥/指向存放数据元素的数组指针 int top;∥/栈顶指针 int maxsize;∥/栈容量 public: sqStack( int ms=10);//构造函数
3.2 栈的应用举例 栈的应用非常广泛，只要问题满足LIFO原则，均可使 用栈做数据结构。 //顺序栈的模板类接口定义以及基本运算的实现代码 template <class T> class sqStack { protected: int *elem ; // 指向存放数据元素的数组指针 int top ; // 栈顶指针 int maxSize; // 栈容量 public: sqStack(int ms=10); // 构造函数
tsTack( const sastack<>s);//复制构造函数 ~ sqStack(){ delete[]elem;}//析构函数 saStack& operator=(const sastack<r>&)i /“=”运算符重载 bool isEmpty oi return top /判栈“空”否? boo1isFu1()//判栈“满”否? i return top maxSize-1 boo1push(m);//进栈(插入、压栈) bool Pop();//出栈(删除、退栈) bool GetTop(s);//取栈顶元素
sqStack (const sqStack<T>&); // 复制构造函数 ~sqStack() { delete[] elem; } // 析构函数 sqStack& operator=(const sqStack<T>&); // “=”运算符重载 bool isEmpty() { return top == -1 ; } // 判栈“空”否？ bool isFull() // 判栈“满” 否？ { return top == maxSize-1; } bool Push(T); // 进栈 (插入、压栈) bool Pop(); // 出栈 (删除、退栈) bool GetTop(T &); // 取栈顶元素 };