数据结构复习篇知识
数据结构复习篇知识
二、栈
栈是一种“发育不良”的线性表，它具有与线性表相同的存储结构（基于数组的或基于链于的），但栈的“缺陷”－－－不能像线性表那样具有插入、删除操作－－－反而给了它独有的特色。在后面将会发现，递归，可以用栈来实现。
在时间复杂度上，基于数组的栈AStack和链式栈LStack，在push()、pop()操作上，都是一个时间常数1。在我的测试中，10万次push()和10万次pop()后，基于数组的栈只比链式栈快一秒。但要注意AStack需要预先指定栈元素的最大个数，而LStack是动态分配的，元素个数在理论上不受限。
经常思考，我发现昨天在线性表那篇文章中，有一个设计错误，就是不应该把结点类Node与List类放在一个文件中，这是违反模块化思想的。当我今天的栈中要用到结点时，应该可以很轻松的通过头文件的方式把结点类引到我的代码中。以下是一个最简单的结点类界面（事实上可以采用可用空间表freelist的方式来定义结点类）：
/*
定义常用于链表中的各种结点界面
文件名：NodeInterface.h
*/
#ifndefNODEINTERFACE_H
#defineNODEINTERFACE_H
template<classT>classNode//单端结点，只含有一个指针
{
public:
Telement;
Node*next;
public:
Node(constT&eVal,Node*nVal=NULL)
{
element=eVal;
next=nVal;
}
Node(Node*nVal=NULL)
{
element=0;
next=nVal;
}
};
#endif
定义常用于链表中的各种结点界面
文件名：NodeInterface.h
*/
#ifndefNODEINTERFACE_H
#defineNODEINTERFACE_H
template<classT>classNode//单端结点，只含有一个指针
{
public:
Telement;
Node*next;
public:
Node(constT&eVal,Node*nVal=NULL)
{
element=eVal;
next=nVal;
}
Node(Node*nVal=NULL)
{
element=0;
next=nVal;
}
};
#endif
以下是栈的界面及两种实现的代码：
/*
文件名:StackInterface.h
*/
#ifndefSTACKINTERFACE_H
#defineSTACKINTERFACE_H
#include"NodeInterface.h"
//定义栈的界面
template<classT>classStack
{
public:
virtualboolpush(constT&)=0;//入栈
virtualboolpop(T&)=0;//出栈
virtualbooltopValue(T&)=0;//栈顶元素值
};
/////////////////////////////////////
//基于数组的栈Array_basedSatck
/////////////////////////////////////
template<classT>classAStack:publicStack<T>
{
private:
intmaxSize;//栈最多能容纳的元素个数
inttop;//指示栈中元素的实际个数,由于数组从0开始,(top-1)才指示了栈顶元素的下标
T*listArray;//arrayholdingstackelements
public:
AStack(intsize=100)
{
maxSize=size;
top=0;
listArray=newT[maxSize];
}
~AStack()
{
delete[]listArray;
}
boolpush(constT&);
boolpop(T&);
booltopValue(T&);
intlength()const
{
returntop;
}
};
template<classT>boolAStack<T>::push(constT&element)
{
if(top==maxSize)//stackisfull.
{
returnfalse;
}
listArray[top]=element;
++top;
returntrue;
}
template<classT>boolAStack<T>::pop(T&ref_elem)
{
if(top==0)//noelementinstack
{
returnfalse;
}
ref_elem=listArray[--top];
returntrue;
}
template<classT>boolAStack<T>::topValue(T&ref_elem)
{
if(top==0)//noelementinstack
{
returnfalse;
}
ref_elem=listArray[top-1];
returntrue;
}
///////////////////////////////////
//链式栈LinkedStack
///////////////////////////////////
template<classT>classLStack:publicStack<T>
{
private:
intlistSize;//thenumberofelements,andthatisthenumberofnodes
Node<T>*top;//与AStack栈不同,这里,top指向栈顶元素
public:
LStack()//不必限定元素的最大值
{
listSize=0;
top=NULL;
}
~LStack()
{
}
boolpush(constT&);
boolpop(T&);
booltopValue(T&);
voidclear();
intlength()const
{
returnlistSize;
}
};
template<classT>boolLStack<T>::push(constT&element)
{
Node<T>*tmp=newNode<T>(element,top);
top=tmp;
++listSize;
returntrue;
}
template<classT>boolLStack<T>::pop(T&ref_elem)
{
if(top==NULL)
{
returnfalse;//栈中没有元素
}
Node<T>*tmp=top;
top=top->next;
ref_elem=tmp->element;
deletetmp;
--listSize;
returntrue;
}
template<classT>boolLStack<T>::topValue(T&ref_elem)
{
if(top==NULL)
{
returnfalse;//noneelementinstack
}
ref_elem=top->element;
returntrue;
}
template<classT>voidLStack<T>::clear()
{
Node<T>*tmp;
while(top!=NULL)
{
tmp=top;
top=top->next;
deletetmp;
}
}
#endif
文件名:StackInterface.h
*/
#ifndefSTACKINTERFACE_H
#defineSTACKINTERFACE_H
#include"NodeInterface.h"
//定义栈的界面
template<classT>classStack
{
public:
virtualboolpush(constT&)=0;//入栈
virtualboolpop(T&)=0;//出栈
virtualbooltopValue(T&)=0;//栈顶元素值
};
/////////////////////////////////////
//基于数组的栈Array_basedSatck
/////////////////////////////////////
template<classT>classAStack:publicStack<T>
{
private:
intmaxSize;//栈最多能容纳的元素个数
inttop;//指示栈中元素的实际个数,由于数组从0开始,(top-1)才指示了栈顶元素的下标
T*listArray;//arrayholdingstackelements
public:
AStack(intsize=100)
{
maxSize=size;
top=0;
listArray=newT[maxSize];
}
~AStack()
{
delete[]listArray;
}
boolpush(constT&);
boolpop(T&);
booltopValue(T&);
intlength()const
{
returntop;
}
};
template<classT>boolAStack<T>::push(constT&element)
{
if(top==maxSize)//stackisfull.
{
returnfalse;
}
listArray[top]=element;
++top;
returntrue;
}
template<classT>boolAStack<T>::pop(T&ref_elem)
{
if(top==0)//noelementinstack
{
returnfalse;
}
ref_elem=listArray[--top];
returntrue;
}
template<classT>boolAStack<T>::topValue(T&ref_elem)
{
if(top==0)//noelementinstack
{
returnfalse;
}
ref_elem=listArray[top-1];
returntrue;
}
///////////////////////////////////
//链式栈LinkedStack
///////////////////////////////////
template<classT>classLStack:publicStack<T>
{
private:
intlistSize;//thenumberofelements,andthatisthenumberofnodes
Node<T>*top;//与AStack栈不同,这里,top指向栈顶元素
public:
LStack()//不必限定元素的最大值
{
listSize=0;
top=NULL;
}
~LStack()
{
}
boolpush(constT&);
boolpop(T&);
booltopValue(T&);
voidclear();
intlength()const
{
returnlistSize;
}
};
template<classT>boolLStack<T>::push(constT&element)
{
Node<T>*tmp=newNode<T>(element,top);
top=tmp;
++listSize;
returntrue;
}
template<classT>boolLStack<T>::pop(T&ref_elem)
{
if(top==NULL)
{
returnfalse;//栈中没有元素
}
Node<T>*tmp=top;
top=top->next;
ref_elem=tmp->element;
deletetmp;
--listSize;
returntrue;
}
template<classT>boolLStack<T>::topValue(T&ref_elem)
{
if(top==NULL)
{
returnfalse;//noneelementinstack
}
ref_elem=top->element;
returntrue;
}
template<classT>voidLStack<T>::clear()
{
Node<T>*tmp;
while(top!=NULL)
{
tmp=top;
top=top->next;
deletetmp;
}
}
#endif
晚一些时候，我把用栈实现递归的方法，写到这里来。