c++实现栈

栈的概念

栈是数据结构中一种特殊的线性表，它的基本特性是"先入后出，后入先出"。如下图：

栈的基本操作

栈有基本操作如下：

void Push(const T& d);//入栈
void Pop();//出栈
T& Top();//返回栈顶元素
bool Empty();//判断是否为空栈
size_t Size();//栈中元素个数

栈的实现

Stack.hpp

#pragma once
#include

using namespace std;

template
class Stack
{
public:
Stack();
~Stack();
Stack(const Stack& s);
Stack& operator=(Stack s);
void Push(const T& d);
void Pop();
T& Top();
bool Empty();
size_t Size();
protected:
void _CheckCapacity();
protected:
T* _a;
size_t _top;
size_t _capacity;
};
template
void Stack::_CheckCapacity()
{
if (_a == NULL)
{
_capacity = 3;
_a = new T[_capacity];
return;
}
if (_top == _capacity)
{
_capacity += 3;
T* tmp = new T[_capacity];
for (size_t i = 0; i < _top; i++)
{
tmp[i] = _a[i];
}
delete[] _a;
_a = tmp;
}
}

template
Stack::Stack()
:_a(0)
, _top(0)
, _capacity(0)
{}

template
Stack::~Stack()
{
if (_a)
{
delete[] _a;
}
}
template
Stack::Stack(const Stack& s)
:_top(s._top)
,_capacity(s._capacity)
{
_a = new T[_capacity];
for (size_t i = 0; i < _top; i++)
{
_a[i] = s._a[i];
}

}

template
Stack& Stack::operator=(Stack s)
{
swap(s._a,_a);
_top = s._top;
_capacity = s._capacity;
return *this;
}
//template
//Stack& Stack::operator=(const Stack& s)
//{
// if (this != &s)
// {
// delete[] _a;
// _capacity = s._capacity;
// _top = s._top;
// _a= new T[_capacity];
// for (size_t i = 0; i < _top; i++)
// {
// _a[i] = s._a[i];
// }
// }
// return *this;
//}

template
void Stack::Push(const T& d)
{
_CheckCapacity();
_a[_top++] = d;
}

template
void Stack::Pop()
{
if (_top)
{
--_top;
}
}

template
T& Stack::Top()
{
return _a[_top - 1];
}
template
bool Stack::Empty()
{
if (_top == 0)
return true;
else
return false;
}

template
size_t Stack::Size()
{
return _top;
}

//test.cpp

#include "Stack.h"
#include
int main()
{
Stack s;
s.Push("1111111111111");
s.Push("2222222222222");
s.Push("3333333333333");
s.Push("4444444444444");
s.Push("5555555555555");
Stack s1(s);
Stack s2;
s2 = s;
while (!s2.Empty())
{
cout << s2.Top() << " ";
s2.Pop();
}
getchar();
return 0;
}

运行结果：