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

骑猪看日落 2022-06-13 03:41 255阅读 0赞

栈的概念

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

![SouthEast][]

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

顺序栈：

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

![SouthEast 1][]

顺序堆栈所有操作的时间复杂度均为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;
    }

[SouthEast]: /images/20220613/897de8f7027c49f6843a8ed20b931380.png
[SouthEast 1]: /images/20220613/ed9b91b9e4904599bef7d41e8e17b81f.png