Posted on 2012-08-01 16:51
C小加 阅读(7579)
评论(1) 编辑 收藏 引用 所属分类:
数据结构和算法
基本数据结构:栈(stack)
作者:C小加 更新时间:2012-8-1
栈(stack)是限制插入和删除只能在一个位置上进行的线性表,该位置在表的末端,叫做栈顶。添加元素只能在尾节点后添加,删除元素只能删除尾节点,查看节点也只能查看尾节点。添加、删除、查看依次为入栈(push)、出栈(pop)、栈顶节点(top)。形象的说,栈是一个先进后出(LIFO)表,先进去的节点要等到后边进去的节点出来才能出来。
![](/images/cppblog_com/cxiaojia/stack_1.png)
如图1,是一个栈的形象图,top指针指向的是栈顶节点,所以我们可以通过top访问到2节点,但是0和1节点由于先于2进入这个表,所以是不可见的。如果把0节点当做头节点,2节点当做尾节点,那么栈限制了访问权限,只可以访问尾节点。
![](/images/cppblog_com/cxiaojia/stack_2.png)
如图2,当添加一个节点3的时候,只能在栈顶节点,也就是尾节点后添加,这样3节点变成了栈顶,2节点变成了不可见节点,访问的时候只能访问到3节点。入栈时限制了插入地址,只能在栈顶添加节点。
![](/images/cppblog_com/cxiaojia/stack_3.png)
当我们执行出栈的命令时,图2的栈顶元素是3节点,删除的时候只能允许删除栈顶的元素,这样子3节点被删除,top指向删除后的栈顶2节点,如图3所示。
栈有两种是实现结构,一种是顺序存储结构,也就是利用数组实现,一种是链式存储结构,可以用单链表实现。数组实现栈很简单,用一个下标标记top来表示栈顶,top==-1时,栈空,top==0时,表示栈里只有一个元素,通过访问top为下标的数组元素即可。出栈top自减,入栈top自加就OK了。
单链表实现栈要比单链表的实现简单点。我们通过在表的尾端插入来实现push,通过删除尾节点来实现pop,获取尾节点的元素来表示top。我修改了链表那一章的单链表代码,把头节点当做栈顶节点,实现了一个简单的栈模板,仅供学习所用。代码会不定时更新。代码下载
代码如下:
template<class T>
class stackNode
{
public:
stackNode():next(NULL){}
T data;//值
stackNode* next;//指向下一个节点的指针
};
template<class T>
class mystack
{
private:
unsigned int stacklength;
stackNode<T>* node;//临时节点
stackNode<T>* headnode;//尾结点
public:
mystack();//初始化
unsigned int length();//栈元素的个数
void push(T x);//入栈
bool isEmpty();//判断栈是否为空
void pop();//出栈
T top();//获得栈顶元素
void clear();//清空栈
};
template<class T>
mystack<T>::mystack()
{
node=NULL;
headnode=NULL;
stacklength=0;
}
template<class T>
inline unsigned int mystack<T>::length(){return stacklength;}
template<class T>
void mystack<T>::push(T x)
{
node=new stackNode<T>();
node->data=x;
node->next=headnode;//把node变成头节点
headnode=node;
++stacklength;
}
template<class T>
bool mystack<T>::isEmpty()
{
return stacklength==0;
}
template<class T>
void mystack<T>::pop()
{
if(isEmpty()) return;
node=headnode;
headnode=headnode->next;//头节点变成它的下一个节点
delete(node);//删除头节点
--stacklength;
}
template<class T>
T mystack<T>::top()
{
if(!isEmpty())
return headnode->data;
}
template<class T>
void mystack<T>::clear()
{
while(headnode!=NULL)
{
node=headnode;
headnode=headnode->next;
delete(node);
}
node=NULL;
headnode=NULL;
stacklength=0;
}
很清楚,除了clear函数外,所有的方法的时间复杂度都是O(1)。这种实现方式的缺点在于对new和delete的调用的开销是昂贵的,所以采用数组的方式实现会更好一点。
栈的应用
使用栈的时候一般不用自己重新去写,因为STL给我们实现了一个很安全的栈,可以放心去使用。也可以用数组模拟一个,很简单。
编译器调用函数就用了栈结构,当第一个函数还没执行完毕,调用第二个函数的时候,编译器就会把第一个函数压栈,第二个函数调用完毕的时候,就会取栈顶函数,也就是第一个函数继续执行。
平衡符号 http://acm.nyist.net/JudgeOnline/problem.php?pid=2
中缀转后缀 http://acm.nyist.net/JudgeOnline/problem.php?pid=467
后缀试求值 http://acm.nyist.net/JudgeOnline/problem.php?pid=35
poj 3250 http://acm.pku.edu.cn/JudgeOnline/problem?id=3250
poj 1363 http://acm.pku.edu.cn/JudgeOnline/problem?id=1363
poj 1208 http://acm.pku.edu.cn/JudgeOnline/problem?id=1208
poj 1686 http://acm.pku.edu.cn/JudgeOnline/problem?id=1686
poj 3250 http://acm.pku.edu.cn/JudgeOnline/problem?id=2045
hdu 1022 http://acm.hdu.edu.cn/showproblem.php?pid=1022