✏️ Queue (큐의 개념)
- 먼저 들어간 데이터가 먼저 나오는 FIFO(First In First Out) 혹은 LILI(Last In Last Out)을 특징으로 하는 자료구조다.데이터가 입력된 순서대로 처리되어야할 떄 주로 사용이 된다.
- 정해진 한 곳(top)을 통해서 insert, delete가 이루어지는 stack과 달리 Queue는 한쪽 끝(rear)에서 insert, 다른 쪽 끝(front)에서 delete작업이 이루어진다. rear에서 이뤄지는 삽입연산을 enQueue, front에서 이뤄지는 삭제연산을 dequeue라고 한다.
- 활용처: 프로세스관리, BFS 구현, Cache 구현
✏️ Queue (큐의 사용과 구현)
Python은 queue라이브러리를 제공한다. 하지만 list를 이용해 대부분 구현이 가능하기에 가장 간단한 방법은 범용 자료구조인 list를 사용하는 것이다. append()와 pop(0)을 활용하면 Queue의 enqueue와 dequeue를 사용하는 효과를 낼 수 있다.
1. queue Library 활용
import queue
(1) Queue()
Code:
# Queue() : 일반적으로 사용되는 큐 자료구조이다.
q = queue.Queue()
q.put(10)
q.put(20)
q.put(30)
print(q.qsize())
print(q.get())
print(q.get())
print(q.qsize())
Output:
3
10
20
1
put() : enqueue
get(): dequeue
qsize: queue의 요소개수를 가져온다
(2) PriorityQueue()
: 데이터의 우선순위를 지정해 정렬시키고, 우선순위에 따라 출력하는 자료구조이다.
Code:
# PriorityQueue() : 우선순위 큐
q = queue.PriorityQueue()
q.put((10, "중요한거"))
q.put((0, "엄청중요한거"))
q.put((15, "안중요한거"))
print(q.get()[1])
print(q.get()[1])
print(q.get()[1])
Output:
엄청중요한거
중요한거
안중요한거
우선순위가 지정되지 않는다면 오름차순으로 정렬이되고, 위처럼 (우선순위, 값) 형태의 튜플을 넣어준다면 우선순위에 맞추어 정렬이 된다.
2. List 로 Queue() 구현
Code:
class Queue():
def __init__(self):
self.q = list()
def put(self, x):
self.q.append(x)
def get(self):
return self.q.pop(0)
def qsize(self):
return len(self.q)
q = Queue()
q.put(10)
q.put(20)
q.put(50)
print(q.qsize())
print(q.get())
print(q.get())
print(q.qsize())
Output:
3
10
20
1
✏️ Stack (스택의 개념)
- 데이터를 순서대로 쌓는 자료구조이다.
- LIFO (Last In First Out) 또는 FILO (First In Last Out) 이라고 부른다.
- 입력과 출력이 한방향으로 이루어져 접근이 제한적이다.
✏️ Stack (스택의 사용과 구현)
push() : 데이터를 스택에 쌓는다.
pop() : 데이터를 스택에서 꺼낸다.
1. List 로 구현
class Stack:
def __init__(self):
self.stack = list()
def push(self, x):
self.stack.append(x)
def pop(self):
return self.stack.pop()
stack = Stack()
stack.push(10)
stack.push(30)
stack.push(50)
print(stack.pop())
print(stack.pop())
✏️ Linked List (연결리스트의 개념)
- Array List와 달리 엘리먼트와 엘리먼트 간의 연결(link)를 이용해서 리스트를 구현한 것.
- python의 경우 List 기본 자료형에 linked list 기능이 함께 포함되어 있다.
- array list에서는 엘리먼트라는 이름을 사용하지만 linked list와 같이 연결된 엘리먼트들은 Node 혹은 Vertex라고 부른다.
Node: 데이터의 저장단위로 데이터 값 + 포인터로 구성되어 있다.
Pointer: 각 노드 안에서, 다음이나 이전의 노드의 주소를 가지는 값을 의미한다.
✏️ Linked List (연결리스트의 구현)
1. Node 구현
class Node:
def __init__(self, data):
self.data = data
self.next = None
현재 노드에서 다음 노드를 어떻게 참조시킬까? 아래와 같이 할 수 있을 것.
head = Node(10)
next_node = Node(20)
head.next = next_node
2. 단순 연결 리스트의 구현
- 첫번째 노드 삽입
- 중간 노드 삽입
- 마지막 노드 삽입
- 노드삭제
SLL class 생성
class SLL:
def __init__(self, data):
new_node = Node(data)
self.head = new_node
self.list_size = 1
* 길이를 계산하는 것보다 O(n), 길이를 가지고 있는편 O(1) 이 더 빠르다.
아래 메서드들은 모두 SLL 클래스 내부에서 구현된다.
첫번째 노드 삽입
def insertFirst(self, data):
new_node = Node(data)
temp_node = self.head
self.head = new_node
self.head.next = temp_node
self.list_size += 1
헤더를 교체한다.
노드 선택
다른 메서드의 작업 간단화를 위한 메서드. 인덱스 번호로 노드를 선택한다.
def selectNode(self, num):
if self.list_size < num:
return
node = self.head
count = 0
while count < num:
node = node.next
count += 1
return node
마지막 노드 삽입
def insertLast(self, data):
node = self.head
while True:
if node.next == None:
break
node = node.next
new_node = Node(data)
node.next = new_node
self.list_size += 1
중간 노드 삽입
def insertMiddle(self, num, data):
if self.head.next == None:
insertLast(data)
return
node = self.selectNode(num)
new_node = Node(data)
temp_next = node.next
node.next = new_node
new_node.next = temp_next
self.list_size += 1
헤드노드 삭제
def deleteHead(self):
node = self.head
self.head = node.next
del node
노드 삭제
def deleteNode(self, num):
if self.list_size < 1:
return
elif self.list_size < num:
return
if num == 0:
self.deleteHead()
return
node = self.selectNode(num-1)
node.next = node.next.next
del_node = node.next
del del_node
'프로그래밍 > 자료구조 & 알고리즘' 카테고리의 다른 글
[알고리즘] Lower Bound와 Upper Bound (1) | 2022.02.02 |
---|---|
Binary Search (이진탐색) 알고리즘 (0) | 2022.02.01 |
[Python & Algorithm] Dynamic Programming(동적프로그래밍) (0) | 2022.01.22 |
[Python & Data Structure] Graph (0) | 2021.11.04 |
[Python & Data Structure] Tree (0) | 2021.11.02 |