栈的基本操作——顺序栈的类模板定义

栈和队列都是特殊的线性表，是限制存取位置的线性结构；可以由顺序表实现，也可以由链表实现。
什么是栈
栈定义为：只允许在表的一端进行插入和删除的线性表。
允许进行插入和删除的一端叫做栈顶(top)，而另一端叫栈底(bottom)。栈中没有任何元素时，称为空栈。设给定栈s=(a0，a1，……，an-1)，称a0为栈底，an-1为栈顶。
栈又称作后进先出（LIFO：Last In First Out）的线性表。
栈可以用顺序表实现，称顺序栈；也可以用链表实现，称链栈

 

 

"Stack.h"

<strong><span style="font-size:18px;">#pragma once

#include <iostream>
using namespace std;

template<class T>
class Stack
{
public:
Stack()//构造函数
:_array(NULL)
,_top(-1)
,_capacity(0)
{}
~Stack()//析构函数
{
if (_array)
{
delete[] _array;
}
}

void Push(const T& num)//压栈
{
_CheckCapacity();
_array[++_top] = num;
}

void Pop()//出栈
{
if (Empty() == true)
{
printf("Stack is Empty\n");
return;
} 
else
{
--_top;
}
}

T& GetTop()//获取栈的栈顶元素
{
return _array[_top];
}

void PrintStack()//打印栈中的元素
{
for (int i = 0;i <= _top;++i)
{
cout<<_array[i]<<"  ";
}
cout<<endl;
}

void PrintStackTop()//打印栈顶元素
{
cout<<_array[_top];
}

size_t Size()//获取栈的有效大小
{
return _top + 1;
}

T GetElem(int num)//取第i个数据，top不变
{
for (size_t i = 0;i < Size()-1;++i)
{
if (i == num-1)
{
return _array[i];
}
}
return 0;
}

void MackEmpty()//使得栈为空
{
_top = -1;
}
protected:
void _CheckCapacity()//判断栈是否需要在开辟内存空间
{
if (_array == NULL)
{
_capacity = 5;
_array = new T[_capacity];
return;
}

if (_capacity == _top + 1)//动态增容
{
_capacity *= 2;
T* tmp = new T[_capacity];

for (size_t i = 0;i <= _top;++i)
{
tmp[i] = _array[i];
}
_array = tmp;
}
}

bool Empty()//栈是否为空
{
return _top == -1;
}
private:
T* _array;
int _top;
size_t _capacity;
};</span></strong>

 

"test.cpp"

 

<strong><span style="font-size:18px;">#define _CRT_SECURE_NO_WARNINGS 1

#include "stack.h"

void test1()//Push  PrintStack  Pop  GetTop  GetElem   MackEmpty
{
Stack<int> stack;
stack.Push(1);
stack.Push(8);
stack.Push(10);
stack.Push(5);
stack.Push(9);
stack.Push(2);
stack.PrintStack();

stack.Pop();
stack.Pop();
stack.PrintStack();

int ret = stack.GetTop();
printf("%d \n",ret);

int tmp = stack.GetElem(3);
printf("%d \n",tmp);

stack.MackEmpty();
stack.PrintStack();

}
int main()
{
test1();
system("pause");
return 0;
}</span></strong>