Queue Blog

7-0 Intro

queue를 끝까지 공부하고 나니 큐를 단독으로 공부하기 보다는 스택과 함께 생각을 하면서 공부를 하 좋을 것 같다고 생각했다.

큐를 공부하다 보면, 단순히 선입’선’출이라는 이유 만으로(=출력 순서가 다르다는 이유 만으로) 스택에서는 발생하지 않았던 문제점들도 꽤 많이 생기고, 탐색 방법에서도 차이를 보인다.

따라서 큐를 공부할 때는 스택과 동일한 기능을 구현하는 과정에서 어떤 차이가 있는 지 확인하고, 그 차이가 ‘탐색 순서’가 다르기 때문에 발생함을 염두에 두면 좋을 것 같다.

7-1 Queue의 이해와 ADT정의

1) Queue의 이해

queue는 선입선출(FIFO)의 구조다. 흔히 발생하는 줄서기, 기다리기 등등의 예시와 연결지어 생각할 수 있다

2) Queue의 ADT

7-2 Implementing Queue (based on array)

1) 큐 구현 논리

큐와 스택은 앞에서 꺼내느냐, 뒤에서 꺼내느냐의 차이만 있기 때문에 스택의 구현에서 조금만 수정하면 된다고 생각할 수도 있지만, 꺼내는 순서의 차이로 발생하는 문제들이 여러 개 있다.

(1) Enqueue

뒤로 넣기 때문에, 무언가 넣을 때 R이 이동할 것이다.

(2) Dequeue

앞으로 빼기 때문에, F가 가리키는 놈을 삭제할 것이다.

(3) Problems

Queue에서 문제가 발생하는 상황을 생각해보자.

이처럼 저장공간이 모두 차지 않았음에도 F와 R이 끝까지 온 상황을 의미한다. 이 경우의 해결은 B, C, F, R모두를 비어있는 앞으로 보내버리면 된다. 그러나, 이렇게 끝까지 왔을 때 마다 노드를 미는 것 보다는, 전체 구조를 원형 배열로 돌리는 것이 훨씬 효율적일 것이다.

2) 원형 큐

(1) Enqueue

노드를 추가함에 따라서 R이 움직이는 구조다.

(2) Dequeue

삭제할 때는 F가 가리키는 노드가 삭제되는 구조다.

(3) Issues

이제 삽입과 삭제 말고 조회와, 비어있는지를 확인해보자.

<문제점>

여기서 문제점이 발생하는데,

F와 R의 위치관계 만으로 (한 칸 앞에 있다는 사실만으로) 현재 메모리가 꽉 차있는 건지, 텅 비어있는 건지 알 수 없다는 점이다.

<해결책>

이런 문제를 개선하기 위해서 F가 가리키는 노드를 비워놓는 방법이 있다. 전에 스택을 공부할 때도 조회와 삭제의 일관성을 위해 비어있는 노드를 하나 삽입했던 것과 같은 해결방법이라고 볼 수 있다 .

<확인>

개선된 원형 큐에서는

텅 빈 상태 = F,R이 동일한 위치를 가리키고 있다.
꽉 찬 상태 = F가 R의 한 칸 앞에 존재한다

(= 구분가능)

3) 원형 큐의 구현

(1) Header File

#ifndef__C_QUEUE_H__
#define __C_QUEUE_H_-
#define TRUE 1
#define FALSE 0
#define QUE_LEN 100

typedef int Data;
typedef struct _cQueue{
int front; //Front pointer
int rear; //Rear pointer
Data queArr[QUE_LEN];
} Queue;

typedef Queue Queue;

void QueueInit (Queue * pq);
int QISEmpty (Queue * pq);

void Enqueue (Queue * pq, Data data);
Data Dequeue (Queue * pq);
Data @Peek (Queue * pq);

#endif

(2) Final Code

#include <stdio.h>
#include <stdlib.h>
#include "CircularQueue.h"

void QueueInit(Queue *pq)
{
    pq->front = 0;
    pq->rear = 0;
}

int QIsEmpty(Queue *pq)
{
    if (pq->front == pq->rear)
        return TRUE;
    else
        return FALSE;
}

int NextPosIdx(int pos)
{
    if (pos == QUE_LEN - 1)
        return 0;
    else
        return pos + 1; // 추가된 부분
}
void Enqueue(Queue *pq, Data data)
{
    if (NextPosIdx(pq->rear) == pq->front)
    {
        printf("Queue Memory Error!");
        exit(-1);
    }

    pq->rear = NextPosIdx(pq->rear);
    pq->queArr[pq->rear] = data;
}

Data Dequeue(Queue *pq)
{
    if (QIsEmpty(pq))
    {
        printf("Queue Memory Error!");
        exit(-1);
    }

    pq->front = NextPosIdx(pq->front);
    return pq->queArr[pq->front];
}

