데이터 구조 와 알고리즘 대기 열, 스 택

배열, 링크 를 제외 하고 선형 데이터 구조 에서 중요 한 몇 가지 구조 가 있 습 니 다. 대기 열, 스 택.
대기 열, 선진 적 인 데이터 구조 (FIFO), 사실 대기 열 은 두 개의 파이프 로 볼 수 있 습 니 다. 한 입 에서 들 어가 고 다른 입 에서 나 옵 니 다. 먼저 들 어 가 는 것 은 반드시 다른 입 에서 먼저 나 가 야 합 니 다. 그렇지 않 으 면 뒤의 것 이 나 갈 수 없습니다.스 택 은 후진 적 으로 먼저 나 오 는 데이터 구조 (LIFO) 로 스 택 은 하나의 입구 만 있 는 파이프 와 같 습 니 다. 하나의 입 만 들 어 갈 수 있 고 먼저 들 어 가 는 것 은 바닥 에 있 기 때문에 반드시 후진 적 으로 들 어 가 는 것 을 먼저 나 가게 해 야 나 갈 수 있 습 니 다.
대기 열 과 스 택 을 실현 하려 면 순서 로 구 조 를 저장 할 수도 있 고 체인 으로 구 조 를 저장 할 수도 있다.여기 서 사용 하 는 것 은 링크 로 이 루어 지 는 동시에 두 개의 스 택 으로 하나의 대기 열 을 실현 하고 두 개의 대기 열 로 하나의 스 택 을 실현 하 는 알고리즘 (STL 의 quue 와 stack) 도 사용 합 니 다.
1. 대열
대기 열 에서 가장 많이 사용 되 는 동작 은 대기 열 (push) 에 들 어가 서 대기 열 (pop) 을 내 고 팀 의 첫 번 째 값 (front) 을 보 는 것 입 니 다. 대기 열 에 들 어 가 는 것 은 대기 열 에 들 어 가 는 끝 이 고, 대기 열 은 맨 앞 에 있 는 노드 를 삭제 하 는 것 입 니 다.

typedef struct ListNode{
    int element;
    int *next;
}ListNode;
typedef struct LinkedQueue{
    int size;
    ListNode *front;
    ListNode *back;
}LinkedQueue;

/* alloc a node.*/
ListNode* allocNode(int element){
    ListNode *pNode = (ListNode*)malloc(sizeof(ListNode));
    if(pNode){
        pNode->element = elemnt;
        pNode->next = NULL;
    }
    return pNode;
}

/* alloc a queue.*/
LinkedQueue* allocLinkedQueue(){
    LinkedQueue *pQueue = (LinkedQueue*)malloc(sizeof(LinkedQueue));
    if(pQueue){
        pQueue->size = 0;
        pQueue->front = NULL;
        pQueue->back = NULL;
    }
    return pQueue;
}

/* pop a node out of the queue.*/
bool pop(LinkedQueue *pQueue){
    if(NULL == pQueue)
       return false;
    LinkedQueue *pNode = pQueue->front;
    if(pQueue->front == pQueue->back)
        pQueue->back = NULL;
    pQueue->front = pQueue->front->next;
    free(pNode);
    pQueue->size --;
    return true;
}

/* push a node into the queue.*/
bool push(LinkedQueue *pQueue,int element){
    if(NULL == pQueue)
        return false;
    pQueue->size ++;
    if(NULL == pQueue->front){
        pQueue->front = pQueue->back = allocNode(element);
    }
    else
        pQueue->back = allocNode(element);
    return true;
}

/* get the front element from the queue.*/
bool front(LinkedQueue *pQueue,int *element){
    if(pQueue->size){
        *element = pQueue->front->element;
        return true;
    }
    else
        return false;
}

2. 창고
스 택 에서 가장 많이 사용 되 는 작업 은 스 택 에 들 어 가 는 것 (push) 입 니 다. 스 택 (pop) 에서 스 택 꼭대기 의 값 (front) 을 보 는 것 입 니 다. 스 택 에 들 어 가 는 것 은 스 택 의 상단 입 니 다. 스 택 에서 스 택 꼭대기 의 노드 를 삭제 합 니 다.
 

typedef struct ListNode{
    int element;
    struct ListNode *next;
}ListNode;
typedef struct LinkedStack{
    ListNode *topNode;
    ListNode *downNode;
    int stackLength;
}LinkedStack;

/* get the top node from the stack.*/
int top(LinkedStack *pStack){
   return pStack->topNode->element; 
}

/* pop the top node from the stack.*/
void pop(LinkedStack **pStack){
    ListNode *pNode = (*pStack)->topNode->next;
    free(*pStack);
    *pStack = pNode;
}

ListNode* allocNode(int element){
    ListNode *pNode = (ListNode*)malloc(sizeof(ListNode));
    if(NULL != pNode){
        pNode->element = element;
        pNode->next = NULL;
    }
    return pNode;
}

