程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> C++采用模板實現棧的方法，采用模板實現

C++采用模板實現棧的方法，采用模板實現

編輯：C++入門知識

C++采用模板實現棧的方法，采用模板實現


今天又看了遍《effective C++》,手動實現了一下條款42中的棧，貼出來當博客的處女貼。

首先棧的聲明如下，采用了模板傳入類型，而棧的底層采用是個鏈表。

// stack.h
// by Chwen 2014-10-27 

#include<stdio.h>
#include <stdlib.h>
#include <iostream>

using namespace std;

// 棧聲明

template<typename T>
class Stack
{
public:
    Stack();
    ~Stack();

    void push(const T& node);
    T Top();
    void pop();
    int size()const;
    bool Empty() const;
    void clear();

private:
    struct StackNode
    {
        T data;
        StackNode* next;
        StackNode(const T& Newdata, StackNode* nextNode)
            :data(Newdata),next(nextNode)
        {}
    };
　　 
    StackNode * top;
    // 防止默認拷貝和默認賦值
    Stack(const Stack& rhs);
    Stack& operator=(const Stack& rhs);
    int mySize;
};

 

　　而對應的cpp實現如下：

// stack.cpp
 
#include "stack.h"
using namespace std;


// 棧實現

template<typename T>
Stack<T>::Stack()
    :top(nullptr),mySize(0)
{

}

template<typename T>
Stack<T>::~Stack()
{
    clear();
}

template<typename T>
void Stack<T>::push(const T& node)
{
    top = new StackNode(node,top);
    mySize ++;
}

template<typename T>
T Stack<T>::Top()
{
    if (Empty())
    {
        _DEBUG_ERROR("Error, stack is empty!");
    }
    return top->data;
}

template<typename T>
void Stack<T>::pop()
{
    if (Empty())
    {
        _DEBUG_ERROR("Error, stack is empty!");
    }
    StackNode* topOfStack = top;
    top = top->next;
    delete topOfStack;
    topOfStack = nullptr;
    mySize --;
    return;
}

template<typename T>
bool Stack<T>::Empty() const
{
    return top == nullptr;
}

template<typename T>
void Stack<T>::clear()
{
    while (top)
    {
        StackNode* topOfStack = top;
        top = top->next;
        delete topOfStack;

    }
    mySize = 0;
}
template<typename T>
int Stack<T>::size()const
{
    return mySize;
}

以上即是采用模板實現的棧的所有代碼，可以實現棧的push,  pop, top, clear 等操作。

以下寫了一個簡單的測試代碼：

void funv()
{
 
    Stack<int> s;

    for(int i = 0; i < 10; ++i)
    {
        s.push(i);
    }
    for(int j = s.size()-1 ; j >= 0; --j)
    {
        cout<< "node: " << s.Top() <<endl;
        s.pop();
    }

    s.clear();

}

int main ()
{
　　funv();
　　getchar();
　　return 0;
}

 


之後effective C++指出了另一種更精巧的方式實現，即私有繼承。

代碼實現如下：

// stack.h
// by Chwen 2014-10-27 
#include<stdio.h>
#include <stdlib.h>
#include <iostream>

class commonStack
{
protected:
    commonStack();
    ~commonStack();

    void push(void* node);
    void* Top();
    void pop();
    int size()const;
    bool Empty() const;
    void clear();

    
private:
    struct StackNode
    {
        void* data;
        StackNode* next;
        StackNode(void* Newdata, StackNode* nextNode)
            :data(Newdata),next(nextNode)
        {}
    };

    StackNode * top;
    // 防止默認拷貝和默認賦值
    commonStack(const commonStack& rhs);
    commonStack& operator=(const commonStack& rhs);
    int mySize;
};


template <typename T>
class Stack:private commonStack
{
public:
    void push(T * ty){commonStack::push(static_cast<void*>(ty));}
    T* top(){return static_cast<T*>(commonStack::Top());}
    void pop(){return commonStack::pop();}
    int size(){return commonStack::size();}
    bool Empty()const{ return commonStack::Empty(); }
    void clear(){return commonStack::clear();}
 

};

 

