창고 와 대열 연습 문제

목차
하나, 두 개의 창고 가 하나의 대열 을 실현 하 다
2. 두 개의 대열 이 하나의 스 택 을 실현 합 니 다.
하나, 두 개의 창고 가 하나의 대열 을 실현 하 다
       분석: 스 택 은 후진 이 먼저 나 오고 대열 은 먼저 나 옵 니 다.만약 에 두 개의 스 택 으로 하나의 대열 을 실현 하려 면 주요 한 두 개의 인 터 페 이 스 는 바로 입 대 를 실현 하 는 것 이다. 그래서 우 리 는 두 개의 스 택 을 항상 하 나 를 입 대 스 택 으로 유지 하고 하 나 는 출 대 스 택 으로 구체 적 으로 아래 에서 분석 하도록 한다.
       1. 정의

typedef struct QueueByTwoStack
{
    Stack s1;  //   
    Stack s2;  //   
}QueueByTwoStack;

       2. 입단 / 출전
       분석:
               (1) 입 대: s1 을 입 대 스 택 으로 정의 하면 입 대 했 을 때 두 스 택 이 비어 있 는 지 없 는 지 에 관 계 없 이 s1 로 입 주 했 습 니 다.
               (2) 출 대: 출 대 하려 면 두 번 째 스 택 을 빌려 야 합 니 다. 처음에 우리 가 스 택 에 들 어간 모든 데 이 터 는 s1 에 있 었 습 니 다. 만약 에 대열 의 출 대 를 실현 하려 면 s1 중의 데 이 터 를 s2 에 부 어야 합 니 다. 모든 데 이 터 를 뒤 집 었 을 때 우 리 는 s2 의 스 택 바닥 은 s1 의 스 택 이 고 s2 의 스 택 지붕 은 s1 의 스 택 바닥 이 므 로 팀 을 실현 합 니 다.바로 s2 의 스 택 을 스 택 에서 내 는 것 입 니 다. 그래서 방법 은 s2 가 비어 있 지 않 으 면 s2 스 택 의 정상 요 소 를 직접 내 면 됩 니 다.만약 s2 가 비어 있다 면, 우 리 는 s1 에 있 는 원소 의 개 수 를 제어 하여 팀 을 나 갈 수 있 으 며, 팀 을 나 간 후, s2 에 남 은 데 이 터 는 다음 팀 을 기다 리 면 된다.

void QueueByTwoStackPush(QueueByTwoStack* qts, DataType d)
{
	assert(qts);

	StackPush(&(qts->s1), d);
}

void QueueByTwoStackPop(QueueByTwoStack* qts)
{
	assert(qts);

	//1、  s2   ，    
	//2、  s2    ，  s1      ，  
	if (StackEmpty(&(qts->s2)) == 0)
	{
		while (StackEmpty(&(qts->s1)))
		{
			StackPush(&(qts->s2), StackTop(&(qts->s1)));
			StackPop(&(qts->s1));
		}
	}
	StackPop(&(qts->s2));
}

       3. 나머지 인터페이스 

void QueueByTwoStackInit(QueueByTwoStack* qts)
{
	StackInit(&(qts->s1));
	StackInit(&(qts->s2));
}

void QueueByTwoStackDestory(QueueByTwoStack* qts)
{
	StackDestory(&(qts->s1));
	StackDestory(&(qts->s2));
}

DataType QueueByTwoStackFront(QueueByTwoStack* qts)
{
        //S2    ，s1    
        //1、  s2   ，      s2   
        //2、  s2  ，         ，     s1   ，        
        //   s1  s2 ，      s2   
	if (StackEmpty(&(qts->s2)) == 0)
	{
		while (StackEmpty(&(qts->s1)))
		{
			StackPush(&(qts->s2), StackTop(&(qts->s1)));
			StackPop(&(qts->s1));
		}
	}
	return StackTop(&(qts->s2));
}

int QueueByTwoStackSize(QueueByTwoStack* qts)
{
	return StackSize(&(qts->s1)) + StackSize(&(qts->s2));
}

int QueueByTwoStackEmpty(QueueByTwoStack* qts)
{
	return StackEmpty(&(qts->s1)) | StackEmpty(&(qts->s2));
}

