栈在实际编程中经常会用到，本文利用数组和链表分别实现了栈的操作。
1.数组方式实现如下：
#include<iostream>
using namespace std;
template <class T>
class arraystack{
public:
arraystack();
~arraystack();
bool isempty();
void push(const T& data);
void pop();
T& gettop();
private:
T *stacknodes;
int top;
int capacity;
};
template<class T>
arraystack<T>::arraystack()
{
capacity=3;
stacknodes=new T[3];
top=-1;
cout<<"the stack is constructed!"<<endl;
cout<<"the capacity is:"<<capacity<<endl;
}
template <class T>
arraystack<T>::~arraystack()
{
delete []stacknodes;
capacity=0;
top=-1;
cout<<"the stack is destructed!"<<endl;
}
template <class T>
bool arraystack<T>::isempty()
{
if(top==-1)
return true;
else
return false;
}
template <class T>
void arraystack<T>::push(const T& data)
{
if(top+1==capacity)
{
capacity=2*capacity;
T *p=new T[capacity];
for(int i=0;i<=top;++i)
p[i]=stacknodes[i];
T *q=stacknodes;
stacknodes=p;
delete []q;
cout<<"the capacity is:"<<capacity<<endl;
}
stacknodes[++top]=data;
cout<<"push in:"<<stacknodes[top]<<endl;
}
template <class T>
void arraystack<T>::pop()
{
if(!isempty())
top--;
}
template <class T>
T& arraystack<T>::gettop()
{
if(!isempty())
return stacknodes[top];
}
int main()
{
const int n=5;
int data;
arraystack<int> stk;
int a[n]={4,8,6,12,9};
for(int i=0;i<n;i++)
stk.push(a[i]);
while(!stk.isempty())
{
data=stk.gettop();
cout<<"pop out:"<<data<<endl;
stk.pop();
}
}
2.链表方式实现如下：
#include<iostream>
using namespace std;
template <class T>
struct linknode{
T data;
linknode* next;
};
template <class T>
class mystack{
public:
mystack();
~mystack();
bool isempty();
void push(const T& data);
void pop();
T& gettop();
private:
linknode<T> *head;
linknode<T> *top;
int length;
};
template <class T>
mystack<T>::mystack()
{
head=NULL;
top=NULL;
length=0;
cout<<"the stack is constructed!"<<endl;
}
template <class T>
mystack<T>::~mystack()
{
while(!isempty())
pop();
cout<<"the stack is destructed!"<<endl;
}
template <class T>
bool mystack<T>::isempty()
{
if(head==NULL)
return true;
else
return false;
}
template <class T>
void mystack<T>::push(const T& data)
{
if(!head)
{
head=new linknode<T>;
head->data=data;
head->next=NULL;
top=head;
length++;
cout<<"push in:"<<top->data<<endl;
}
else
{
linknode<T> *p=new linknode<T>;
p->data=data;
p->next=NULL;
top->next=p;
top=p;
length++;
cout<<"push in:"<<top->data<<endl;
}
}
template <class T>
void mystack<T>::pop()
{
if(!isempty())
{
linknode<T> *p=head;
if(p==top)
{
head=NULL;
top=NULL;
}
else
{
while(p->next!=top)
{
p=p->next;
}
top=p;
p=top->next;
}
delete p;
length--;
}
}
template <class T>
T& mystack<T>::gettop()
{
if(!isempty())
return top->data;
}
int main()
{
const int n=5;
int data;
mystack<int> stk;
int a[n]={4,8,6,12,9};
for(int i=0;i<n;i++)
stk.push(a[i]);
while(!stk.isempty())
{
data=stk.gettop();
cout<<"pop out:"<<data<<endl;
stk.pop();
}
}