欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

栈 | 栈的实现

程序员文章站 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;
}
相关标签: 数据结构