数据结构——顺序栈与链栈的C++实现

顺序栈的实现peStaticStack.h

#include "peStaticStack.h"

#define STATICSTACK_SUCCESS0
#define STATICSTACK_ERROR1

template<class T>
class peStaticStack
{
public:
peStaticStack(int size);
~peStaticStack(void);

int StackSize;
int Top;
T* Data;

int Push(T data);
int Pop(T* data);
int Pop(void);
};

template<class T>
peStaticStack<T>::peStaticStack(int size)
{
StackSize = size;
Top = -1;
Data = new T[StackSize];
}

template<class T>
peStaticStack<T>::~peStaticStack(void)
{
delete[] Data;
}

template<class T>
int peStaticStack<T>::Push(T data)
{
if(Top == (StackSize - 1))//栈满
return STATICSTACK_ERROR;

++Top;
Data[Top] = data;

return STATICSTACK_SUCCESS;
}

template<class T>
int peStaticStack<T>::Pop(void)
{

if(-1 == Top)//空栈
return STATICSTACK_ERROR;

--Top;
return STATICSTACK_SUCCESS;
}

template<class T>
int peStaticStack<T>::Pop(T* data)
{
if(-1 == Top)//空栈
return STATICSTACK_ERROR;

*data = Data[Top];
--Top;
return STATICSTACK_SUCCESS;
}

链栈的实现peLinkStack.cpp

#include "peLinkStack.h"
#include<stdlib.h>

#define LINKSTACK_SUCCESS0
#define LINKSTACK_ERROR1

template<class T>
struct LinkStackStru
{
T data;
LinkStackStru<T>* next;
};

template<class T>
class peLinkStack
{
public:
peLinkStack(void);
~peLinkStack(void);

LinkStackStru<T>* Top;
int Count;

int Push(T data);
int Pop(T* data);
int Pop(void);
};

template<class T>
peLinkStack<T>::peLinkStack(void)
{
Top = (LinkStackStru<T>*)malloc(sizeof(LinkStackStru<T>));
Top->next = NULL;
Count = 0;
}

template<class T>
peLinkStack<T>::~peLinkStack(void)
{
}

template<class T>
int peLinkStack<T>::Push(T data)
{
LinkStackStru<T>* p = (LinkStackStru<T>*)malloc(sizeof(LinkStackStru<T>));
p->data = data;
p->next = Top->next;
Top->next = p;
++Count;
return LINKSTACK_SUCCESS;
}

template<class T>
int peLinkStack<T>::Pop(T* data)
{
return LINKSTACK_SUCCESS;
}

template<class T>
int peLinkStack<T>::Pop(void)
{
if(0 == Count)
return LINKSTACK_ERROR;

LinkStackStru<T>* p;
p = Top->next;
Top->next = p->next;
--Count;
free(p);

return LINKSTACK_SUCCESS;
}

Main.cpp

#include <iostream>
#include "peStaticStack.cpp"
#include "peLinkStack.cpp"
using namespace std;

int main()
{
peStaticStack<int> peStack(10);

peStack.Push(1);
peStack.Push(2);
peStack.Push(3);
peStack.Push(4);
peStack.Push(5);
peStack.Push(6);

peStack.Pop();
peStack.Pop();
peStack.Pop();

cout << "Printf Static Statck:" << endl;
cout << "Size = " << peStack.StackSize << endl;
cout << "Top = " << peStack.Top << endl;
for(int i = 0; i <= peStack.Top; ++i)
{
cout << peStack.Data[i] << endl;
}//i

peLinkStack<int> LinkStack;

LinkStack.Push(11);
LinkStack.Push(22);
LinkStack.Push(33);
LinkStack.Push(44);
LinkStack.Push(55);
LinkStack.Push(66);

LinkStack.Pop();
LinkStack.Pop();

cout << "Printf LinkStack:" << endl;
cout << "Count = " << LinkStack.Count << endl;
LinkStackStru<int>* p;
p = LinkStack.Top;
for(int i = 0; i <  LinkStack.Count; ++i)
{
p = p->next;
cout <<  p->data << endl;
}//i

system("pause");
return 0;
}

程序运行结果