栈的概念

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


栈的基本操作

栈有基本操作如下：

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


栈的实现

Stack.hpp


#pragma once
#include<iostream>

using namespace std;

template<class T>
class Stack
{
public:
Stack();
~Stack();
Stack(const Stack<T>& s);
Stack<T>& operator=(Stack<T> 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<class T>
void Stack<T>::_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<class T>
Stack<T>::Stack()
:_a(0)
, _top(0)
, _capacity(0)
{}

template<class T>
Stack<T>::~Stack()
{
if (_a)
{
delete[] _a;
}
}
template<class T>
Stack<T>::Stack(const Stack<T>& 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<class T>
Stack<T>& Stack<T>::operator=(Stack<T> s)
{
swap(s._a,_a);
_top = s._top;
_capacity = s._capacity;
return *this;
}
//template<class T>
//Stack<T>& Stack<T>::operator=(const Stack<T>& 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<class T>
void Stack<T>::Push(const T& d)
{
_CheckCapacity();
_a[_top++] = d;
}

template<class T>
void Stack<T>::Pop()
{
if (_top)
{
--_top;
}
}

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

template<class T>
size_t Stack<T>::Size()
{
return _top;
}


//test.cpp

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

运行结果：