자료구조(4) - Queue

자료구조(4) - Queue

Queue

Queue

<개념>

Queue : Stack과 비슷한 구조로 Stack과의 차이점은 아래가 뚫려있는 바구니이다. 그래서 처음 들어간 데이터가 가장 먼저 나오게 되는 First In, Fist Out 의 구조를 띈다

Queue 작동방식

<특징>

FIFO(First In, First Out) 문제에 강함,

빨대나 터널, 출입구와 비슷한 모양으로 지나간 갯수를 셀 때 유용

<구현>

# Stack 기본 메소드

Queue 메소드 설명 return push(x) X원소 데어터 추가 None pop() 가장 처음 넣은 데이터 꺼내기 value peek() pop이 될 데이터 확인 None is_empty 남은 데이터가 있는지 확인 None

구현은 여러가지가 있지만 알고있는 방법들을 나열하자면 3가지 정도 된다.

deque 라이브러리 이용

List이용

LinkedList이용

# Queue구현 - deque 라이브러리 함수 이용

우선 해당 함수를 사용하기 위한 import 필수

from collections import deque

deque 라이브러리

deque 메소드 설명 return append( x) 오른쪽에 x 추가 None appendleft(x) 왼쪽에 x 추가 None clear() deque 초기화 None copy() 복사 None count( x) x와 같은 원소의 수세기 value extend( iterable) iterable 인자에서온 요소를 오른쪽에 추가 None extendleft( iterable) iterable 인자에서 온 요소를 왼족에 추가 None index(x[ A, start[ B , stop]]) x의 위치를 반환

(A : 시작 인덱스, B : 끝 인덱스) value insert( i, x) i 위치에 x 삽입 None pop() 오른쪽 요소를 제거 후 반환 value popleft() 왼족 요소를 제거 후 반환 value remove( value) value의 첫번째 항목을 제거 None reverse() 순서 뒤집기 None rotate( n = 1) N번 회전(끝인덱스를 반대편으로 보내기)

(n ==음수이면 방향 반대) None maxlen 최대 크기 value / None

deque의 라이브러리 중 appendleft(x), pop()이 각각 push, pop의 기능과 동일 하기 때문에 해당 라이브러리를 사용해도 무방하다.

# Queue구현 - list 이용

#Python Code - by list

class Queue: #List를 이용한 Queue 구현 def __init__(self): self.items = [] def push(self, value): self.items.append(value) def pop(self): if self.is_empty(): return 'stack is Empty' #Queue안에 데이터가 없을 경우 return self.items.pop(0) def peek(self): if self.is_empty(): return 'stack is Empty' #Queue안에 데이터가 없을 경우 return self.items[0] def is_empty(self): return len(self.items) == 0

기본 메소드를 적절히 이용하면 구현가능하다!

# Queue구현 - Linkedlist 이용

앞서 진행했던 Stack과는 달리 훨씬더 복잡하게 진행이된다.

이유는 구멍이 하나였던 Stack에서는 하나의 부분만 집중하면 됬지만 Queue의 경우 구멍이 2개이기 때문에

동시에 확인을 해야한다.

우선 앞선 Linked List에 없었던 tail를 추가해야하고

구현 방식은 새로운 데이터를 tail에 넣고 head에서 데이터를 반환하는 방식으로 구현한다.

<구현 과정>

Push(x) : tail에 추가하는 것이 목표

1. 새로운 노드를 만드다

처음 대입할 경우

1-1 head, tail이 새로운 노드라 정하고

ruturn

2. 현재 tail의 next를 새로운 노드와 연결

3. tail을 새로운 노드로 변경

일반적인 push 과정

1-1 Queue에 처음 원소를 집어 넣을 때

pop(), peek(), is_empty()과정은 Stack의 pop과 동일한 방법으로 진행이 된다.

*Queue 가 비였을 경우는 항상 예외를 주어야 한다.

#Python Code - by linkedList

class Node: def __init__(self, data): self.data = data self.next = None class Queue: def __init__(self): self.head = None self.tail = None def enqueue(self, value): new_node = Node(value) if self.is_empty(): # queue가 비였을 경우 head와 tail둘다 없기 때문에 self.tail = new_node # 둘다 동시에 적용해야 한다. self.head = new_node return # return을 하지 않으면 tail.next에 또 같은 값이 들어가고 # tail이 이동되므로 오류 발생 self.tail.next = new_node self.tail = new_node return def dequeue(self): if self.is_empty(): return print("Queue is Empty") delete_node = self.head self.head = delete_node.next delete_node.next = None return delete_node def peek(self): if self.is_empty(): return print("Queue is Empty") return self.head.data def is_empty(self): return self.head is None

from http://zhqmfkv.tistory.com/34 by ccl(A) rewrite - 2021-12-17 20:00:38