공부하자 동진아

링크드 리스트 구조

  - 연결 리스트라고도 함

  - 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조

  - 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조

  - 링크드 리스트 기본 구조와 용어

      • 노드(Node) : 데이터 저장 단위 (데이터 값, 포인터)로 구성, 하나의 데이터

      • 포인터(pointer) : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

링크드 리스트의 장단점

  - 장점

      • 미리 데이터 공간을 할당하지 않아도 된다. (배열은 미리 데이터 공간을 할당)

  - 단점

      • 연결을 위한 별도 데이터 공간이 필요하므로, 저장 공간 효율이 높지 않다.

      • 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느리다.

      • 중간 데이터 삭제 시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업이 필요하다.

파이썬 객체지향 프로그래밍으로 링크드 리스트 구현 : 노드 생성, 추가, 삭제, 검색

class Node:		# 노드 생성
	def __init__(self, data):
		self.data = data
		self.next = None

class NodeMgmt:
	def __init__(self, data):		# 맨 앞에 값을 지정
		self.head = Node(data)

	def add(self, data):			# 데이터 추가
		if self.head == '':
			self.head = Node(data)
		else:
			node = self.head
			while node.next:
				node = node.next
			node.next = Node(data)	# 노드 연결

	def desc(self):					# 해당 전체 링크드 리스트 출력
		node = self.head
		while node:
			print(node.data)
			node = node.next

	def delete(self, data):			# 데이터 삭제
		if self.head =='':
			print('해당 값을 가진 노드가 없습니다.')
			return
            
		if self.head.data == data:	# head 삭제
			temp = self.head
			self.head = self.head.next
			del temp
		else:
			node = self.head
			while node.next:		# head가 아닌 노드 삭제
				if node.next.data == data:
					temp = node.next
					node.next = node.next.next
					del temp
					return
				else:
					node = node.next

	def search_node(self, data):	# 노드 삭제
		node = self.head
		while node:
			if node.data == data:
				return node
			else:
				node = node.next

스택

  - 데이터를 제한적으로 접근할 수 있는 구조

      • 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조

  - 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조

      • 큐 : FIFO 정책

      • 스택 : LIFO 정책

스택 구조

  - 스택은 LIFO(Last In, First Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따름

      • LIFO : 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책

      • FILO : 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책

  - 대표적인 스택의 활용

      • 컴퓨터 내부의 프로세스 구조의 함수 동작 방식

  - 주요 기능

      • push() : 데이터를 스택에 넣기

      • pop() : 데이터를 스택에서 꺼내기

스택 구조와 프로세스 스택

  - 장점

      • 구조가 단순해서, 구현이 쉽다.

      • 데이터 저장/읽기 속도가 빠르다.

  - 단점

      • 데이터 최대 개수를 미리 정해야 한다.

      • 저장 공간의 낭비가 발생할 수 있음

파이썬 리스트 기능에서 제공하는 메서드로 스택 사용해보기

  - append(push), pop 메서드 제공

data_stack = list()

data_stack.append(1)
data_stack.append(2)

print(data_stack)		# [1, 2]
print(data_stack.pop())	# 2

  - pop(), push() 기능 구현해보기

stack_list = list()

def push(data):
	stack_list.append(data)

def pop():
	data = stack_list[-1]
	del stack_list[-1]
	return data

for index in range(10):
	push(index)

print(pop())	# 9

큐 구조

  - 줄은 서는 행위와 유사

  - 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조, '선입선출' 구조의 자료구조

  - FIFO(First In, First Out) 방식으로 스택과 꺼내는 순서가 반대

알아둘 용어

  - Enqueue : 큐에서 데이터를 넣는 기능

  - Dequeue : 큐에서 데이터를 꺼내는 기능

파이썬 queue 라이브러리 활용해서 큐 자료 구조 사용하기

  - queue 라이브러리에는 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue() 제공

      • Queue() : 가장 일반적인 큐 자료 구조

      • LifoQueue() : 나중에 입력된 데이터가 먼저 출력되는 구조 (스택구조)

      • PriorityQueue() : 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력

        PriorityQueue((우선순위, 데이터))

참고 : 어디에 큐가 많이 쓰일까?

  - 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용됨 (운영체제 참조)

파이썬을 활용한 Queue(), LifoQueue(), PriorityQueue() 구현

  - Queue()

import queue

data_queue = queue.Queue	# queue 라이브러리에 있는 Queue 사용

data_queue.put('dongjin')
data_queue.put(1)

print(data.queue.qsize())	# 2
print(data.queue.get())		# 'dongjin'
print(data.queue.qsize())	# 1

  - LifoQueue()

import queue

data_queue = queue.LifoQueue	# queue 라이브러리에 있는 LifoQueue 사용

data_queue.put('dongjin')
data_queue.put(1)

print(data.queue.qsize())	# 2
print(data.queue.get())		# 1

  - PriorityQueue()

import queue

data_queue = queue.PriorityQueue	# queue 라이브러리에 있는 PriorityQueue 사용

data_queue.put((10, 'dongjin'))
data_queue.put((5, 1))
data_queue.put((12, 'korea'))

print(data.queue.qsize())	# 3
print(data.queue.get())		# (5, 1)
print(data.queue.get())		# (10, 'dongjin')

리스트 변수로 큐를 다루는 enqueue, dequeue 기능 구현

queue_list = list()

def enqueue(data):
	queue_list.append(data)
    
def dequeue():
	data = queue_lsit[0]
	del queue_list[0]
	return data
    
for index in range(10):
	enqueue(index)
    
print(len(queue_lsit))		# 10
print(dequeue())		# 0