알고리즘 서론 10.1 - 5 쌍 단 대기 열

NEXT(p, l)
1    if p = l
2        then ret <- 1
3        else ret <- p + 1
4    return ret
PRE(p, l)
1    if p = 1
2        then ret <- l
3        else ret <- p - 1
4    return ret
DEQUEUE-LEFT-INSERT(D, x)
1    l <- PRE([left[D], length[D])
2    if l = right[D]
3        then error "overflow"
4    if left[D] = right[D]
5        right[D] <- NEXT(right[D], length[D])
6   D[left[D]] <- x
7   left[D] <- l
DEQUEUE-RIGHT-INSERT(D, x)
1    r <- NEXT([right[D], length[D])
2    if r = left[D]
3        then error "overflow"
4    if left[D] = right[D]
5        left[D] <- PRE(left[D], length[D])
6    D[right[D]] <- x
7   right[D] <- r 
DEQUEUE-LEFT-DELETE(D)
1    if left[D] = right[D]
2        then error "underflow"
3    ret <- D[left[D]]
4    left[D] <- NEXT(left[D], length[D])
DEQUEUE-RIGHT-DELETE(D)
1    if left[D] = right[D]
2        then error "underflow"
3    ret <- D[right]
4    right[D] <- PRE(right[D], length[D])

//    
struct deque
{
	//                        
	int left;//    ，    1
	int right;//    ，    1
	int length;//    
	int *s;//  
	deque(int size):left(1),right(1),length(size){s = new int[size+1];}
};
//      
void Print(deque D)
{
	int i;
	if(D.right >= D.left)
	{
		for(i = D.left+1; i < D.right; i++)
			cout<<D.s[i]<<' ';
		cout<<endl;
	}
	//         
	else
	{
		for(i = D.left + 1; i <= D.length; i++)
			cout<<D.s[i]<<' ';
		for(i = 1; i < D.right; i++)
			cout<<D.s[i]<<' ';
		cout<<endl;
	}
}
//          
bool Deque_Empty(deque D)
{
	if(D.left == D.right)
		return 1;
	return 0;
}
//       ，    ，                    
int Next(int p, int l)
{
	if(p == l)
		return 1;
	else return p+1;
}
int Pre(int p, int l)
{
	if(p == 1)
		return l;
	else
		return p - 1;
}
//    
void Deque_Left_Insert(deque &D, int x)
{
	//    
	int l = Pre(D.left, D.length);
	if(l == D.right)
	{
		cout<<"error:overflow"<<endl;
		return ;
	}
	//        ，         
	if(D.left == D.right)
		D.right = Next(D.right, D.length);
	D.s[D.left] = x;
	D.left = l;
}
//    ，          
void Deque_Right_Insert(deque &D, int x)
{
	int r = Next(D.right, D.length);
	if(r == D.left)
	{
		cout<<"error:overflow"<<endl;
		return ;
	}
	if(D.left == D.right)
		D.left = Pre(D.left, D.length);
	D.s[D.right] = x;
	D.right = r;
}
//    
int Deque_Left_Delete(deque &D)
{
	//  
	if(D.left == D.right)
	{
		cout<<"error:underflow"<<endl;
		return -1;
	}
	D.left = Next(D.left, D.length);
	//           ，            
	if(Next(D.left,D.length) == D.right)
		D.right = D.left;
	return D.s[D.left];
}
//    ，        
int Deque_Right_Delete(deque &D)
{
	if(D.left == D.right)
	{
		cout<<"error:underflow"<<endl;
		return -1;
	}
	D.right = Pre(D.right, D.length);
	if(Next(D.left,D.length) == D.right)
		D.left = D.right;
	return D.s[D.right];
}