데이터 구조 요약 - 대기 행렬 과 스 택

대열 과 스 택 은 순서 와 체인 식 대열 과 스 택 으로 나 뉘 는데 나 는 귀납 할 만 한 것 이 없고 어렵 지 않다 고 생각한다.대열 은 먼저 들 어가 고 먼저 나 가 고, 창 고 는 먼저 들 어간 후에 나온다.대기 열, 그리고 순환 대기 열.쌓 기 정렬 과 결합 하면 우선 대기 열 이 있 습 니 다.그리고 일부 전형 적 인 응용 도 있 습 니 다. 예 를 들 어 접미사 전환 접미사, 접미사 계산 등 은 스 택 을 사용 한 다음 에 이 진 트 리 의 일부 스 트 리밍 도 대기 행렬 과 스 택 을 자주 사용 합 니 다.쉽게 말 하면 순서 저장 구조 (예 를 들 어 배열) 와 체인 저장 구조 (예 를 들 어 링크) 를 한 번 밀봉 한 다음 에 이런 저장 구조 에 새로운 성질 을 주 었 다.마지막 으로 그 말 입 니 다. 생각 만 파악 하면 구체 적 으로 실현 하면 수준 있 게 스타일 을 쓸 수 있 습 니 다!
1. 대기 열:

template <class T>
class Queue
{
protected:
	int front,rear;	         
		T  *data;	         
	int maxsize;	         
public:
	Queue ( int sz = 10 ){
		rear= front=0;
		maxsize=sz;
		data=new T[maxsize];
	};        
	~Queue ( ) { 
		delete [ ] data; 
	}
	void Enq ( T & item );    
	int Outq( T & item);            
	void MakeEmpty ( );    
	int IsEmpty ( );
	int IsFull ( );
};
template <class T>
void Queue<T>::Enq( T & item )
{
	assert ( !IsFull ( ) );	       //      
	data[ rear] = item;     //     
	rear++;
}
template <class T>
int  Queue<T>::Outq( T & item)
{
	if ( IsEmpty ( ) ) return 0;  //
	item=data[front];
	front++;
	return 1;    

}
template <class T>
int  Queue<T>::IsEmpty ( )
{
	if (front==rear)
	{
		return 1;
	} 
	else
	{
		return 0;
	}
}
template <class T>
int  Queue<T>::IsFull( )
{
	if (rear==maxsize)
	{
		return 1;
	} 
	else
	{
		return 0;
	}
}
template <class T>
void  Queue<T>::MakeEmpty()
{
	rear=front=0;
}

2. 창고:

class Stack
{
protected:
	int top;	                   //    
	Type *elements;	            //     
	int maxSize;	                  //     
public:
	Stack ( int sz = 10 );            //    
	~Stack ( ) { delete [ ] elements; }
	void Push ( Type & item );         //  
	int Pop( Type & item);            //  
	Type GetTop ( );                    //   
	void MakeEmpty ( ) { top = -1; }       //   
	int IsEmpty ( ) const { return top == -1; }
	int IsFull ( ) const
	{ return top == maxSize-1; }
};


template <class Type>
Stack<Type> ::Stack ( int s ) : top (-1), maxSize (s)
{
	elements = new Type[maxSize];
	assert ( elements != NULL );        //  
}


template <class Type>
void Stack<Type> ::Push ( Type & item )
{
	assert ( !IsFull ( ) );	       //      
	elements[++top] = item;     //     
} ;

template <class Type>
int Stack<Type> ::Pop (Type &Item )
{
	if ( IsEmpty ( ) ) return 0;  //     
	Item=elements[top];
	top--;
	return 1;                //      
}


template <class Type>
Type Stack<Type>::GetTop ( )
{
	assert ( !IsEmpty ( ) );	     //      
	return elements[top];         //      
}

3. 스 택 의 응용 - 접두사 접 두 사 를 바 꾸 고 계산 합 니 다.

