자료구조2(큐, 덱)

 

큐

큐는 한쪽 끝을 rear로 정하여 삽입 작업만 이루어지고 반대쪽 끝은 front로 정해 삭제 작업만 이루어진다.

 

큐의 FIFO 구조, 선입선출

 

 

- 순차 자료구조

초기 상태 : front = rear = -1 , 공백 상태 : front = rear , 포화 상태 : rear = n-1

deQueue(Q)
	front <- front + 1;
	return Q[front];

 

- 연결 자료구조

front 위치를 옮긴 후 삭제한다

//c언어 순차 자료구조
typedef char element;

typedef struct QueueType{
	element queue[4];
    int front, rear;
}QueueType;

void enQueue(QueueType *Q, element item){
	Q->rear++;
    Q->queue[Q->rear] = item;
}

element deQueue(QueueType *Q){
	Q->front++;
    return Q->queue[Q->front];
}

 

 

Queue에서 deQueue를 할때 배열에 있는 요소를 삭제하는 것이 아니라 front위치만 변해서 Queue[4];인 경우 E는 삽입할 수 없는 개념을 모르고 구현하려고 해서 매우 헷갈렸다.

 

- 파이썬으로 구현

from collections import deque # queue 라이브러리를 이용하는 것보다 간단하다.

# 큐(Queue) 구현을 위해 collections 모듈에서 제공하는 deque 라이브러리 사용
queue = deque()

# 삽입(5) 삽입(4) 삭제() 삽입(5) 삭제()
queue.append(5)
queue.append(4)
queue.popleft()
queue.append(5)
queue.popleft()

print(queue)
queue.reverse()
print(queue)

# deque 객체를 리스트 자료형으로 변경하고자 한다면 list() 메서드를 이용 list(queue)

 

원형 큐

 

- 순차 자료구조

 

- 연결 자료구조

연결 큐의 구조

 

연결 큐의 초기 상태(공백 큐)는 front와 rear를 NULL 포인터로 설정하여 표현한다.

typedef char element;

typedef struct QNode{
	element data;
    struct QNode* link;
}QNode;

typedef struct{
	QNode* front, * rear;
}LQueueType;

삽입 연산, 새 노드 삽입전 큐가 공백이면 포인터 front,rear이 모두 새 노드를 가리킴

void enLQueue(LQueueType* LQ, element item){// 연결 큐의 rear에 원소를 삽입하는 연산
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
    newNode->data = item;
    newNode->link = NULL;
    if(LQ->front == NULL){
    	LQ->front = newNode;
        LQ->rear = newNode;
    }else{
    	LQ->rear->link = newNode;
        LQ->rear = newNode;
        }
}

삭제 연산

element deLQueue(LQueueType* LQ){ // 연결 큐에서 원소를 삭제하고 반환하는 연산
	QNode* old = LQ->front;
    element item;
    if(isLQEmpty(LQ)) return;
    else{
    	item = old->data;
        LQ->front=LQ->front->link
        if(LQ->front == NULL)
        	LQ->rear = NULL;
        free(old);
        return item;
    }
}

 

덱

Deque(Double - Ended Queue)은 front, rear 에서 삽입 삭제가 모두 가능한 큐

from collections import deque
deque=deque()
print("현재 데크 :",deque)
deque.append(1)         #오른쪽에 1 추가
print("현재 데크 :",deque)
deque.appendleft(2)     #왼쪽에 2 추가
print("현재 데크 :",deque)
deque.popleft()         #첫 번째 원소 제거
print("현재 데크 :",deque)
deque.pop()             #끝 원소 제거
print("현재 데크 :",deque)