class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
기본적인 연결리스트의 객체선언부이고 Node의 data는 실제 우리가 담고자하는 데이터를 할당하게되고 next는 다음 노드의 주소값을 가진다.
Node Management 클래스 구현
class NodeMgmt:
def __init__(self, data):
if self.head == None:
self.head = Node(data)
최초로 링크드리스트가 선언되면 링크드리스트의 정보를 가지는 Management를 만들어준다. 이후 삽입 삭제 검색 출력 함수등이 Management클래스에 속하게된다.
데이터 추가(add) 함수 구현
def add(self, data):
if self.head == None: # head에 데이터가 존재하지 않으면 바로 추가해주는 예외처리
self.head = Node(data)
else:
node = self.head
while node.next:
node = node.next
node.next = Node(data)
기본적으로 add함수는 연속적으로 데이터를 저장하기 때문에 while문을 이용하여 node의 가장 마지막 위치를 찾는다.
node.next가 존재하지 않으면 반복문을 빠져나온다. 반복문을 빠져나옴과 동시에 node.next에 새로 생성되는 Node의 주소값을 넣어줌으로 기존 링크드리스트와 연결시켜준다.
Insert 함수 구현
def insert(self, data, is_data):
if self.head == None:
self.head = Node(data)
return True
else:
node = self.head
while node.data != is_data:
node = node.next
if node == None:
return False
new = Node(data)
new.next = node.next
node.next = new
return True
Insert함수는 기본적으로 search의 기능을 가지고있다. 데이터를 중간에 삽입하기위해선 앞이든 뒤든 데이터를 알고있어야 삽입이 가능하기 때문에 반복문을 이용하여 입력받은 is_data가 링크드리스트내에 존재하는지 확인을 하고 존재 한다면 반복문을 빠져나와 데이터를 삽입하게 된다.
● 메모리의 스택 영역은 함수의 호출과 관계되는 지역번수, 매개변수, 리턴값 등의 임시데이터를 저장한다.
스택의 구조
● 스택은 LIFO(Last In, First Out 후입선출)구조의 데이터 관리 방식을 따른다.
- LIFO: 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책
- FILO: 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책
● 데이터를 제한적으로 접근할 수 있는 구조
- 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
● 스택의 주요 기능
- push(): 데이터를 스택에 넣음
- pop(): 데이터를 스택에서 추출
위 그림에서 2를 push하게 되면 스택에 쌓이게 되고 그림의 흐름처럼 3, 4, 5, 6이 차례대로 스택에 쌓이게 된다.
이후 pop을 하면 쌓였던 데이터중에 가장 나중에 쌓인 6이 가장 먼저 추출이 되고 계속 추출을 하면 가장위에 있는 데이터가 추출되게 된다.
스택의 장점
● 구조가 단순해서 구현이 쉽다.
● 데이터 저장/읽기 속도가 빠르다.
스택의 단점
● 데이터 최대 갯수를 미리 정해야 한다.
● 저장 공간의 낭비가 발생할 수 있다.(미리 최대 갯수만큼 공간을 확보해야함)
파이썬 리스트기능에서 제공하는 메서드로 스택 구현
list_stack = list()
list_stack.append(1) #리시트에 append메소드를 이용해 데이터를 쌓는다.
list_stack.append(2)
list_stack.pop() #가장 마지막에 입력된 2가 추출된다.
파이썬으로 push, pop함수 구현하기
list_stack = list() #리스트 선언
def push(data):
list_stack.append(data) #push에 데이터를 입력받아 스택에 쌓아준다.
def pop():
data = list_stack[-1] #후입선출구조이기 때문에 마지막데이터를 data변수에 입력해준다.
del list_stack[-1] #리스트의 마지막데이터를 삭제해준다.
return data #마지막으로 저장한 데이터를 리턴해줘서 사용자에게 어떤수가 사라졌는지 보여준다.
for i in range(10):
push(i) #0~9까지 수를 스택에 쌓아준다.
pop() #마지막으로 쌓인 9가 추출된다.
● queue라이브러리에는 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue()를 제공한다.
- Queue(): 가장 일반적인 큐 자료구조
import queue
d_queue = queue.Queue() # d_queue를 Queue()를 통해 기본큐로 선언
d_queue.put('hello') #put을 이용하여 d_queue에 데이터 추가
d_queue.put(10)
d_queue.get() #get을 이용하여 데이터를 가져온다. 여기서 나오는 출력문은 hello가 된다.
- LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조(스택구조와 같음)
import queue
d_queue = queue.LifoQueue() #LifoQueue를 통해 LIFO큐를 선언
d_queue.put('hello') #Queue함수로 선언한것과 동일하게 put으로 데이터 삽입
d_queue.put(30)
d_queue.get() #FIFO와 반대로 LIFO는 마지막으로 들어간 데이터가 먼저나오기때문에 출력문은 30
- PriorityQueue(): 데이터마다 우선순위를 부여하여 우선순위가 높은 순서대로 데이터를 출력한다.
import queue
d_queue = queue.PriorityQueue()
d_queue.put((3, 'hello')) #PriorityQueue는 튜플로입력받고 첫번째에는 우선순위 두번째에 데이터를 입력한다.
d_queue.put((5, 100))
d_queue.put((15, 'world'))
d_queue.get() #우선순위가 가장 낮은수를 출력하기 때문에 출력문은 (3, 'hello')가 된다.
파이썬 라이브러리를 사용하지않고 enqueue, dequeue구현
list_q = [] #리스트 선언
def enqueue(data):
list_q.append(data) #추가하고싶은 데이터를 입력하면 리스트에 추가
def dequeue():
data = list_q[0] #리스트의 0번째 데이터를 data에 대입
del list_q[0] #리스트의 0번째 데이터를 삭제
return data #data를 리턴해줌으로 삭제된 데이터를 보여준다.
