자료구조 09 : 큐

LeeWonjin·2022년 6월 15일
자료구조학부
0

[학부]자료구조/알고리즘

목록 보기
9/18

개요

선입선출(FIFO)순서에 따라 삽입 삭제가 일어나는 ADT
삽입은 뒤(Rear)에서, 삭제는 앞(Front)에서 수행

메소드

  • enqueue(e) : rear에 원소 삽입
  • element dequeue() : front쪽 원소 삭제 후 반환
  • element front() : front쪽 원소 반환
  • int size() : 원소 개수
  • bool isEmpty()
  • iterator elements() : 전체 원소 반환

예외

  • emptyQueueException() : 비어있는 큐에 dequeue시도
  • fullQueueException() : 꽉찬 큐에 enqueue시도 (구현방법에 따른 제약사항)

큐 구현

원형배열 기반

  • 구성요소
    • Q : 크기 N인 1차원 배열
    • f : front원소 인덱스
    • r : rear원소 인덱스
  • 아이디어
    • full, empty상태 구분을 위해 원소 하나는 비워둔다. (즉, 크기 N인 배열의 경우 N-1개 원소만 삽입가능) ---> 굳이 N개공간 다 쓰고싶으면, 큐 크기를 저장하는 변수를 관리하면 됨.
    • 초기화할 때 r다음 f가 오도록 설정 (r=0 f=1 / r=N-1 f=0 / r=N-2 f=N-1 등)
  • 의사코드
    : 공간복잡도 O(n), 시간복잡도 O(1)
Alg init()
1. f ← 0
   r ← N-1
2. return

Alg isEmpty()
1. return (r + 1) % N = f

Alg isFull()
1. return (r + 2) % N = f

Alg enqueue(e)
1. if(isFull())
     fullQueueException()
2. r ← (r + 1) % N
   Q[r] ← e
3. return

Alg dequeue()
1. if(isEmpty())
     emptyQueueException()
2. removedElem ← Q[f]
   f ← (r + 1) % N
3. return removedElem

Alg size()
1. return (N - f + r + 1) % N
  • C언어
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 100

int Q[N];
int f = 0;
int r = N - 1;

bool isEmpty() {
	return (r + 1) % N == f;
}

bool isFull() {
	return (r + 2) % N == f;
}

int size() {
	return (N + r - f + 1) % N;
}
void enqueue(int elem) {
	if (isFull())
		return;
	
	r = (r + 1) % N;
	Q[r] = elem;
}

int dequeue() {
	if (isEmpty())
		return NULL;

	int e = Q[f];
	f = (f + 1) % N;
	return e;
}

int main() {
	enqueue(1); enqueue(2); enqueue(3);
	int a, b, c;
	a = dequeue(); b = dequeue(); c = dequeue();
	printf("%d %d %d", a, b, c); // 1 2 3
	return 0;
}

연결리스트 기반

  • 구성요소
    • 단일연결리스트 Q
    • head를 가리키는 포인터 f, tail을 가리키는 포인터 r
  • 의사코드
Alg init()
1. f ← NULL
   r ← NULL
2. return

Alg enqueue()
1. p ← getNode()
   p.elem ← e
   p.next ← NULL
2. if(isEmpty())
     f ← p
     r ← p
   else
     r.next ← p
     r ← p
3. return

Alg dequeue(e)
1. if(isEmpty())
     emptyQueueException()
2. q ← f
   removedElem ← q.elem
   f ← f.next
   putNode(q)
3. if(f = NULL)
     r ← NULL
4. return removedElem
  • C언어
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct _Node {
	struct _Node* next;
	int elem;
} Node;

typedef struct _Queue {
	Node* f;
	Node* r;
} Queue;

void enqueue(Queue* Q, int elem) {
	Node* p = (Node*)malloc(sizeof(Node));
	p->next = NULL;
	p->elem = elem;

	if (Q->r == NULL)
		Q->f = p; 
	else 
		(Q->r)->next = p;

	Q->r = p;
}

