【数据结构】顺序栈（顺序表动态实现）

栈的概念

栈：一种特殊的线性表，其只允许在在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一段称为栈顶，另一端称为栈底。不含任何元素的栈称为空栈，栈又称为后进先出的线性表。

栈的特点：后进先出(LIFO)

顺序栈：

顺序堆栈和顺序表数据成员相同，不同之处，顺序堆栈的入栈和出栈操作只允许对当前栈顶进行

顺序堆栈所有操作的时间复杂度均为O(1)。

实现代码：

Stack.h

#ifndef __STACK_H__
#define __STACK_H__

#include<iostream>
#include<cassert>
using namespace std;
//顺序栈 深拷贝

template <typename T>
class Stack
{
public:
	Stack(size_t capacity = 5)
		:_size(0),
		_capacity(5)
	{
		_capacity = (capacity > _capacity) ? capacity : _capacity;
		_array = new T[_capacity];
	}

	Stack(const Stack<T>& s)
	{
		_array = new T[s._capacity];
		_size = s._size;
		__capacity = s._capacity;

		for (size_t index = 0; index < _size; index++)
		{
			_array[index] = s._array[index];
		}
	}
	//复制重载 普通版
	/*Stack<T>& operator=(const Stack<T>& s)
	{
		_array = new T[s._capacity];
		_size = s._size;
		__capacity = s._capacity;

		for (size_t index = 0; index < _size; index++)
		{
			_array[index] = s._array[index];
		}
		return *this;
	}*/
	//简洁版
	Stack<T>& operator=(const Stack<T>& s)
	{
		if (*this != s)
		{
			Stack temp(s);
			swap(_array, temp._array);
			_size = s._size;
			_capacity = s._capacity;
		}
		return *this;
	}

	~Stack()
	{
		if (Empty())
		{
			delete[] _array;
			_size = 0;
			_capacity = 0;

		}
	}

public:
	//压栈
	void Push(const T data)
	{
		CheckCapacity();
		_array[_size++] = data;
	}
	void Pop()
	{
		--_size;
	}
	Stack<T> Top()
	{
		assert(!Empty());
		//测试栈顶元素
		cout << _array[_size-1] << endl;
		return _array[_size-1];
	}
	size_t Length() const
	{
		return _size;
	}
	void Print()
	{
		assert(!Empty());
		for (int index = 0; index < _size; index++)
		{
			cout << _array[index] << "  ";
		}
	}
private:
	bool Empty()
	{
		return (_size == 0);
	}

	//检查容量
	void CheckCapacity()
	{
		if (_size >= _capacity)
		{
			T* temp = new T[2 * _capacity];
			for (int index = 0; index < _size; index++)
			{
				temp[index] = _array[index];
			}
			_array = temp;
			_capacity *= 2;
		}
	}
private:
	T* _array;
	size_t _size;
	size_t _capacity;

};

#endif

test.c

#include"Stack.h"void Funtest1(){	Stack<int> s1(3);//初始容量小于要求的初始值	Stack<int> s2(7);//大于等于初始值	s1.Push(1);	s1.Push(2);	s1.Push(3);	s1.Push(4);	s1.Push(5);	//容量不足时	s1.Push(6);	s1.Push(7);	s1.Print();	s1.Pop();	s1.Pop();	cout << endl;	s1.Top();	}int main(){	Funtest1();	system("pause");	return 0;}