概念：棧是一種特殊的線性表，僅能在線性表的一端（棧頂）進行操作。
棧的特性：后進先出（last in first out）
棧的基本操作：
創(chuàng)建棧（stack()）; 銷毀棧（~stack()）; 清空棧（clear()）
進棧（push()）; 出棧（pop()）;
獲取棧頂元素（top()）; 獲取棧的大?。╯ize()）
棧的繼承關系：
棧的聲明：(接口)
重慶分公司
重慶分公司
template < typename T >
class stack : public Object
{
Public:
virtual void push(const T& e) = 0;
virtule void pop() = 0;
virtual T top() const = 0;
virtual void clear() = 0;
virtual int size() const = 0;
};棧的順序?qū)崿F(xiàn),(棧是一種特殊的線性表)。
設計要點：
類模板，使用原生數(shù)組作為棧的存儲空間，使用模板參數(shù)決定棧的大容量
template < typename T, int N>
class StaticStack : public stack
{
protected:
T m_space[N];
int m_size;
int m_top;
public:
StaticStack()
int capacity() const
void push(const T& e)
void pop()
T top() const
int size() const
void clear()
}; 順序存儲結(jié)構棧最終實現(xiàn)：
template < typename T, int N >
class StaticStack : public Stack
{
protected:
T m_space[N];
int m_size;
int m_top;
public:
StaticStack() //O(1)
{
m_top = -1;
m_size = 0;
}
void push(const T& e) //O(1)
{
if(m_size < N)
{
m_space[m_top + 1] = e; //為了異常安全
m_size++;
m_top++;
}
else
{
THROW_EXCEPTION(InvaildParemeterException, "no space in current stack...");
}
}
void pop() //O(1)
{
if(m_size > 0)
{
m_size--;
m_top--;
}
else
{
THROW_EXCEPTION(InvaildParemeterException, "no element in current stack...");
}
}
T top() const //O(1)
{
if(m_size > 0)
{
return m_space[m_top];
}
else
{
THROW_EXCEPTION(InvaildParemeterException, "no element in current stack...");
}
}
int size() const //O(1)
{
return m_size;
}
int capacity() const //O(1)
{
return N;
}
void clear() //O(1)
{
m_size = 0;
m_top = -1;
}
}; 順序存儲結(jié)構棧的優(yōu)勢：所有操作的時間復雜度都為常量O(1)
順序棧的缺陷：當存儲元素為類類型時，StaticStack的對象在創(chuàng)建時，會多次調(diào)用元素類型的構造函數(shù)，影響效率。
為了解決這個問題，我們使用鏈式存儲結(jié)構來實現(xiàn)棧。
1.類模板，繼承自抽象父類Stack;
2.在內(nèi)部組合使用LinkList類，實現(xiàn)棧的鏈式存儲；
3.在當鏈表成員對象的頭部進行操作。
鏈式存儲結(jié)構棧的聲明：
template
class LinkStack: public Stack
{
protected:
LinkList m_list;
public:
void push(const T& e)
void pop()
T top() const
void clear()
int size() const
}; 鏈式存儲結(jié)構棧的最終實現(xiàn)：
template < typename T >
class LinkStack : public Stack
{
protected:
LinkList m_list;
public:
void push(const T& e) // 頭插法 O(1)
{
m_list.insert(0, e);
}
void pop() //O(1)
{
if(m_list.length() > 0)
{
m_list.remove(0);
}
else
{
THROW_EXCEPTION(InvalidOperationException, "no elememt in current linkstack...");
}
}
T top() const ///O(1)
{
if(m_list.length() > 0)
{
return m_list.get(0);
}
else
{
THROW_EXCEPTION(InvalidOperationException, "no elememt in current linkstack...");
}
}
int size() const //O(1)
{
return m_list.length();
}
void clear() //O(n)
{
m_list.clear();
}
}; 符號匹配問題：
在C語言中有一些成對匹配出現(xiàn)的符號，(), {}, [], <>, ‘’, “”，如何實現(xiàn)編譯器中的符號成對檢測？
算法思路：
1.從一個字符開始掃描，當遇見普通字符時忽略，當遇見左符號時入棧，當遇見有符號時彈出棧頂符號，進行匹配。
2.當所有字符掃描完成，且棧為空則成功；匹配失敗或最終棧非空則失敗。
算法實現(xiàn)：
#include
#include "Exception.h"
#include "LinkStack.h"
using namespace std;
using namespace DTLib;
bool is_left(char c)
{
return (c == '(') || (c == '{') || (c == '<') || (c == '[');
}
bool is_right(char c)
{
return (c == ')') || (c == '}') || (c == '>') || (c == ']');
}
bool is_quot(char c)
{
return (c == '\'') || (c == '\"');
}
bool is_mathch(char l, char r)
{
return ((l=='(') && (r==')')) ||
((l=='<') && (r=='>')) ||
((l=='{') && (r=='}')) ||
((l=='[') && (r==']')) ||
((l=='\'') && (r=='\'')) ||
((l=='\"') && (r=='\"'));
}
bool scan(const char* code)
{
LinkStack ls;
int i = 0;
bool ret = true;
code = ((code == NULL) ? "" : code);
while(ret && (code[i] != '\0'))
{
if(is_left(code[i]))
{
ls.push(code[i]);
}
else if(is_right(code[i]))
{
if((ls.size() > 0) && is_mathch(ls.top(), code[i]))
{
ls.pop();
}
else
{
ret = false;
}
}
else if(is_quot(code[i]))
{
if((ls.size() == 0) || !is_mathch(ls.top(), code[i]))
{
ls.push(code[i]);
}
else if(is_mathch(ls.top(), code[i]))
{
ls.pop();
}
}
i++;
}
return (ret && (ls.size() == 0));
}
int main()
{
cout << scan("[\"\"]")<< endl;
cout << scan("else if(is_quot(code[i])){if((stack.size() == 0) || !is_match(stack.top(),code[i])){stack.push(code[i]);}else if(is_match(stack.top(),code[i])){stack.pop();}}")<< endl;
return 0;
} 總結(jié)：
1.鏈式棧的實現(xiàn)組合使用了單鏈表對象，當在單鏈表的頭部進行操作能夠?qū)崿F(xiàn)高效的入棧和出棧操作；
2.棧“先入后出”的特性適用于檢測成對出現(xiàn)的符號，非常適合就近匹配的場合。
另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。
