main.cpp

一个我的数据结构解题集合

#include <stdexcept>
#include <iostream>
#include <stdlib.h>
using namespace std;

class DoubleDirectStack {
	enum { INIT_SIZE = 201 };

	int buf_[INIT_SIZE];	// 栈空间
	int *top1_, *top2_;		// 栈顶指针

public:
	/* 构造函数
	 */
	DoubleDirectStack() {
		top1_ = buf_;
		top2_ = buf_ + INIT_SIZE -1;
	} // DoubleDirectStack()

	/* 第一个栈的入栈函数
	 * 若溢出抛出std::overflow_error异常
	 */
	void push1(int e) {
		if ( top1_ == top2_ )
			throw std::overflow_error("DoubleDirectStack::push1: overflow");
		*top1_++ = e;
	} // push1(int)

	/* 第二个栈的入栈函数
	 * 若溢出抛出std::overflow_error异常
	 */
	void push2(int e) {
		if ( top1_ == top2_ )
			throw std::overflow_error("DoubleDirectStack::push2: overflow");
		*top2_-- = e;
	} // push2(int)

	/* 查询第一个栈的栈顶元素
	 */
	int top1() const {
		if ( top1_ == buf_ )
			throw std::underflow_error("DoubleDirectStack::top1: underflow");
		return *(top1_-1);
	} // top1() const


	/* 查询第二个栈的栈顶元素
	 */
	int top2() const {
		if ( top2_ == buf_ + INIT_SIZE - 1 )
			throw std::underflow_error("DoubleDirectStack::top2: underflow");
		return *(top2_+1);
	} // top2() const

	/* 弹出第一个栈的栈顶元素
	 */
	void pop1() {
		if ( top1_ == buf_ )
			throw std::underflow_error("DoubleDirectStack::top1: underflow");
		--top1_;
	} // pop1()

	/* 弹出第二个栈的栈顶元素
	 */
	void pop2() {
		if ( top2_ == buf_ + INIT_SIZE - 1 )
			throw std::underflow_error("DoubleDirectStack::top2: underflow");
		++top2_;
	} // pop2()

	/* 查询第一个栈的元素数量
	 */
	int size1() const {
		return top1_ - buf_;
	} // size1() const

	/* 查询第二个栈的元素数量
	 */
	int size2() const {
		return buf_ + INIT_SIZE - 1 - top2_;
	} // size2() const

	/* 查询第一个栈是否为空
	 */
	bool isEmpty1() const {
		return size1() == 0;
	} // isEmpty1() const

	/* 查询第二个栈是否为空
	 */
	bool isEmpty2() const {
		return size2() == 0;
	} // isEmpty2() const


}; // DoubleDirectStack

int main() {

	cout << "本程序实现了一个双向增长的栈（最多容纳200个元素），\n"
		 << "下面随便插入一些数据以测试进出栈程序。"
		 << endl;

	{	// 程序块1: 双向压入0~99，然后分别弹出（输出）
		cout << "双向压入0~99，然后分别弹出（输出）: " << endl;

		DoubleDirectStack stack;
		for (int i = 0; i < 100; ++i) {
			stack.push1(i);
			stack.push2(i);
		}

		cout << "Size of Stack1: " << stack.size1() << endl;\
		cout << "Print stack1: " << endl;
		while ( !stack.isEmpty1() ) {
			cout << stack.top1() << ' ';
			stack.pop1();
		}
		cout << endl;
		system("pause");

		cout << "Size of Stack2: " << stack.size2() << endl;
		cout << "Print stack2: " << endl;
		while ( !stack.isEmpty2() ) {
			cout << stack.top2() << ' ';
			stack.pop2();
		}
		cout << endl;
		system("pause");
	}

	{	// 程序块2: 单向压入0~199，然后弹出（测试2个方向）
		cout << "单向压入0~199，然后弹出（测试2个方向）: " << endl;
	
		DoubleDirectStack stack;
		int i;

		for (i = 0; i < 200; ++i) {
			stack.push1(i);
		}

		cout << "Size of Stack1: " << stack.size1() << endl;
		cout << "Print stack1: " << endl;
		while ( !stack.isEmpty1() ) {
			cout << stack.top1() << ' ';
			stack.pop1();
		}
		cout << endl;
		system("pause");

		for (i = 0; i < 200; ++i) {
			stack.push2(i);
		}

		cout << "Size of Stack2: " << stack.size2() << endl;
		cout << "Print stack2: " << endl;
		while ( !stack.isEmpty2() ) {
			cout << stack.top2() << ' ';
			stack.pop2();
		}
		cout << endl;
		system("pause");
	}

	return 0;
}