스 택 으로 대기 열 구현

스 택 을 사용 하여 대기 열의 다음 동작 을 수행 합 니 다: push (x) – 하나의 요 소 를 대기 열의 끝 에 넣 습 니 다.pop () – 대기 열 첫 부분 에서 요 소 를 제거 합 니 다.peek () – 대기 열의 첫 번 째 요 소 를 되 돌려 줍 니 다.empty () – 대기 열 이 비어 있 는 지 되 돌려 줍 니 다.예제: MyQueue queue = new MyQueue ();
queue.push(1); queue.push(2); queue.peek(); // 1 queue. pop (); /1 queue. empty (); /false 로 돌아 가기

typedef int STDatatype;
typedef struct Stack
{
	STDatatype* _a;
	int _top;//  
	int _capacity;//  
}Stack;

void StackInit(Stack* ps,int n)
{
	assert(ps);
	ps->_a = NULL;
	ps->_capacity = 0;
	ps->_top = 0;
}
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = 0;
	ps->_top = 0;

}

void StackPush(Stack* ps, STDatatype x)
{
	assert(ps);
	if (ps->_top == ps->_capacity)
	{
		size_t newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
		ps->_a = (STDatatype*)realloc(ps->_a, sizeof(STDatatype)*newcapacity);
		assert(ps->_a);
		ps->_capacity = newcapacity;
	}
	ps->_a[ps->_top] = x;
	ps->_top++;
}
void StackPop(Stack* ps)
{
	assert(ps);
    if(ps->_top > 0)
    {
        	ps->_top--;
    }
}
STDatatype StackTop(Stack* ps)
{
	assert(ps);
	return ps->_a[ps->_top - 1];
}
int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->_top == 0 ? 0 : 1;
}
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}
typedef struct {
    Stack pushST;
    Stack popST;
} MyQueue;

/** Initialize your data structure here. */
MyQueue* myQueueCreate(int maxSize) {
    MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&queue->pushST,maxSize);
    StackInit(&queue->popST,maxSize);
    return queue;
    
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushST,x);
}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
   if(StackEmpty(&obj->popST) == 0)
   {
       while(StackEmpty(&obj->pushST) != 0)
       {
           StackPush(&obj->popST,StackTop(&obj->pushST));
           StackPop(&obj->pushST);
       }
   }
    int front = StackTop(&obj->popST);
    StackPop(&obj->pushST);
    return front;
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->popST) == 0)
   {
       while(StackEmpty(&obj->pushST) != 0)
       {
           StackPush(&obj->popST,StackTop(&obj->pushST));
           StackPop(&obj->pushST);
       }
   }
    return StackTop(&obj->popST);
    
}

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
    if(StackEmpty(&obj->pushST) == 0 && StackEmpty(&obj->popST) == 0)
        return true;
    else
        return false; 
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->pushST);
    StackDestroy(&obj->popST);
    free(obj);
    obj = NULL;
}