//     ：          ，           “(”  ，   “）”          “（”，
//  “（”   ，
//                。       ，
//              ，         ，       ，                 ，   
//      ，        。               。
void operation(char* exp1)//     
{
	int i=0;
	int pos1=0,pos2=0;
	char *exp2;
	exp2=new char[100];
	char temp;
	Stack<char> s2(100);//            
	char first='#';
	s2.Push(first);
	while(exp1[pos1]!='#')
	{
		if(judgenum(exp1[pos1]))
		{
			exp2[pos2]=exp1[pos1];
			pos2++;
			pos1++;
		}
		else
		{
			char sign=judgeop(s2.GetTop(),exp1[pos1]);
			switch(sign)
			{
			case '>':s2.Push(exp1[pos1]),pos1++;break;
			case '=':s2.Pop(temp),pos1++;break;
			case '<':
				{
					s2.Pop(temp);
					exp2[pos2]=temp;
					pos2++;
					break;
				}
			}
		}
	}
	while(s2.Pop(temp))
	{
		exp2[pos2]=temp;
		pos2++;
	}
	cout<<"      ：";
	while(exp2[i]!='#')
	{
		cout<<exp2[i]<<" ";
		i++;

	}
	cout<<endl;
	cout<<"   ：";
	Result(exp2);
	cout<<endl;
	delete[]exp2;
}
char judgeop(char o1,char o2)//     
{
	switch(o1)
	{
	case '#':return '>';
	case '+':{switch(o2)
			 {
				case '*':
				case '/':
				case '(':return '>';
				case '+':
				case '-':
				case ')':return '<';
			 }}
	case '-':
		{
			switch(o2)
			{

			case '*':
			case '/':
			case '(':return '>';
			case '+':
			case '-':
			case ')':return '<';
			}
		}
	case '*':
		{
			switch(o2)
			{
			case '(':return '>';
			case '*':
			case '/':
			case '-':
			case '+':
			case ')':return '<';
			}
		}
	case '/':
		{
			switch(o2)
			{	
			case '(':return '>';
			case '*':
			case '/':
			case '+':
			case '-':
			case ')':return '<';
			}
		}
	case '(':
		{
			switch(o2)
			{
			case '+':
			case '-':
			case '*':
			case '/':
			case '(':return '>';
			case ')':return '=';
			}
		}

	}
}
double operate(double a,double b,char c)//        
{
	switch(c)
	{
	case '+':return (a+b);
	case '-':return (a-b);
	case '*':return (a*b);
	case '/':return (a/b);
	}
}

//          ，                     ，     ，    
//       ，，，，
void Result(char *exp1)//       
{
	Stack<double> s1(100);
	int pos=0;
	double temp1,temp2;
	double result=0;

	while(exp1[pos]!='#')
	{
		if (exp1[pos]>=48&&exp1[pos]<=57)
		{
			double d=(double)(exp1[pos]-48);
			s1.Push(d);
			pos++;
		} 
		else
		{
			s1.Pop(temp1);
			s1.Pop(temp2);
			result=operate(temp2,temp1,exp1[pos]);
			s1.Push(result);
			pos++;
		}
	}
	s1.Pop(result);
	cout<<result<<endl;
}

4. 대기 열의 응용:

//     ：        ，
void divisition(int r[9][9],int n)
{
	int *q,*temp,*s;
	q=new int[n];
	temp=new int[n];
	s=new int[n];
	Queue<int> que(20);
	int set=0,i,k,per=1;
	for (k=1;k<=n;k++)//          
	{
		que.Enq(k);
	}
	do 
	{
		que.Outq(i);
		if (i<=per)//                    ，        
		{
			set++;//     
			s[i]=set;
			for(k=1;k<=n;k++)
				temp[k]=r[i][k];
			per=i;
		}
		else
		{
			if (temp[i]!=0)//  ，    ，       
			{
				que.Enq(i);
			} 
			else
			{
				s[i]=set;//   ，        
				for (k=i+1;k<=n;k++)
				{
					temp[k]=temp[k]+r[i][k];//          
				}
			}
			per=i;//     ，      
		}
	} while (!que.IsEmpty());
	cout<<"      ：";
	for(int i=1;i<=9;i++)
		cout<<i<<" ";
	cout<<endl;
	cout<<"    ：";
	for(int i=1;i<=n;i++)
		cout<<s[i]<<" ";
	delete []q;
	delete []s;
	delete []temp;

}