qstack.hpp

八皇后问题

//=======================================================================
//	DECLARATION AND DEFINITION OF SEQUENCE STACK CLASS
//
//	DESCRIPTION:Used to solve the Eight Queen Problem.
//
//	FILE NAME:QStack.hpp
//
//	2005/03/13 CREATED BY ZHUJI
//	LAST MODIFIED:2005/03/17 20:20
//=======================================================================

#ifndef QSTACK_HPP
#define QSTACK_HPP

#ifndef NULL
#define NULL 0
#endif

#include "pLib.h"

class QStack
{
private:
//=======================================================================
//	PRIVATE VARIABLES DECLARATION
//=======================================================================
	QPoint *Data;				//Storing the queen's position
	int     QPos;				//Storing the first queen's position
	int     Size;				//Storing the maximum size of the stack
	int     Top;				//Storing the top of the stack

public:
//=======================================================================
//	PUBLIC FUNCTION DEFINITION
//=======================================================================

//=======================================================================
//	FUNCTION:QStack()
//
//	DESCRIPTION:Default constructor.
//=======================================================================
	QStack(void){
		Top  = -1;
		QPos = -1;
		Size = GRIDCOUNT;
		Data = new QPoint[Size];
	}

//=======================================================================
//	FUNCTION:QStack()
//
//	DESCRIPTION:Copy constructor.
//=======================================================================
	QStack(const QStack &Stack){
		QPos = Stack.QPos;
		Size = Stack.Size;
		Data = new QPoint[Size];

		for(Top=-1;Top<Stack.Top;++Top)
			Data[Top+1] = Stack.Data[Top+1];

		if(QPos != -1)
			Data[QPos] = Stack.Data[QPos];
	}

//=======================================================================
//	FUNCTION:~QStack()
//
//	DESCRIPTION:Destructor.
//=======================================================================
	~QStack(){
		delete Data;
		Data  = NULL;
		Top   = -1;
		QPos  = -1;
		Size  =  0;
	}

//=======================================================================
//	FUNCTION:size()
//
//	DESCRIPTION:Return the maximum size of the stack.
//=======================================================================
	int size(void){
		return(Size);
	}

//=======================================================================
//	FUNCTION:length()
//
//	DESCRIPTION:Return the amount of the elements in the stack.
//=======================================================================
	int length(void){
		if(Top < QPos)
			return(Top+1);
		else
			return(Top);
	}

//=======================================================================
//	FUNCTION:isEmpty()
//
//	DESCRIPTION:If the stack is empty, then return true; otherwise return
//	false.
//=======================================================================
	bool isEmpty(void){
		return(Top == -1);
	}

//=======================================================================
//	FUNCTION:isFull()
//
//	DESCRIPTION:If the stack is full, then return true; otherwise return
//	false.
//=======================================================================
    bool isFull(void){
        return((Top+1 == Size) || ((Top+2 == Size) && (QPos+1 == Size)));
    }

//=======================================================================
//	FUNCTION:InLine()
//
//	DESCRIPTION:Check whether there is a queen in the line of the queen
//	that stored at the Top position. If so, return the queen.
//=======================================================================
	QPoint InLine(void){
		QPoint myQueen = Data[Top];

        if(Top < QPos)
        {
            if(Data[QPos].ColPos == myQueen.ColPos)
                return(Data[QPos]);
            else if(Data[QPos].ColPos-QPos == myQueen.ColPos-Top)
                return(Data[QPos]);
            else if(Data[QPos].ColPos+QPos == myQueen.ColPos+Top)
                return(Data[QPos]);
        }

		for(int i=Top-1;i>=0;--i)
		{
            if(Data[i].ColPos == myQueen.ColPos)
                return(Data[i]);
            else if(Data[i].ColPos-i == myQueen.ColPos-Top)
                return(Data[i]);
            else if(Data[i].ColPos+i == myQueen.ColPos+Top)
                return(Data[i]);
            else
                continue;
		}

		myQueen.X = 0;
		myQueen.Y = 0;
        myQueen.ColPos = -1;
        return myQueen;
	}

//=======================================================================
//	FUNCTION:PushQueen()
//
//	DESCRIPTION:Storing the queen into stack.
//=======================================================================
	bool PushQueen(const QPoint &Queen){
		if(Top+1 == Size)
			return false;
		else
		{
			if(Top+1 == QPos)
			{
				if(Top+2 == Size)
					return false;
				else
					++Top;
			}

			Data[++Top] = Queen;

			return true;
		}
	}

//=======================================================================
//	FUNCTION:PopQueen()
//
//	DESCRIPTION:Return the queen and delete it from the stack.
//=======================================================================
	QPoint PopQueen(void){
		if(Top == -1)
		{
			QPoint temp;

			temp.X = 0;
			temp.Y = 0;
			temp.ColPos = -1;

			return(temp);
		}
		else
		{
			--Top;

			if(Top == QPos)
			{
				if(QPos == -1)
					return(Data[Top+1]);
				else
				{
					--Top;
					return(Data[Top+2]);
				}
			}
			else
				return(Data[Top+1]);
		}
	}

//=======================================================================
//	FUNCTION:clear()
//
//	DESCRIPTION:Clear the stack.
//=======================================================================
	void clear(void){
		Top  = -1;
		QPos = -1;
	}

//=======================================================================
//	FUNCTION:SetFQueen()
//
//	DESCRIPTION:Storing the first queen at the indicated position.
//=======================================================================
	bool SetFQueen(const QPoint &Queen,const int Pos){
		if(Pos>=0 && Pos<=Size)
		{
			QPos = Pos - 1;
			Data[QPos] = Queen;

			if(Top == QPos)
				--Top;

			return true;
		}
		else
			return false;
	}

//=======================================================================
//	FUNCTION:GetFQueen()
//
//	DESCRIPTION:Return the first queen.
//=======================================================================
	QPoint GetFQueen(void){
		if(QPos == -1)
		{
			QPoint temp;

			temp.X = 0;
			temp.Y = 0;
			temp.ColPos = -1;

			return(temp);
		}
		else
			return(Data[QPos]);
	}

//=======================================================================
//	FUNCTION:GetFQueenPos()
//
//	DESCRIPTION:Return the first queen's position.
//=======================================================================
    int GetFQueenPos(void){
        return(QPos+1);
    }

//=======================================================================
//	FUNCTION:GetQueen()
//
//	DESCRIPTION:Return the queen.
//=======================================================================
	QPoint GetQueen(const int Pos){
		if(Pos>=0 && Pos<=Top+1)
		{
			if(Pos-1 < QPos)
				return(Data[Pos-1]);
			else
				return(Data[Pos]);
		}
		else
		{
			QPoint temp;

			temp.X = 0;
			temp.Y = 0;
			temp.ColPos = -1;

			return(temp);
        }
	}

//=======================================================================
//	FUNCTION:operator []()
//
//	DESCRIPTION:Overloaded operator [].
//=======================================================================
	QPoint operator [](const int Pos){
		if(Pos>=0 && Pos<=Top+1)
		{
			if(Pos-1 < QPos)
				return(Data[Pos-1]);
			else
				return(Data[Pos]);
		}
		else
		{
			QPoint temp;

			temp.X = 0;
			temp.Y = 0;
			temp.ColPos = -1;

			return(temp);
        }
	}

//=======================================================================
//	FUNCTION:operator =()
//
//	DESCRIPTION:Overloaded operator =.
//=======================================================================
	QStack &operator =(const QStack &Stack){
		if(Data != NULL)
			delete [] Data;

		QPos = Stack.QPos;
		Size = Stack.Size;
		Data = new QPoint[Size];

		for(Top=-1;Top<Stack.Top;++Top)
			Data[Top+1] = Stack.Data[Top+1];

		if(QPos != -1)
			Data[QPos] = Stack.Data[QPos];

        return *this;
	}
};

#endif