基于靜態(tài)數(shù)組實(shí)現(xiàn),內(nèi)部預(yù)設(shè)一個(gè)很大的數(shù)組對(duì)象, 實(shí)現(xiàn)簡(jiǎn)單，缺點(diǎn)是空間受限。
基于動(dòng)態(tài)數(shù)組實(shí)現(xiàn),內(nèi)部預(yù)設(shè)一個(gè)容量值,然后分配一段內(nèi)存空間數(shù)組,如果入棧大于默認(rèn)容量值時(shí),則再次擴(kuò)大分配新的內(nèi)存數(shù)組,并將舊數(shù)組拷貝至新數(shù)組及釋放舊數(shù)組.
基于雙向循環(huán)鏈表實(shí)現(xiàn)

棧的函數(shù)需要實(shí)現(xiàn)如下所示:

T pop() : 出棧并返回棧頂元素
void push(const T &t) : 入棧
const T & top() const : 獲取const類(lèi)型棧頂元素
T &top() : 獲取棧頂元素
int length() const: 獲取數(shù)量(父類(lèi)已經(jīng)實(shí)現(xiàn))void clear(): 清空棧(父類(lèi)已經(jīng)實(shí)現(xiàn))

本章,我們實(shí)現(xiàn)的?；趧?dòng)態(tài)數(shù)組實(shí)現(xiàn),它的父類(lèi)是我們之前實(shí)現(xiàn)的Vector類(lèi)：

C++ 動(dòng)態(tài)數(shù)組模版類(lèi)Vector實(shí)例詳解

所以代碼實(shí)現(xiàn)會(huì)非常簡(jiǎn)單.

2.棧實(shí)現(xiàn)

代碼如下所示:

#ifndef Stack_H
#define Stack_H
#include "throw.h"
// throw.h里面定義了一個(gè)ThrowException拋異常的宏,如下所示:
//#include <iostream>
//using namespace std;
//#define ThrowException(errMsg)  {cout<<__FILE__<<" LINE"<<__LINE__<<": "<<errMsg<<endl; (throw errMsg);}
#include "Vector.h"
template<class T>
class Stack : public Vector<T>
{
public:
    T pop()
    {
        if(Vector<T>::isEmpty()) {        // 如果棧為空,則拋異常
            ThrowException("Stack is empty ...");
        }
        T t = Vector<T>::data()[Vector<T>::length() - 1];
        Vector<T>::resize(Vector<T>::length() - 1);
        return  t;
    }
    // 入棧,實(shí)際就是append尾部添加成員
    void push(const T &t)
    {
        Vector<T>::append(t);
    }
    T &top()
    {
        if(Vector<T>::isEmpty()) {
            ThrowException("Stack is empty ...");
        }
        return Vector<T>::data()[Vector<T>::length() - 1];
    }
    const T &top() const
    {
        if(Vector<T>::isEmpty()) {
            ThrowException("Stack is empty ...");
        }
        return Vector<T>::data()[Vector<T>::length() - 1];
    }
};
#endif // Stack_H

3.代碼測(cè)試

int main(int argc, char *argv[])
{
    Stack<int> stack;
    cout<<"******* current length:"<<stack.length()<<endl;
    for(int i = 0; i < 5; i++) {
        cout<<"stack.push:"<<i<<endl;
        stack.push(i);
    }
    cout<<"******* current length:"<<stack.length()<<endl;
    while(!stack.isEmpty()) {
        cout<<"stack.pop:"<<stack.pop()<<endl;
    }
    return 0;
}

運(yùn)行打印: