链栈(C++)

阅读原文时间：2023年07月11日阅读：1

链栈，字面意思，就是用链表来实现一个栈的数据结构。

那么，只需将单链表的头节点当作栈顶，尾节点当作栈底。入栈只需要头插，出栈只需头删即可。所以只需要吧单链表稍微阉割一下就可以得到链式栈了。代码如下

//header.h
#pragma once
#include
using namespace std;
template
struct LinkNode //节点类定义
{
T data; //数据域
LinkNode *next; //链指针域
LinkNode(LinkNode *ptr = NULL){this->next = ptr;} //初始化指针域的构造函数
LinkNode(const T& item, LinkNode *ptr = NULL)//初始化数据成员和指针成员和指针的构造函数
{
this->data = item;
this->next = ptr;
}
};

template
class ListStack //用头结点的数据域表示链表元素数量
{
protected:
LinkNode *first;
public:
ListStack(){first = new LinkNode;first->data = 0;}//无参数构造
ListStack(const T& x)
{
this->first = new LinkNode;
this->input(x);
}//含有参数的构造函数
ListStack(ListStack& L);//拷贝构造
~ListStack(){makeEmpty();}//析构函数
void makeEmpty();//将链表置空的函数
int Length()const{return this->first->data;}//计算链表长度的函数
LinkNode* getHead()const{return this->first;}//返回附加头结点地址
LinkNode* getRear()const;//返回尾部指针
void input(T head);//头插
void output();//将链表打印出来
bool IsEmpty()const{return !this->first->data;}
bool Remove(int i, T& x);//删除第i个元素，将第i个元素的data赋值给x
ListStack& operator=(ListStack& L);//符号重载，赋值
bool del(T& x);

};
template
bool ListStack::del(T& x)
{
return this->Remove(1, x);
}
template
ListStack& ListStack::operator=(ListStack& L)
{
if(!L.IsEmpty())
{
LinkNode *srcptr = L.first, *desptr = this->first;
while(srcptr->next != NULL)
{
desptr->data = srcptr->data;
desptr->next = new LinkNode;
srcptr = srcptr->next;
desptr = desptr->next;
}
desptr->data = srcptr->data;
}
}
template
bool ListStack::Remove(int i, T& x)
{
if(i>0 && i<=this->first->data)
{
LinkNode *tmp = this->first, *p;
if(i!=1)
{
int j = 0;
while(j!=i-1)
{
tmp = tmp->next;
++j;
}
p = tmp->next;
tmp->next = p->next;
x = p->data;
delete p;
}
else
{
p = tmp->next;
x = p->data;
tmp->next = p->next;
delete p;
}
--this->first->data;
return true;
}
return false;
}

template
void ListStack::input(T head)
{
LinkNode *tmp = new LinkNode;
if(tmp == NULL)
{
cerr<<"内存分配错误！\n"<<endl;
exit(-1);
}

if(this->first->next != NULL)  
{  
    tmp->next = this->first->next;  
    this->first->next = tmp;  
}  
else  
{  
    this->first->next = tmp;  
    tmp->next = NULL;  
}  
tmp->data = head;  
++this->first->data;

}
template
void ListStack::output()
{
LinkNode *p = this->first->next;
while(p!=NULL)
{
cout<data<<" | "; p = p->next;
}
cout<<"over"<
ListStack::ListStack(ListStack& L)
{
T value;
LinkNode *srcptr = L.getHead();
LinkNode *desptr = this->first = new LinkNode;
this->first->data = srcptr->data;
while(srcptr->next != NULL)
{
value = srcptr->next->data;
desptr->next = new LinkNode(value);
desptr = desptr->next;
srcptr = srcptr->next;
}
desptr->next = NULL;
}
template
void ListStack::makeEmpty()
{
LinkNode *p, *q = this->first->next;
this->first->data = 0;
while(q != NULL)
{
p = q;
q = q->next;
delete p;
}
}
template
LinkNode* ListStack::getRear()const
{
LinkNode *p = this->first;
while(p->next!=NULL)
p = p->next;
return p;

}

#include"header.h"

int main()
{
int x = 0;
ListStack LS;
for(int i=0; i<=7; ++i)
LS.input(i);
LS.output();
for(int i=0; i<=2; ++i)
{
LS.del(x);
cout<<x<<" ";
}
cout<<endl;
LS.output();