void TestQueueByTwoStack()
{
	QueueByTwoStack qts;
	QueueByTwoStackInit(&qts);

	QueueByTwoStackPush(&qts, 1);
	QueueByTwoStackPush(&qts, 2);
	QueueByTwoStackPush(&qts, 3);
	QueueByTwoStackPush(&qts, 4);
	QueueByTwoStackPush(&qts, 5);

	while (QueueByTwoStackEmpty(&qts))
	{
		printf("%d ", QueueByTwoStackFront(&qts));
		QueueByTwoStackPop(&qts);
	}
	printf("
");

	QueueByTwoStackDestory(&qts);
}

2. 두 개의 대기 열 이 하나의 스 택 을 실현 합 니 다.
        분석: 첫 번 째 문 제 를 통 해 두 번 째 문 제 는 쉽게 생각 할 수 있 습 니 다. 두 대열 에서 우리 가 해 야 할 일 은 그 중의 하 나 를 항상 비 워 두 는 것 입 니 다.
1. 정의

typedef struct StackByTwoQueue
{
    Queue q1;
    Queue q2;
}StackByTwoQueue;

2. 입고 / 출고 
     분석:
             (1) 입 스 택: 입 스 택 은 비 어 있 는 대기 열 에 데 이 터 를 입력 합 니 다.이 유 는 이것 이 하나의 대기 열 이기 때 문 입 니 다. 우 리 는 데이터 가 들 어 오 는 순서 만 일치 시 키 면 됩 니 다. 항상 빈 대기 열 을 유지 하 는 것 은 스 택 을 나 가기 위해 준비 하 는 것 입 니 다.
             (2), 출고: 위 에서 이미 빈 대기 열 은 출고 준 비 를 위 한 것 이 라 고 말 했다.왜냐하면 이것 은 두 개의 대열 이다. 우리 가 아무리 첫 번 째 문제 처럼 거꾸로 해도 우리 가 얻 은 결 과 는 모두 같다. 팀 에 저 장 된 물건 은 변 하지 않 고 하나의 대열 을 바 꾸 어 저장 할 뿐이다.그러나 거꾸로 하 는 과정 에서 비 공 대기 열 에 남 은 데 이 터 를 발 견 했 을 때 이 데 이 터 는 바로 우리 가 스 택 에서 나 가 고 싶 은 데이터 이기 때문에 비 공 대기 열 에 있 는 데이터 개 수 를 제어 하여 스 택 에서 나 가 고 싶 은 데 이 터 를 찾 을 수 있 습 니 다.따라서 스 택 에서 두 개의 대기 열 을 정의 합 니 다. 하 나 는 빈 대기 열 을 기록 하고 하 나 는 빈 대기 열 이 아 닙 니 다.

void StackByTwoQueuePush(StackByTwoQueue* stq, DataType d)
{
	assert(stq);

        //1、  q1  ，  q1   
        //2、  q1  ，  q2   
	if (QueueEmpty(&(stq->q1)) != 0)
	{
		QueuePush(&(stq->q1), d);
	}
	else
	{
		QueuePush(&(stq->q2), d); 
	}
}

void StackByTwoQueuePop(StackByTwoQueue* stq)
{
	Queue* empty = NULL;  
	Queue* nonempty = NULL; 

	assert(stq);

	empty = &(stq->q1);     //     
	nonempty = &(stq->q2);      //      
        //1、  q1     ，      ，          
	if (QueueEmpty(&(stq->q1)) != 0)
	{
		empty = &(stq->q2);
		nonempty = &(stq->q1);
	}
        //2、       ，             
        //           
	while (QueueSize(nonempty) > 1)
	{
		QueuePush(empty, QueueFront(nonempty));
		QueuePop(nonempty);
	}
        //3、   
	QueuePop(nonempty);
}

3. 기타 인터페이스 

void StackByTwoQueueInit(StackByTwoQueue* stq)
{
	QueueInit(&(stq->q1));
	QueueInit(&(stq->q2));
}

void StackByTwoQueueDestory(StackByTwoQueue* stq)
{
	QueueDestory(&(stq->q1));
	QueueDestory(&(stq->q2));
}

DataType StackByTwoQueueTop(StackByTwoQueue* stq)
{
        //         ，        
        //           
	if (QueueEmpty(&(stq->q1)))
	{
		return QueueBack(&(stq->q1));
	}
	else
	{
		return QueueBack(&(stq->q2));
	}
}

int StackByTwoQueueSize(StackByTwoQueue* stq)
{
	return QueueSize(&(stq->q1)) + QueueSize(&(stq->q2));
}

int StackByTwoQueueEmpty(StackByTwoQueue* stq)
{
	return QueueEmpty(&(stq->q1)) | QueueEmpty(&(stq->q2));
}

void TestStackByTwoQueue()
{
	StackByTwoQueue stq;
	StackByTwoQueueInit(&stq);

	StackByTwoQueuePush(&stq, 1);
	StackByTwoQueuePush(&stq, 2);
	StackByTwoQueuePush(&stq, 3);
	StackByTwoQueuePush(&stq, 4);
	StackByTwoQueuePush(&stq, 5);

	while (StackByTwoQueueEmpty(&stq))
	{
		printf("%d ", StackByTwoQueueTop(&stq));
		StackByTwoQueuePop(&stq);
	}
	printf("
");

	StackByTwoQueueDestory(&stq);
}