C++实现顺序栈和链栈（使用模板类）
顺序栈
类定义
//顺序栈
#pragma once
const int Maxsize = 10;
template
class Sq_Stack
{
private:
T s[Maxsize];
int top;
public:
Sq_Stack();
bool isEmpty();
bool isFull();
bool Push(T elem);
bool Pop(T& elem);
~Sq_Stack();
};
总体实现
//顺序栈
#include "Sq_Stack.h"
template
Sq_Stack::Sq_Stack()
{
top = 0;
}
template
bool Sq_Stack::isEmpty()
{
return top == 0;
}
template
bool Sq_Stack::isFull()
{
return top == Maxsize;
}
template
bool Sq_Stack::Push(T elem)
{
if (isFull())
return false;
else
{
s[top++] = elem;
return true;
}
}
template
bool Sq_Stack::Pop(T& elem)
{
if (isEmpty())
return false;
else
{
elem = s[--top];
return true;
}
}
template
Sq_Stack::~Sq_Stack()
{
top = 0;
}
分块
初始化
template
Sq_Stack::Sq_Stack()
{
top = 0;
}
判空
template
bool Sq_Stack::isEmpty()
{
return top == 0;
}
判满
template
bool Sq_Stack::isFull()
{
return top == Maxsize;
}
入栈
template
bool Sq_Stack::Push(T elem)
{
if (isFull())
return false;
else
{
s[top++] = elem;
return true;
}
}
出栈
template
bool Sq_Stack::Pop(T& elem)
{
if (isEmpty())
return false;
else
{
elem = s[--top];
return true;
}
}
销毁（逻辑销毁）
template
Sq_Stack::~Sq_Stack()
{
top = 0;
}
链栈
结点定义
template
class Node
{
public:
T data;
Node* next;
};
方法定义
template
class Link_Stact
{
private:
Node* top;
public:
Link_Stact();
bool isEmpty();
void Push(T elem);
bool Pop(T& elem);
};
总体实现
//链栈
#include
#include "Link_Stack.h"
template
Link_Stact::Link_Stact()
{
top = NULL;
}
template
bool Link_Stact::isEmpty()
{
return top == NULL;
}
template
void Link_Stact::Push(T elem)
{
Node* p = new Node;
p->data = elem;
p->next = top;
top = p;
}
template
bool Link_Stact::Pop(T& elem)
{
if (isEmpty())
return false;
else
{
elem = top->data;
top = top->next;
return true;
}
}
分块
初始化
template
Link_Stact::Link_Stact()
{
top = NULL;
}
判空
template
bool Link_Stact::isEmpty()
{
return top == NULL;
}
入栈
template
void Link_Stact::Push(T elem)
{
Node* p = new Node;
p->data = elem;
p->next = top;
top = p;
}
出栈
template
bool Link_Stact::Pop(T& elem)
{
if (isEmpty())
return false;
else
{
elem = top->data;
top = top->next;
return true;
}
}
测试代码
#include
#include "Sq_Stack.h"
#include "Sq_Stack.cpp"
#include "Link_Stack.h"
#include "Link_Stack.cpp"
using namespace std;
int main()
{
//顺序栈测试
Sq_Stack s;
for (int i = 0; i < 10; i++)
s.Push(i + 1);
int k;
for (int i = 0; i < 10; i++)
{
s.Pop(k);
cout << k << " ";
}
cout << endl;
//链栈测试
Link_Stact ls;
for (int i = 0; i < 10; i++)
{
ls.Push('a' + i);
}
char c;
for (int i = 0; i < 10; i++)
{
ls.Pop(c);
cout << c;
}
cout << endl;
return 0;
}
运行结果
