자료구조(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에 처음 원소를 집어 넣을 때&amp;amp;nbsp;

 

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

 

---