栈 | 栈的实现
程序员文章站
2024-03-01 13:17:10
...
描述
栈是一种线性存储结构,栈中数据是按照“先进后出”方式进出栈,向栈中添加/删除数据时,只能从栈顶进行操作。
顺序栈(C++)
#include<iostream>
using namespace std;
template<class T>
class ArrayStack{
public:
ArrayStack();
ArrayStack(int size);
~ArrayStack();
T top();//返回栈顶元素
int size();//返回栈中元素数量
bool empty();//判断栈是否为空
bool pop();//删除栈顶元素
bool push(T e);//入栈
private:
T *arr;//实现栈的数组
int count;//记录栈中元素的数量
int capacity;//栈的容量
};
//构造函数
template<class T>
ArrayStack<T>::ArrayStack(int size)
{
count=0;
capacity=size;
arr=new T[capacity];
if(!arr)
{
cout<<"arr malloc error!"<<endl;
}
}
template<class T>
ArrayStack<T>::ArrayStack()
{
new (this)ArrayStack(30);
}
//析构函数
template<class T>
ArrayStack<T>::~ArrayStack()
{
if(arr)
{
delete[] arr;
arr=NULL;
}
}
//入栈
template<class T>
bool ArrayStack<T>::push(T e)
{
//栈满,入栈失败,返回false
if(count>=capacity)
return false;
arr[++count]=e;
return true;
}
//返回栈顶元素
template<class T>
T ArrayStack<T>::top()
{
return arr[count];
}
//删除栈顶元素
template<class T>
bool ArrayStack<T>::pop()
{
if(count<=0)
return false;
count--;
return true;
}
//返回栈的大小
template<class T>
int ArrayStack<T>::size()
{
return count;
}
//判断栈是否为空
template<class T>
bool ArrayStack<T>::empty()
{
return count==0;
}
int main()
{
ArrayStack<int> *stack=new ArrayStack<int>;
int a[]={1,2,3,4};
int len=sizeof(a)/sizeof(a[0]);
cout<<"入栈:";
for(int i=0;i<len;i++)
{
cout<<a[i]<<" ";
stack->push(a[i]);
}
cout<<"\n栈中元素个数为"<<stack->size()<<endl;
//获取栈顶元素
int temp=stack->top();
stack->pop();
cout<<"删除栈顶元素"<<temp<<endl;
cout<<"栈中元素个数为"<<stack->size()<<endl;
while(!stack->empty())
{
cout<<"删除元素"<<stack->top()<<endl;
stack->pop();
}
return 0;
}