데이터 구조 (1) - 순서 스 택 의 실현 과 괄호 가 일치 하 는 응용

왜 창고 부터 시작 합 니까?저 는 선형 부분 이 비교적 간단 한 것 은 스 택 과 대기 열 이 라 고 생각 하기 때문에 많이 사용 합 니 다. 많은 사람들 이 링크 가 간단 하 다 고 생각 합 니 다. 사실은 링크 가 간단 합 니까?링크 가 파생 될 수 있 는 것 은 오히려 많다. 일시 적 으로 이해 할 수 있 는 것 이 아니 라 마이크로소프트 의 채용 소감 회고 문 에서 마이크로소프트 면접 관 이 그 에 게 어떻게 두 개의 링크 로 하나의 스 택 을 실현 하 느 냐 고 물 었 던 것 을 기억 하고 있다.물론 지금 순 서 를 어 지 럽 히 는 것 은 대학 1 학년 때 데이터 구 조 를 배 웠 기 때 문 입 니 다. 지금 은 더 깊이 있 고 다양한 토론 만 하고 있 기 때문에 처음부터 가 르 치 는 구조 에 신경 쓰 지 않 습 니 다. 이것 은 초보 적 인 튜 토리 얼 이 아 닙 니 다.
잔말 말고 스 택 공 부 를 시작 하 다.
우선, 스 택 은 선형 표 의 확장 입 니 다. 한 쪽 에서 만 수정 할 수 있 기 때문에 고급 언어 로 이 루어 진다 면 LinearList 를 직접 계승 하여 파생 할 수 있 습 니 다. 그러나 이런 방법 은 효율 적 인 문제 가 발생 하고 코드 와 주석 을 구체 적 으로 볼 수 있 습 니 다.
그래서 우 리 는 Stack 기본 클래스 를 사용자 정의 하 는 것 을 선택 합 니 다.
4. 567913. 프로그램 은 템 플 릿 함 수 를 사용 하여 정의 하 는데 예전 의 방법 과 다르다.이것 은 회고, 정리, 확대 와 깊이 가 있 기 때문에 이전의 정의 와 달리 불가피 하 다 고 말 했다.뒤의 장 에는 서로 다른 방법, 서로 다른 정의 의 실현 이 있 을 것 이 고, 판매 자 는 여기 서 먼저 이다.
이어서 괄호 매 칭 을 실현 하 겠 습 니 다.괄호 매 칭 방법 도 많 으 니 참고 하 시기 바 랍 니 다.

/*template
class Stack::private LinearList{
	//LIFO  
	//   Stack       ，   Stack         ，    LinearList     
public:
	Stack(int MaxStackSize = 10) :LinearList(MaxStackSize) {}
	bool IsEmpty() const{
		return LinearList::IsEmpty();
	}
	bool IsFull() const{
		return (Length() == GetMaxSize());//   LinearList        GetMaxSize()，
	}
	T Top() const{
		if (IsEmpty()) throw OutOfBounds();
		T x;
		Find(Length(), x);
		return x;
	}
	Stack& Add(const T& x){
		Insert(Length(), x);
		return *this;
	}
	Stack& Delete(T& x){
		LinearList::Delete(Length(), x);
		return *this;
	}
};
    ，             。  ：
            ，          length()，      Insert()。 Insert                 ，        for        0      
          
     Stack       ，      
*/

template
class Stack{
	//LIFO  
public:
	Stack(int MaxStackSize = 10);
	~Stack(){ delete[] stack; }
	bool IsEmpty() const { return top == -1; }
	bool IsFull() const { return top == MaxTop; }
	T Top() const;
	Stack& Add(const T& x);
	Stack& Delete(T& x);
private:
	int top;//  
	int MaxTop;//      
	T *stack;//      
};

template
Stack::Stack(int MaxStackSize){
//Stack     
	MaxTop = MaxStackSize - 1;
	stack = new T[MaxStackSize];
	top = -1;
}

template
T Stack::Top() const{
//      
	if (IsEmpty()) throw OutOfBounds();
	else return stack[top];
}

template
Stack& Stack::Add(const T& x){
	//    x
	if (IsFull()) throw NoMem();
	stack[++top] = x;
	return *this;
}

template
Stack& Stack::Delete(T& x){
	//    x
	if (IsEmpty()) throw OutOfBounds();
	x = stack[top--];
	return *this;
}

class OutOfBounds{
public:
	OutOfBounds() {}
};

class NoMem{
public:
	NoMem(){}
};
// new  NoMem     xalloc  
void my_new_handler(){
	throw NoMem();
}
std::new_handler Old_Handler_=std::set_new_handler(my_new_handler);

이 프로그램 이 그리 복잡 하지 않 기 때문에 실 현 된 그림 을 올 리 지 않 습 니 다.