int dequeue(Queue* Q) {
	Node* q = Q->f;
	int e = q->elem;

	Q->f = (Q->f)->next;
	free(q);

	if (Q->f == NULL)
		Q->r = NULL;

	return e;
}

int main() {
	Queue* Q = (Queue*)malloc(sizeof(Queue));
	Q->f = NULL;
	Q->r = NULL;

	enqueue(Q, 1); enqueue(Q, 2); enqueue(Q, 3);
	int a, b, c;
	a = dequeue(Q); b = dequeue(Q); c = dequeue(Q);
	printf("%d %d %d", a, b, c); // 1 2 3
	return 0;
}

스택 기반

  • 구성요소
    • enqueue가 발생하는 스택 S1
    • dequeue가 발생하는 스택 S2
  • 의사코드
    • 시간복잡도 enqueue O(1)
    • 공간복잡도(상각실행시간) dequeue O(1)
Alg init()
1. S1 ← empty stack
   S2 ← empty stack
2. return

Alg enqueue(e)
1. S1.push(e)
2. return

Alg dequeue()
1. if(S1.isEmpty() & S2.isEmpty())
     emptyQueueException()
2. if(S2.isEmpty())
     while(!S1.isEmpty())
       tmp ← S1.pop()
       S2.push(tmp)
     e ← S2.pop()
     return e
   else
     e ← S2.pop()
     return e
  • C언어
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct _Stack {
	int arr[10];
	int top;
} Stack;

void push(Stack* s, int elem) {
	if (s->top == 9)
		return;

	(s->top)++;
	(s->arr)[s->top] = elem;
}

int pop(Stack* s) {
	if (s->top == -1)
		return NULL;

	(s->top)--;
	return (s->arr)[(s->top) + 1];
}

// -------

void enqueue(Stack* S1, Stack* S2, int elem) {
	if (S1->top == 9)
		return; // full exception

	push(S1, elem);
}

int dequeue(Stack* S1, Stack* S2) {
	if (S1->top == -1 && S2->top == -1)
		return NULL; // empty exception

	if (S2->top == -1) {
		while (S1->top != -1) {
			int e = pop(S1);
			push(S2, e);
		}
	}
	
	return pop(S2);
}

void print(Stack* S1, Stack* S2) {
	for (int i = S2->top; i >= 0; i--)
		printf("%d ", (S2->arr)[i]);

	for (int i = 0; i <= S1->top; i++)
		printf("%d ", (S1->arr)[i]);

	printf("\n");
}

int main() {
	Stack* S1 = (Stack*)malloc(sizeof(Stack));
	S1->top = -1;
	Stack* S2 = (Stack*)malloc(sizeof(Stack));
	S2->top = -1;

	enqueue(S1, S2, 1); enqueue(S1, S2, 2); enqueue(S1, S2, 3);
	print(S1, S2); // 1 2 3

	dequeue(S1, S2); dequeue(S1, S2);
	print(S1, S2); // 3

	dequeue(S1, S2);
	enqueue(S1, S2, 15); enqueue(S1, S2, 20);
	dequeue(S1, S2);
	print(S1, S2); // 20

	return 0;
}

합동큐 (큐 기반 스택구현)

  • 구성요소
    • 큐 Q1, Q2
  • 의사코드
    • push 시간복잡도 O(1)
    • pop 시간복잡도 O(n)
Alg init()
1. Q1 ← empty queue
   Q2 ← empty queue
2. return

Alg push(e)
1. Q1.enqueue(e)
2. return

Alg pop()
1. if(Q1.isEmpty() & Q2.isEmpty())
     emptyQueueException()
2. while(Q1.size() > 1)     { N개원소 중 N-1개 Q2로 보냄 }
     tmp ← Q1.dequeue()
     Q2.enqueue(tmp)
3. e ← Q1.dequeue()        { Q1에 마지막남은 하나 삭제후 반환 }
4. while(!Q2.isEmpty())    { 삭제한거 빼고 원상복구 }
     tmp ← Q2.dequeue()
     Q1.enqueue(tmp)