/* push a node into the stack.*/
void push(LinkedStack **pStack,int element){
    ListNode *pNode = allocNode(element);
    pNode->next = (*pStack)->topNode;
    (*pStack)->topNode = pNode;
}

3. 두 개의 스 택 으로 하나의 대기 열 을 실현 합 니 다.
대열 은 먼저 나 가 는 것 이 고, 스 택 은 후진 이 먼저 나 가 는 것 입 니 다. 어떻게 스 택 에서 하나의 요 소 를 먼저 나 가게 합 니까? 관건 은 다른 스 택 을 잘 이용 하 는 것 입 니 다. 대열 의 주요 작업 은 push (), pop (), front () 에 불과 합 니 다.
push 를 실현 하려 면 스 택 에 있 는 push 와 마찬가지 로 수정 할 필요 가 없습니다. pop 과 front 를 실현 하려 면 다른 스 택 을 빌려 야 합 니 다. 먼저 스 택 stack 1 에서 push 를 사용 합 니 다. pop 이나 front 작업 이 있 을 때 우 리 는 요 소 를 stack 1 에서 스 택 을 나 와 stack 2 에 누 릅 니 다. 그러면 stack 1 의 아래쪽 요 소 는 stack 2 상단 요소 로 변 한 다음 stack 2 에서 pop 또는 front 를 실행 합 니 다.작업. 이후 pop 또는 front 작업 은 stack 2 에서 실 행 됩 니 다. stack 2 에서 요소 size 가 0 일 때 stack 1 에서 스 택 을 내 고 stack 2 에 눌 러 서 실 행 됩 니 다. 매번 pop 작업 은 stack 1 에서 만 실 행 됩 니 다.

bool pop(){
    if(!pQueue.stack2.size() && !pQueue.stack1.size())
        return false;
    if(!pQueue.stack2.size()){
        while(pQueue.stack1.size()){
            pQueue.stack2.push(pQueue.stack1.top());
            pQueue.stack1.pop();
        }
    }
    pQueue.stack2.pop();
    return true;
}

int front(){
    if(!pQueue.stack2.size()){
        while(pQueue.stack1.size()){
            pQueue.stack2.push(pQueue.stack1.top());
            pQueue.stack1.pop();
        }
    }
    return pQueue.stack2.top();
} 

4. 두 개의 대기 열 로 하나의 스 택 을 실현 합 니 다.
스 택 에서 가장 중요 한 작업 은 push (), pop (), top () 입 니 다.
push 작업 은 매번 quue 1 에 요 소 를 넣 으 면 됩 니 다. pop 과 top 작업 은 다른 대기 열 을 빌려 야 합 니 다. quue 1 에 5 개의 요 소 를 눌 렀 다 고 가정 합 니 다. 1, 2, 3, 4, 5 는 이때 pop, 즉 요소 5 를 삭제 해 야 합 니 다. 그러면 지금 은 요소 1, 2, 3, 4 pop 을 사용 해 야 pop 요소 5 를 사용 할 수 있 습 니 다. 그러나 스 택 작업 에서 요소 1, 2, 3, 4 는 pop 에 의 해 떨 어 지지 말 아야 합 니 다. 따라서 1, 2, 3, 3, 3 을 사용 해 야 합 니 다.4 push 는 queue 2 에 있 습 니 다. pop 작업 을 할 때마다 queue 1 에 요소 가 있 는 지 확인 하고 n 개의 요소 가 있 으 면 앞의 n - 1 개의 요소 pop 을 한 다음 에 push 를 queue 2 에 넣 은 다음 pop 을 실행 합 니 다. 그렇지 않 으 면 queue 2 의 n - 1 요 소 를 queue 1 에 옮 긴 다음 pop 작업 을 수행 합 니 다. top 작업 은 pop 작업 과 유사 합 니 다.

bool pop(){
    if(!pStack.queue1.size() && !pStack.queue2.size())
        return false;
    
    if(pStack.queue1.size())    {
        while(pStack.queue1.size() != 1){
            pStack.queue2.push(pStack.queue1.front());
            pStack.queue1.pop();
        }
        pStack.queue1.pop();
        return true;
    }
    else{
        while(pStack.queue2.size() != 1){
            pStack.queue1.push(pStack.queue2.front());
            pStack.queue2.pop();
        }
        pStack.queue2.pop();
        return true;
    }
}

int top(){
    if(pStack.queue1.size())    {
        while(pStack.queue1.size() != 1){
            pStack.queue2.push(pStack.queue1.front());
            pStack.queue1.pop();
        }
        return pStack.queue1.front();
    }
    else{
        while(pStack.queue2.size() != 1){
            pStack.queue1.push(pStack.queue2.front());
            pStack.queue2.pop();
        }
        int top = pStack.queue2.front();
        pStack.queue2.pop()
        pStack.queue1.push(top);
        return top;
    }
}

전체 코드 참조: https://github.com/whc2uestc/DataStructure-Algorithm