数据结构(06)_栈-创新互联
1.栈的设计和实现
1.1.栈的概念
概念:栈是一种特殊的线性表,仅能在线性表的一端(栈顶)进行操作。
栈的特性:后进先出(last in first out)
栈的基本操作:
创建栈(stack()); 销毁栈(~stack()); 清空栈(clear())
进栈(push()); 出栈(pop());
获取栈顶元素(top()); 获取栈的大小(size())
1.2.栈的实现
栈的继承关系:
栈的声明:(接口)
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;
};
1.3.StaticStack
栈的顺序实现,(栈是一种特殊的线性表)。
设计要点:
类模板,使用原生数组作为栈的存储空间,使用模板参数决定栈的大容量
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()
};
顺序存储结构栈最终实现:
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;
}
};
顺序存储结构栈的优势:所有操作的时间复杂度都为常量O(1)
2.LinkStack
顺序栈的缺陷:当存储元素为类类型时,StaticStack的对象在创建时,会多次调用元素类型的构造函数,影响效率。
为了解决这个问题,我们使用链式存储结构来实现栈。
2.1.设计要点
1.类模板,继承自抽象父类Stack;
2.在内部组合使用LinkList类,实现栈的链式存储;
3.在当链表成员对象的头部进行操作。
链式存储结构栈的声明:
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
};
链式存储结构栈的最终实现:
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();
}
};
2.2.栈的应用
符号匹配问题:
在C语言中有一些成对匹配出现的符号,(), {}, [], <>, ‘’, “”,如何实现编译器中的符号成对检测?
算法思路:
1.从一个字符开始扫描,当遇见普通字符时忽略,当遇见左符号时入栈,当遇见有符号时弹出栈顶符号,进行匹配。
2.当所有字符扫描完成,且栈为空则成功;匹配失败或最终栈非空则失败。
算法实现:
#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;
}
总结:
1.链式栈的实现组合使用了单链表对象,当在单链表的头部进行操作能够实现高效的入栈和出栈操作;
2.栈“先入后出”的特性适用于检测成对出现的符号,非常适合就近匹配的场合。
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
本文题目:数据结构(06)_栈-创新互联
转载来于:http://scjbc.cn/article/dheohi.html