5. return e
  • C언어
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct _Node {
	struct _Node* next;
	int elem;
} Node;

typedef struct _Queue {
	Node* f;
	Node* r;
	int size;
} Queue;

void enqueue(Queue* Q, int elem) {
	Node* p = (Node*)malloc(sizeof(Node));
	p->next = NULL;
	p->elem = elem;

	if (Q->r == NULL)
		Q->f = p;
	else
		(Q->r)->next = p;

	Q->r = p;
	(Q->size)++;
}

int dequeue(Queue* Q) {
	Node* q = Q->f;
	int e = q->elem;

	Q->f = (Q->f)->next;
	free(q);

	if (Q->f == NULL)
		Q->r = NULL;
	(Q->size)--;
	return e;
}


// -----------------

void push(Queue* Q1, Queue* Q2, int elem) {
	enqueue(Q1, elem);
}

int pop(Queue* Q1, Queue* Q2) {
	if (Q1->f == NULL && Q2->f == NULL) {
		return NULL; // empty exception
	}

	while (Q1->size > 1) {
		int x = dequeue(Q1);
		enqueue(Q2, x);
	}
	int e = dequeue(Q1);

	while (Q2->f != NULL) {
		int x = dequeue(Q2);
		enqueue(Q1, x);
	}

	return e;
}

void print(Queue* Q1) {
	Node* p = Q1->f;
	while (p != NULL) {
		printf("%d ", p->elem);
		p = p->next;
	}
	printf("\n");
}

int main() {
	Queue* Q1 = (Queue*)malloc(sizeof(Queue));
	Q1->f = NULL;
	Q1->r = NULL;
	Q1->size = 0;
	Queue* Q2 = (Queue*)malloc(sizeof(Queue));
	Q2->f = NULL;
	Q2->r = NULL;
	Q2->size = 0;

	push(Q1, Q2, 1); push(Q1, Q2, 2); push(Q1, Q2, 3);
	print(Q1); // 1 2 3

	pop(Q1, Q2); pop(Q1, Q2);
	print(Q1); // 1

	return 0;
}

데크 ADT

스택과 큐의 합체방식으로 작동하는 ADT
삽입/삭제가 front, rear에서 모두 발생

front에서 삽입=push, 삭제=pop
rear에서 삽입=inject, 삭제=eject

메소드

  • push(e)
  • element pop()
  • inject(e)
  • element eject()
  • element front()
  • element rear()
  • int size()
  • bool isEmpty()

예외

  • emptyDequeException()
  • fullDequeException()

데크 구현

원형배열 기반

원형배열 기반 큐 구현과 동일함. 삽입/삭제 동작방식과 이름만 다름.

  • 구성요소
    • 크기 N의 원형배열 V
    • front인덱스 f, rear인덱스 r
  • 의사코드
Alg init()
1. V ← empty 1D array
   f ← 0
   r ← N-1
2. return

Alg push(e)
1. if((r + 2) % N = f)
     fullDequeException()
2. f ← (f - 1) % N
   V[f] ← e
3. return

Alg pop()
1. if((r + 1) % N = f)
     emptyDequeException()
2. e ← V[f]
3. f ← (f + 1) % N
4. return

Alg inject(e)
1. if((r + 2) % N = f)
     fullDequeException()
2. r ← (r + 1) % N
   V[r] ← e
3. return

Alg eject()
1. if((r + 1) % N = f)
     emptyDequeException()
2. e ← V[r]
3. r ← (r - 1) % N
4. return e
  • C언어
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

#define N 100
int Deque[N];
int f = 0;
int r = N - 1;

void push(int elem) {
	f = (f - 1) % N;
	Deque[f] = elem;
}

int pop() {
	int e = Deque[f];
	f = (f + 1) % N;
	return e;
}

void inject(int elem) {
	r = (r + 1) % N;
	Deque[r] = elem;
}

int eject() {
	int e = Deque[r];
	r = (r - 1) % N;
	return e;
}

