首页 > 代码库 > 栈的实现：链式栈

栈的实现：链式栈

2024-07-07 11:17:26   232人阅读

栈的链式存储，即链式栈。它相比于顺序栈，

优点：

  1. 插入、删除灵活 (不必移动节点，只要改变节点中的指针指向即可)。
  2. 逻辑上相邻的节点物理上不必相邻。
缺点：
  1. 比顺序存储结构的存储密度小 (每个节点都由值域和链域组成，使用指针来表现前后节点的逻辑关系)。
  2. 查找节点时链式存储要比顺序存储慢。
这些优点、缺点体现了顺序存储和链式存储的相区别之处。
看图就很形象了：

下面来看一个链式栈的实现：
类定义和类实现
#include<iostream>
using namespace std; 
typedef int ElemType;  
typedef struct stacknode   //栈节点类型   
{  
    ElemType data;   //值域   
    struct stacknode *next;  //链域   
}StackNode;  
class LinkStack   //链式堆栈   
{  
    private:  
    StackNode *stop;  //栈顶指针   
    int num;    //栈中节点个数   
    public:  
    LinkStack();   //默认构造函数   
    LinkStack(const LinkStack &stack);   //拷贝构造函数  
    ~LinkStack();  //析构函数   
    int size();   //获取栈节点个数   
    bool empty();   //判断栈是否为空   
    StackNode* top();   //获取栈顶元素  
    void pop();    //出栈  
    void push(ElemType data);   //入栈   
    void clear();    //栈清空   
    void stackTraverse(void(*)(StackNode *));   //遍历栈   
};  
//类实现  
LinkStack::LinkStack()   //构建空栈   
{  
     stop=NULL;  
     num=0;   
}   
LinkStack::LinkStack(const LinkStack &stack)   //拷贝构造函数  
{  
    if(stop)   //如果不为空，应该清除节点，释放内存   
    clear();  
    if(stack.stop)  
    {  
        StackNode *pnode,*p=stack.stop;  
        stop=pnode=new StackNode;  
        pnode->data=http://www.mamicode.com/p->data;  >
主函数
int main()
{
	cout<<"栈的实现：链式栈"<<endl;
	LinkStack stack;
	int data;
	cout<<"入栈，输入0结束！"<<endl;
	while(cin>>data && data)
		stack.push(data);
	printf("遍历栈\n");
	stack.stackTraverse(visit);   
	StackNode *pnode=stack.top();
	printf("获取栈顶 %-4d\n",pnode->data);
	stack.pop();
	printf("出栈，遍历栈\n");
	stack.stackTraverse(visit);
	//使用拷贝构造函数 
	LinkStack s;
	s=stack;
	printf("测试拷贝构造函数\n");
	printf("遍历栈\n");
	s.stackTraverse(visit);
	printf("栈中元素个数是 %d\n",s.size());
	stack.clear();
	printf("栈清空后，栈是否为空？\n");
	stack.empty()?printf("Yes!\n"):printf("No!\n");
	system("pause");
	return 0;
}

运行：


完整代码下载：栈的实现：链式栈
小结：
如果清楚了链表的操作，实现链式栈是很简单的。单向链表的各种操作是基础。其它的线性表上的操作无非是单向链表操作的子集。当然，实际问题适合什么样的存储结构，就设计相应的物理结构。


联系
我们