對應的cpp 如下：

 

 
#include "stack.h"
 
using namespace std;

commonStack::commonStack()
    :top(nullptr),mySize(0)
{

}

 
commonStack::~commonStack()
{
    clear();
}

 
void commonStack::push(void* node)
{
    top = new StackNode(node,top);
    mySize ++;
}

 
void* commonStack::Top()
{
    if (Empty())
    {
        _DEBUG_ERROR("Error, stack is empty!");
    }
    return top->data;
}

 
void commonStack::pop()
{
    if (Empty())
    {
        _DEBUG_ERROR("Error, stack is empty!");
    }
    StackNode* topOfStack = top;
    top = top->next;
    delete topOfStack;
    topOfStack = nullptr;
    mySize --;
    return;
}

 
bool  commonStack::Empty() const
{
    return top == nullptr;
}
 
void commonStack::clear()
{
    while (top)
    {
        StackNode* topOfStack = top;
        top = top->next;
        delete topOfStack;

    }
    mySize = 0;
}
 
int commonStack::size()const
{
    return mySize;
}

這裡commonStack將原模板類的T改為了void*, 之後使用protected保護該類不會被其他不明群眾調用，而是給出了一個模板接口類私有繼承這個類，這樣一來，既起到了保護作用，又在低損耗的情況下給出了方便易用的接口，巧奪天工的設計。

測試代碼如下：

void funcInt()
{
    int* a[10];
    for(int i = 0 ; i < 10; ++i)
    {
        a[i] = new int(i);
    }

    Stack<int> s;
    
    for(int j = 0 ; j < 10; ++j)
    {
        s.push(a[j]);
    }

    int k = s.size();
    int* t = s.top();
    s.pop();
    if(s.Empty())
    {
        cout<<"empty"<<endl;
    }
    s.clear();
    
    for(int i = 0 ; i < 10; ++i)
    {
        delete a[i] ;
    }

}

void funcString()
{
    string* str[10];
    for(int i = 0 ; i < 10; ++i)
    {
        str[i] = new string("a");
    }

    Stack<string> s;

    for(int j = 0 ; j < 10; ++j)
    {
        s.push(str[j]);
    }

    int k = s.size();
    string* t = s.top();
    s.pop();
    if(s.Empty())
    {
        cout<<"empty"<<endl;
    }
    s.clear();

    for(int i = 0 ; i < 10; ++i)
    {
        delete str[i] ;
    }
}

int main ()
{
    funcInt();
    funcString();
    getchar();
    return 0;
}

測試代碼沒有輸出，可以斷點看數據。

 

之後我又去看了一眼STL對棧的實現，它默認使用deque作為棧的底層實現。

template<class _Ty,
class _Container = deque<_Ty> >

class stack
{
// 棧實現
}

調用的時候直接std::stack<int> 即默認使用deque作為棧底層容器。

用戶也可以指定其他方式，比如std::stack<int, std::list<int> >, 這樣就使用了list作為棧的底層容器。

讓我感到awesome的是STL實現的精巧和靈活性，居然是可指定底層的一種實現方法，太精巧了。回頭再去看一下《STL源碼剖析》。

只羅列了代碼，沒太詳細的介紹原理，感興趣的可以直接去看《effective C++》和《STL源碼剖析》，以及STL的stack代碼。

 

引用請注明出處，http://www.cnblogs.com/chwen/p/4055474.html 非常感謝，隨時交流。


一個c語言標准 棧 的 模板 滿意再給分

#include<stdio.h>
#include<stdlib.h>
/*定義常量*/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define null 0
#define INFEASIBLE -1
#define OVERFLOW -2

/*定義棧初始分配空間及增量*/
#define initSize 100
#define increment 10
typedef int SElemType;
typedef int Status;

