數組棧（ArrayStack）

棧

  棧是一種線性結構，相比與數組，棧對應的操作時數組的子集，隻能從一端添加元素，也隻能從一端取出元素，是一種 後進先出（Last In First Ou，LIFO） 的資料結構。

push

pop

代碼底層是動态數組，先閱讀這篇文章更佳 Array.h 點它

棧應用之括号比對

include"ArrayStack.h"
using namespace std;

int isValid(string s)
{
    ArrayStack<char>* stack = new ArrayStack<char>();
    for (int i = 0; i < s.size(); ++i) {
        char c = s.at(i);
        if (c == '(' || c == '[' || c == '{') {
            stack->push(c);
        }
        else {
            if (stack->isEmpty()) {
                return false;
            }
            char topChar = stack->pop();
            if (c == ')' && topChar != '(') {
                return false;
            }
            if (c == ']' && topChar != '[') {
                return false;
            }
            if (c == '}' && topChar != '{') {
                return false;
            }
        }
    }
    return stack->isEmpty();
}

int main()
{
	string str = "(){}[]";
	cout << isValid(str) << endl;
	return 0;
}

           

代碼清單之ArrayStack.h

#pragma once
#include"Array.h"
template<typename T>

class ArrayStack
{
public:
	ArrayStack()
	{
		arr = new Array<T>();	
	}
	ArrayStack(const int capacity)
	{
		arr = new Array<T>(capacity);
	}
	//傳回棧的大小
	int getSize()const;
	//判斷棧是否為空
	bool isEmpty()const;
	//傳回棧的容量
	int getCapacity()const;
	//入棧
	void push(T& t)const;
	//出棧
	T pop()const;
	//傳回棧頂
	T peek()const;
	void print()const;
	~ArrayStack()
	{
		delete arr;
		arr = nullptr;
	}
private:
	Array<T>* arr;
};

template<typename T>
inline int ArrayStack<T>::getSize()const
{
	return arr->getSize();	//調用傳回數組大小，也就是棧的大小
}

template<typename T>
inline bool ArrayStack<T>::isEmpty()const
{
	return arr->isEmpty();	//調用判斷數組是否為空，也就是棧是否為空
}

template<typename T>
inline int ArrayStack<T>::getCapacity() const
{
	return arr->getCapacity();	//調用傳回數組的容量
}

template<typename T>
inline void ArrayStack<T>::push(T& t) const
{
	arr->addLast(t);	//調用從數組尾部添加一個元素
}

template<typename T>
inline T ArrayStack<T>::pop()const
{
	return arr->removeLast();	//調用删除數組的最後一個元素
}

template<typename T>
inline T ArrayStack<T>::peek()const
{
	return arr->getLast();	//調用傳回數組最後一個元素也就是棧頂
}

template<typename T>
inline void ArrayStack<T>::print() const
{
	std::cout << "ArrayStack: size = " << arr->getSize() << ", capacity = " << arr->getCapacity() << std::endl;
	std::cout << "bottom ";
	arr->print();
	std::cout << " top" << std::endl;
}