Data QPeek(Queue *pq)
{
    if (QIsEmpty(pq))
    {
        printf("Queue Memory Error!");
        exit(-1);
    }
    return pq->queArr[NextPosIdx(pq->front)];
}

(3) Enqueue

void Enqueue(Queue *pq, Data data)
{
    if (NextPosIdx(pq->rear) == pq->front)
    {
        printf("Queue Memory Error!");
        exit(-1);
    }

    pq->rear = NextPosIdx(pq->rear);
    pq->queArr[pq->rear] = data;
}

if (NextPosIdx(pq->rear) == pq->front) : 큐가 꽉 차있는지 확인하기
NextPosIdx(pq->rear) : Rear포인터를 한 칸 뒤로 민다.
pq->queArr[pq->rear] : 꼬리 포인터가 가리키는 값에 입력을 한다.

7-3 Implementing Queue (based on linked list)

0) stack과의 차이

(1) stack

push와 pop이 일어나는 위치가 Tail로 같은 반면

(2) Queue

enqueue와, dequeue가 발생하는 위치가 각각 Front와 Rear로 다르다.

1)Enqueue

void Enqueue(Queue *pq, Data data)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->next = NULL;
    newNode->data = data;

    if (QIsEmpty(pq))
    {
        pq->front = newNode;
    }
    else
    {
        pq->rear->next = newNode;
    }
    pq->rear = newNode;
}

newNode->next = NULL; : new Node의 다음 노드는 막아둔다
if (QIsEmpty(pq)) : 비어있는지 확인한 후 아무것도 없으면 새로운 노드를 front 포인터가 가리키도록 한다.
- True : pq->front = newNode;
- pq->rear->next = newNode :
- 뭔가 하나라도 있으면 새로운 노드를 꼬리의 다음 노드에 할당한다.

이 과정과, Stack에서 Head에 추가하던 과정을 비교하면

newNode생성하기
Head가 가리키는 곳을 newNode의 꼬리가 가리키도록 하기
Head가 newNode를 가리키도록 하기

2)Dequeue

Data Dequeue(Queue *pq)
{
    Node *delNode;
    Data retData;

    if (QIsEmpty(pq))
    {
        printf("Queue Memory Error!");
        exit(-1);
    }

    delNode = pq->front;
    retData = delNode->data;
    pq->front = pq->front->next;
    free(delNode);
    return retData;
}

QIsEmpty(pq) : 비어있는지 확인해서 비어있으면 → Error
delNode = pq->front : front가 가리키는 노드를 지울 것임.
pq->front = : front 다음놈을 가리키도록 수정한다.
free(delNode)

3) Final Code

void QueueInit(Queue *pq)
{
    pq->front = NULL;
    pq->rear = NULL;
}

int QIsEmpty(Queue *pq)
{
    if (pq->front == NULL)
        return TRUE;
    else
        return FALSE;
}

void Enqueue(Queue *pq, Data data)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->next = NULL;
    newNode->data = data;

    if (QIsEmpty(pq))
    {
        pq->front = newNode;
    }
    else
    {
        pq->rear->next = newNode;
    }
    pq->rear = newNode;
}

Data Dequeue(Queue *pq)
{
    Node *delNode;
    Data retData;

    if (QIsEmpty(pq))
    {
        printf("Queue Memory Error!");
        exit(-1);
    }

    delNode = pq->front;
    retData = delNode->data;
    pq->front = pq->front->next;
    free(delNode);
    return retData;
}

Data Peek(Queue *pq)
{
    if (QIsEmpty(pq))
    {
        printf("Queue Memory Error!");
        exit(-1);
    }
    return pq->front->data;
}

7-4 Utilizing Queue

0) Intro

마지막으로 큐의 활용에 대해 확인해보려고 한다.

사실 예제를 보고 많이 황당했다. 그래서 이 예제를 학습할 때의 방향성은 제시하는 상황과 같은 문제가 발생했을 때 어떻게 큐를 사용해서 해결하는지 확인해보면 좋을 것 같다

1) Situation

결국 문제를 일반화 시킨 후 큐의 어떤 특성이 있기에 활용이 가능했던 건지를 확인해보면 좋을 것 같다.

if(sec%Cus_Come_Term===0) : 15초에 한 번씩 확인해라

Enequeue(&que, CHE_TERM) : 큐 구조 안에 치즈버거를 만드는 시간을 담았음.

2) 삽질 ON

근데 이 문제에서 지금 내가 느끼기에 이상한 점들을 정리해보려고 한다.

(1) Q.

대기실이 꽉 차면 Queue Memory Error가 뜬다고 한다

