首页 > 代码库 > 栈的实现:链式栈
栈的实现:链式栈
栈的链式存储,即链式栈。它相比于顺序栈,
优点:
- 插入、删除灵活 (不必移动节点,只要改变节点中的指针指向即可)。
- 逻辑上相邻的节点物理上不必相邻。
缺点:
- 比顺序存储结构的存储密度小 (每个节点都由值域和链域组成,使用指针来表现前后节点的逻辑关系)。
- 查找节点时链式存储要比顺序存储慢。
这些优点、缺点体现了顺序存储和链式存储的相区别之处。
看图就很形象了:
下面来看一个链式栈的实现:
类定义和类实现
#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; }
运行:
完整代码下载:栈的实现:链式栈
小结:
如果清楚了链表的操作,实现链式栈是很简单的。单向链表的各种操作是基础。其它的线性表上的操作无非是单向链表操作的子集。当然,实际问题适合什么样的存储结构,就设计相应的物理结构。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。