void print() {
	int size = (N + r - f + 1) % N;
	int p = f;

	for (int i = 0; i < size; i++) {
		int idx = (f + i) % N;
		printf("%d ", Deque[idx]);
	}
	printf("\n");
}

int main() {
	push(1); push(2); push(3);
	inject(10); inject(20); inject(30);
	print(); // 3 2 1 10 20 30

	int a, b, c, d;
	a = pop(); b = pop();
	c = eject(); d = eject();
	printf("pop : %d %d %d %d\n", a, b, c, d); // pop : 3 2 30 20

	print(); // 1 10

	return 0;
}

이중연결리스트 기반

  • 구성요소
    • 이중연결리스트 L
    • head포인터 f, tail포인터 r
  • 의사코드
Alg init()
1. f ← NULL
   r ← NULL
2. return

Alg push(e)
1. p ← getNode()
   p.elem ← e
   p.prev ← NULL
   p.next ← f
2. if(f == NULL)
     f = p
     r = p
   else
     f.prev = p
     f = p
3. return

Alg pop()
1. if(isEmpty())
     emptyDequeException()
2. q ← f
   e ← q.elem
3. f ← f.next
4. putNode(q)
6. if(f = NULL)
     r ← NULL
5. return e

Alg inject(e)
1. p ← getNode()
   p.elem ← e
   p.prev ← r
   p.next ← NULL
2. if(r==NULL)
     f = p
     r = p
   else
     r.next = p
     r = p
3. return

Alg eject()
1. if(isEmpty())
     emptyDequeException()
2. q ← r
   e ← q.elem
3. r ← r.prev
4. putNode(q)
5. if(r = NULL)
     f ← NULL
6. return e
  • C언어
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct _Node {
	struct _Node* next;
	struct _Node* prev;
	int elem;
} Node;

typedef struct _Queue {
	Node* f;
	Node* r;
} Queue;

void push(Queue* Q, int elem) {
	Node* p = (Node*)malloc(sizeof(Node));
	p->elem = elem;
	p->prev = NULL;
	p->next = Q->f;
	
	if (Q->f == NULL) {
		Q->f = p;
		Q->r = p;
	}
	else {
		(Q->f)->prev = p;
		Q->f = p;
	}
	
}

int pop(Queue* Q) {
	Node* q = Q->f;
	int e = q->elem;
	Q->f = q->next;
	(Q->f)->prev = NULL;
	free(q);

	if (Q->f == NULL)
		Q->r = NULL;
	
	return e;
}

void inject(Queue* Q, int elem) {
	Node* p = (Node*)malloc(sizeof(Node));
	p->elem = elem;
	p->prev = Q->r;
	p->next = NULL;
	
	if (Q->r == NULL) {
		Q->f = p;
		Q->r = p;
	}
	else {
		(Q->r)->next = p;
		Q->r = p;
	}
}

int eject(Queue* Q) {
	Node* q = Q->r;
	int e = q->elem;
	Q->r = q->prev;
	(Q->r)->next = NULL;
	free(q);

	if (Q->r == NULL) 
		Q->f = NULL;

	return e;
}

void print(Queue* Q) {
	Node* p = Q->f;
	while (p != NULL) {
		printf("%d ", p->elem);
		p = p->next;
	}
	printf("\n");
}

int main() {
	Queue* Q = (Queue*)malloc(sizeof(Queue));
	Q->f = NULL;
	Q->r = NULL;

	push(Q, 1); push(Q, 2); push(Q, 3);
	inject(Q, 10); inject(Q, 20); inject(Q, 30);
	print(Q); // 3 2 1 10 20 30

	int a, b, c, d;
	a = pop(Q); b = pop(Q);
	c = eject(Q); d = eject(Q);
	printf("pop : %d %d %d %d\n", a, b, c, d); // pop : 3 2 30 20

	print(Q); // 1 10
		
	return 0;
}
profile
LeeWonjin
노는게 제일 좋습니다.
이전 포스트

자료구조 08 : 스택 ADT

다음 포스트

자료구조 10 : 트리 ADT

0개의 댓글