基于C++的数据结构-5-链式栈

基于C++的数据结构-5-链式栈,第1张

文章目录
      • 链式栈基础知识
      • 基本 *** 作
      • 代码示例
      • CPP实现及应用

链式栈基础知识

把栈组织成一个单链表,即采用链接结构来表示栈,这样的class="superseo">数据结构就叫做链接栈。



栈的链接结构一般通过单向链表来实现。


在单向链表中,每一个节点表示栈中的元素。


由于栈是在链表头部进行插入删除,所以链式栈不需要设置头结点,栈顶指针通常用top表示,这是它的唯一指针。



由于链接栈具有动态分配元素结点的特点,所以在内存足够大的情况下,可以认为链接栈中最大元素个数没有限制,所以在单向链表中不用**isFull()**去判断是否满溢出。


基本 *** 作

在单向链表中,使用较多的是进栈和出栈。


进栈就是向链接栈的栈顶插入一个元素结点,先将待进栈结点的指针域指向原来的栈顶节点,然后将栈顶节点指针top指向新结点,是进栈元素结点成为新的栈顶节点;
出栈就是从链接栈的栈顶删除一个元素结点,先将栈顶元素取出放到x中,然后使栈顶指针top指向原栈顶节点的后继结点,然后从物理上删除该结点即可。



top为空时,代表栈空,否则就代表还有元素处于栈中。


代码示例

进栈 LinkNode是节点类,T表示数据类型

bool push(const T& x){
	LinkNode<T> *p=new LinkNode<T>;
    if(p==NULL){
    	return false;
    }
    else{
    	p->data=x;
        p->next=top;
        top=p;
        size++;
        return true;
    }
}

出栈 LinkNode是节点类,T表示数据类型

bool pop(T& x){
	LinkNode<T> *p;
    if(Isempty()){
    	return false;
    }
    else{
    	x=top->data;
        p=top;
        top=top->next;
        delete p;
        size--;
        return true;
    }
}
CPP实现及应用
#include
using namespace std;

template<class T>
class LinkStack;

template<class T>
class LinkNode{
	friend class LinkStack<T>;
	public:
		LinkNode(){
			next=NULL;
		}
	private:
		T data;
		LinkNode<T> *next;
};

template<class T>
class LinkStack{
	public:
		LinkStack();
		~LinkStack();
		bool IsEmpty() const;
		bool Push(const T& x);
		bool Top(T& x);
		bool Pop(T& x);
		void Output(ostream& out) const;
	private:
		LinkNode<T> *top;
		int size;
};

template<class T>
LinkStack<T>::LinkStack(){
	top=NULL;
	size=0;
}
template<class T>
LinkStack<T>::~LinkStack(){
	T x;
	while(top!=NULL){
		Pop(x);
	}
}
template<class T>
bool LinkStack<T>::IsEmpty() const{
	return top==NULL;
}
template<class T>
bool LinkStack<T>::Push(const T& x){
	LinkNode<T> *p=new LinkNode<T>;
	if(p==NULL){
		return false;
	}
	else{
		p->data=x;
		p->next=top;
		top=p;
		size++;
		return true;
	}
}
template<class T>
bool LinkStack<T>::Top(T& x){
	if(IsEmpty()){
		return false;
	}
	else{
		x=top->data;
		return true;
	}
}
template<class T>
bool LinkStack<T>::Pop(T& x){
	LinkNode<T> *p;
	if(IsEmpty()){
		return false;
	}
	else{
		x=top->data;
		p=top;
		top=top->next;
		delete p;
		size--;
		return true;
	}
}
template<class T>
void LinkStack<T>::Output(ostream& out) const{
	LinkNode<T> *p;
	p=top;
	for(int i=0;i<size;i++){
		out<<p->data<<endl;
		p=p->next;
	}
}
template<class T>
ostream& operator<<(ostream& out,LinkStack<T>& x){
	x.Output(out);
	return out;
}

void conversion(int,int);

int main(){
	cout<<"---------------将100转化为2进制表示-----------------"<<endl;
	conversion(100,2);
	cout<<endl;
	return 0;
}
void conversion(int n,int base){
	int x,y;
	y=n;
	LinkStack<int> s;
	while(y){
		s.Push(y%base);
		y=y/base;
	}
	cout<<"十进制数100转换为二进制数结果为:"<<endl;
	while(!s.IsEmpty()){
		s.Pop(x);
		cout<<x;
	}
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/634438.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-16
下一篇 2022-04-16

发表评论

登录后才能评论

评论列表(0条)

保存