首页 > 其他 > 详细

ArrayStack

时间:2020-04-09 19:51:21      阅读:51      评论:0      收藏:0      [点我收藏+]

??栈是一种线性结构,相比与数组,栈对应的操作时数组的子集,只能从一端添加元素,也只能从一端取出元素,是一种 后进先出(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;
}

ArrayStack

原文:https://www.cnblogs.com/chengmf/p/12668977.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!