/*定義順序棧類型*/
typedef struct Stack{
SElemType *base;/*棧構造前和銷毀後棧底base為null*/
SElemType *top;/*棧頂指針*/
int stackSize;/*以元素為單位分配當前存儲空間*/
}Stack;

Status initStack(Stack *S){/*初始化一個空棧並將其返回*/
(*S).base=(SElemType *)malloc(initSize*sizeof(SElemType));
if(!(*S).base) exit(OVERFLOW);
(*S).top=(*S).base;
(*S).stackSize=initSize;
return OK;
}

Status destroyStack(Stack *S){/*銷毀棧*/
free((*S).base);
(*S).base=NULL;
(*S).top=NULL;
(*S).stackSize=0;
return OK;
}

Status clearStack(Stack *S){/*清空棧*/
(*S).top=(*S).base;
return OK;
}

Status stackEmpty(Stack S){/*判斷棧是否為空*/
return (S.top==S.base);
}

int stackLength(Stack S){ /*用return返回站棧的長度*/
return S.top-S.base;
}
/**************/
Status getTop(Stack S,SElemType *e){
/*用*e以返回棧頂元素至e */
if(S.top>S.base){
*e=*(S.top-1);
return OK;
}
else return ERROR;
}

Status push(Stack *S,SElemType e){
/*將e入棧以成為新棧頂,並將棧返回*/
if((*S).top-(*S).base>=(*S).stackSize){
/*棧滿,追加空間*/
(*S).base=(SElemType *)realloc((*S).base,((*S).stackSize+increment)*sizeof(SElemType));
if(!(*S).base) exi......余下全文>>
 

C語言中，定義了一個棧類型，想創建兩個棧對象，一個棧用來存放char型數據，另一個存放指針類型，怎實現

不得不說，我還沒有用過呢。你可以看看“c語言如何實現函數模板”，這個應該會對你有所幫助的。這個在c++中特別容易實現，但是c語言因為沒有函數模板，故而需要自己構造，一般都是宏的策略或者函數指針，不過我還沒有碰到過。
 

  1. 上一頁:
  2. 下一頁:
C++入門知識
C++ MFC打開文件的流程，mfc打開文件流程

C++ MFC打開文件的流程，mfc打開文件流程打開文件的
c++11 多線程 -- 基本使用

c++11 多線程 -- 基本使用 c++11 多線程

如何用一個for循環打印出一個二維數組

思路分析： 二維數組在內存中默認是按照行存儲的，比如一個二維
在C++中實現事件(委托)

 實現回調的三種方式(C風格的回調函數， S
Kosaraju算法詳解，kosaraju算法

Kosaraju算法詳解，kosaraju算法 

Linux C++的多線程編程，linux多線程編程

Linux C++的多線程編程，linux多線程編程1. 引
相關文章
閱讀排行榜
Static中C++類的數據共享 hdu5288(2015多校1)OO’s Sequence Lua中的元表與元方法 Given a sequence of numbers (or array).Find the maximum dist poj1562--Oil Deposits 黑馬程序員_JavaSE學習總結第13天_API常用對象3，_javase_api C++: How is the process of function calling in C++ C++ 無法將值寫入注冊表 HKEY_LOCAL_MACHINE\Sofeware\Microsoft\Windows\CurrentVersion\Run，以實現開機自啟動應用程序。，注冊表自啟動項 [LeetCode] Best Time to Buy and Sell Stock II uva 11916 - Emoogle Grid(大步小步算法) poj 1321 棋盤問題
熱門圖文
asp控制xml數據庫的6段代碼 JAVA基礎知識：JAVA變量類型之間的相互轉換 網站建設-個人小白，對jsp不太熟悉，做一個網站，遇到了點問題，在線等牛人解答 PHP 數組的鍵值 一步一步寫算法（之內存） PHP實現多文件上傳的方法 leetcode筆記：Word Break 用JQuery和PHP實現無刷新刪除數據庫數據
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved