线性栈与链栈
用C++编程语言实现 线性栈与链栈 的代码撰写
一、顺序栈
#pragma once
#include <iostream>
using namespace std;
顺序栈类(class LinearStack)
函数声明
//顺序栈
template<class T>
class LinearStack
{
public:
LinearStack(int LSMaxSize); //创建空栈
~LinearStack(); //删除栈
bool IsEmpty(); //判断栈是否为空
bool IsFull(); //判断栈是否为满
bool Push(const T& x); //入栈，在栈顶插入元素x
bool Top(T& x); //求栈顶元素的值放入x中
bool Pop(T& x); //出栈，从栈顶删除一个元素，并将该元素的值放入x中
void OutPut(ostream& out)const; //输出顺序栈
private:
int top; //用来表示栈顶
int MaxSize; //栈中最大元素个数
T* element; //一维动态数组
};
创建空栈(构造函数)
//创建空栈
template<class T>
LinearStack<T>::LinearStack(int LSMaxSize)
{
MaxSize = LSMaxSize;
element = new T[MaxSize];
top = -1;
}
删除栈(析构函数)
//删除栈
template<class T>
LinearStack<T>::~LinearStack()
{
delete[] element;
}
判断栈是否为空
//判断栈是否为空
template<class T>
bool LinearStack<T>::IsEmpty()
{
return top == -1;
}
判断栈是否为满
//判断栈是否为满
template<class T>
bool LinearStack<T>::IsFull()
{
return (top+1) == MaxSize;
}
入栈操作
//入栈，在栈尾部插入元素x
template<class T>
bool LinearStack<T>::Push(const T& x)
{
if (IsFull())
return false;
else
{
top++;
element[top] = x;
return true;
}
}
求栈顶元素
//求栈顶元素
template<class T>
bool LinearStack<T>::Top(T& x)
{
if (IsEmpty())
return false;
x = element[top];
return true;
}
出栈操作
//出栈，从栈顶删除一个元素，并将该元素的值放入x中
template<class T>
bool LinearStack<T>::Pop(T& x)
{
if(IsEmpty())
return false;
x = element[top];
top--;
return true;
}
输出栈及重载运算符<<
//输出栈
template<class T>
void LinearStack<T>::OutPut(ostream& out)const
{
for (int i = 0; i <= top; i++)
{
out <<element[i] << endl;
}
}
//重载运算符<<
template<class T>
ostream& operator<<(ostream& out, const LinearStack<T>& x)
{
x.OutPut(out);
return out;
}
主程序(main)
LinearStack<int> s;
s.Insert(1);
s.Insert(2);
s.Insert(4);
cout << s ;
二、链接栈
单结点类(class Node)
template<class T>
class LinkNode
{
template<class T>
friend class LinkStack;
public:
LinkNode()
{
next = nullptr;
}
private:
T data; //结点元素
LinkNode<T>* next; //指向下一个结点的指针
};
链接栈类（class LinkStack)
函数声明
//链接栈
template<class T>
class LinkStack
{
public:
LinkStack(); //创建空栈
~LinkStack(); //删除栈
bool IsEmpty()const; //判断栈是否为空
bool Push(const T& x); //入栈，在栈顶插入元素x
bool Top(T& x); //求栈顶元素的值放入x中
bool Pop(T& x); //出栈，从栈顶删除一个元素，并将该元素的值放入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;
}
入栈操作
//入栈，在栈尾部插入元素x
template<class T>
bool LinkStack<T>::Push(const T& x)
{
LinkNode<T>* p = new LinkNode<T>;
if (p == NULL)
return false;
p->data = x; //为元素赋值
p->next = top;
top = p;
size++;
return true;
}
求栈顶元素
//求栈顶元素
template<class T>
bool LinkStack<T>::Top(T& x)
{
if (IsEmpty())
return false;
x = top->data;
return true;
}
出栈操作
//出栈，从栈顶删除一个元素，并将该元素的值放入x中
template<class T>
bool LinearStack<T>::Pop(T& x)
{
if (IsEmpty())
return false;
LinkNode<T>* p = top;
x = p->data;
top = top->next;
delete p;
return true;
}
输出栈及重载运算符<<
//输出栈
template<class T>
void LinearStack<T>::OutPut(ostream& out)const
{
LinkNode<T>* p = top;
while (p != NULL)
{
out << p->data << endl;
p = p->next;
}
}
//重载运算符<<
template<class T>
ostream& operator<<(ostream& out, const LinearStack<T>& x)
{
x.OutPut(out);
return out;
}
主程序(main)
LinkStack<int> s;
s.Insert(1);
s.Insert(2);
s.Insert(4);
cout << s;
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 351134995@qq.com