근데 Circular Queue.c를 확인해보면, 큐가 꽉 찬 상황은 100개의 원형 배열이 가득 찬 상태를 의미하는 것 같다. 근데 그럼 사람들이 기다리기만 하고, 나가지는 않는 상황인 거 같은데,

문제 조건에는 대기가 끝난 이후 사람은 대기실에 자리를 비워줘야 한다고 했다.

(2) A.

내가 코드를 잘못이해 했다

if(makeProc==0 && !QIsEmpty(&que))
    makeProc = Dequeue(&que)

makeProc-- ;

makeProc : 임시 변수 = 현재 작업하고 있는 상황을 제시하는 상황
makeProc-- : for문은 1초에 한 번씩 반복이 되는데, 만드는 상황도 반영하고 있는 것이다.
makeProc이 0 이 된 상황 (= 지금 만들던 거 다 만든 상황) 이 되면
- makeProc에 마지막 값 (= 지금 기다리고 있는 사람의 햄버거 만드는 시간)을 할당하고,
- Delete : que에 할당된 값을 삭제한다.
→ Dequeue(&que) :

⇒ 이 부분 잘못 이해한 이유 : 일단 makeProc 변수에 대한 이해와, 조건문을 잘못 해석했다

(3) Solution

문제에 대한 이해가 부족한 것일까
- 목적성 + 문제 이해 (대기실에 사람 다 넣어놓고, 다 만들고 나면 쫓아낼 것임, ) 이 필요한 것일까 아니면
코드에 대한 이해가 부족한 것일까
- Error가 뜨는 타이밍이 언제임? + makeProc의 의의는 무엇인가

(4) Final Sum

둘 다 문제일 수도 있지만, 코드에 대한 이해가 부족하다고 피드백 해야 조금 더 빠르게 오류를 잡아낼 수 있을 것 같다. 기본적인 코드의 의미를 이해 해야 → 이를 목적에 맞추어 해석하기 용이하기 때문이다.

또한, 코드에 대한 이해가 (= 메뉴얼이 정해져 있는 규칙의 나열에 대한 이해가 )

매번 달라지는 문제 상황을 선 이해 하고 이에 맞추어 코드를 보는 것 보다 효율적일 것이라고 생각한다. 코드가 이해 안되는 경우 문제로 돌아가는 것이 맞지만, 문제 이해부족을 고정된 문제 원인으로 생각하기에는 날리는 비용이 너무 크다.

저작자표시 비영리 변경금지 (새창열림)

'프로그래밍 > Data Structure' 카테고리의 다른 글

10. Sort #2 Complex Sort Algorithm1 (0)	2025.03.10
10. Sort #1 Basic sort Algorithm (0)	2025.03.10
2. Stack #2 Caculator Algorithm1 (1)	2025.01.26
2. Stack #1 ADT && structure (1)	2025.01.25
1. Linked List #1 Array based list (0)	2025.01.24

공대생의 일상에 퐁당

3. Queue

Queue Blog

7-0 Intro

7-1 Queue의 이해와 ADT정의

1) Queue의 이해

2) Queue의 ADT

7-2 Implementing Queue (based on array)

1) 큐 구현 논리

(1) Enqueue

(2) Dequeue

(3) Problems

2) 원형 큐

(1) Enqueue

(2) Dequeue

(3) Issues

3) 원형 큐의 구현

(1) Header File

(2) Final Code

(3) Enqueue

7-3 Implementing Queue (based on linked list)

0) stack과의 차이

(1) stack

(2) Queue

1)Enqueue

2)Dequeue

3) Final Code

7-4 Utilizing Queue

0) Intro

1) Situation

2) 삽질 ON

(1) Q.

(2) A.

(3) Solution

(4) Final Sum

'프로그래밍 > Data Structure' 카테고리의 다른 글

티스토리툴바

3. Queue

Queue Blog

7-0 Intro

7-1 Queue의 이해와 ADT정의

1) Queue의 이해

2) Queue의 ADT

7-2 Implementing Queue (based on array)

1) 큐 구현 논리

(1) Enqueue

(2) Dequeue

(3) Problems

2) 원형 큐

(1) Enqueue

(2) Dequeue

(3) Issues

3) 원형 큐의 구현

(1) Header File

(2) Final Code

(3) Enqueue

7-3 Implementing Queue (based on linked list)

0) stack과의 차이

(1) stack

(2) Queue

1)Enqueue

2)Dequeue

3) Final Code

7-4 Utilizing Queue

0) Intro

1) Situation

2) 삽질 ON

(1) Q.

(2) A.

(3) Solution

(4) Final Sum

'프로그래밍 > Data Structure' 카테고리의 다른 글

관련글

티스토리툴바