# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # Data Structure
#
# ## 자료구조의 정의 및 종류
#
# 자료구조를 물리적으로 구현하는 방법
# * List
# * Linked list
#
# 이를 이용하여 구현된 자료구조의 종류
#
# * List
# * Linked list
#
# 아래는 **List**, **Linked list** 로 구현이 가능하고,
# * Array
# * Stack
# * Queue
# * Tree
# * Heap
# * Graph
# 데크는 **List** 로 구현이 가능하다.
# * Deque
#
# ## 자료구조의 분류
#
# 자료구조
#  * 단순구조
#   - 2진수, 정수, 실수, 문자, 문자열 --> 배열, 구조체, 클래스 등 사용자 정의 자료형으로 사용
#  * 선형구조
#   _ 리스트
#   - 연결 리스트 --> 단순 연결, 이중 연결, 원형 연결 리스트
#   - 데크
#   - 스택
#   - 큐
#  * 비선형구조
#   - 트리 --> 일반 트리, 이진 트리
#   - 그래프 --> 방향 그래프, 무방향 그래프
#  * 파일구조
#   - 순차파일
#   - 색인파일
#   - 직접파일

# ## 자료구조의 구현

# ### List 형 자료구조
# * 배열: 크기가 변하지 않음, 중간 값이 지워져도 크기가 일정
# * 리스트: 크기가 변함, 중간 값이 지워지면 뒤에 값이 앞으로 이동

# #### Python example
# List 를 생성하고 삭제, 출력 예시

# +
# Python List
sales_results = [12, 45, 67, 43, 56, 98]

for s in sales_results:
    print ( "The sales result = %d" % ( s ) )
    
print ( " delete:", sales_results[3])
del sales_results[3]

for s in sales_results:
    print ( "The sales result = %d" % ( s ) )

# -

# ### 연결 리스트 자료구조
# * 연결 리스트
# * 더블 연결 리스트
# * 환형 연결 리스트
#
# 연결리스트는 데이터 사이의 관계를 이용하기 때문에
# * 데이터의 중간 삽입과 삭제가 용이
# * 데이터를 서치하기는 불편

# #### Python example
# Node class 를 선언하고 이를 이용해
# 1. 연결 리스트를 생성하고,
# * 데이터를 삭제,
# * 데이터를 삽입,
# * 최종 결과를 출력 한다.
#

# +
# Python Linked List

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = None # 다음 data


# +
# 1. 연결리스트 생성

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node1.next = node2
node2.next = node3
node3.next = node4

# +
# 2. 구성된 리스트에서 데이터 2 를 지우고 나머지를 연결

del_data = 2

pre_node = node1
next_node = pre_node.next

if pre_node.data == del_data:
    node1 = next_node
    del pre_node
    
while next_node:
    if next_node.data == del_data:
        pre_node.next = next_node.next
        del next_node
        break
    pre_node = next_node
    next_node = next_node.next
# -

# 3. 구성된 리스트에서 데이터 9 를 삽입
new_node = Node(9)
new_node.next = node1
node1 = new_node

# 4. 결과 출력
node = node1
while node:
    print( node.data )
    node = node.next


# ### 연결리스트를 이용한 스택 구현
# #### Python example
# Link class 를 선언하고 이를 이용해 스택을 구현

# +
# Link class
class Link:
    def __init__(self, d1=None, d2=None):
        self.data1 = d1
        self.data2 = d2
        self.next_link = None

    def printLink(self):
        print ( "{", self.data1, ", ", self.data2, "}")

# LinkList class
class LinkList:
    def __init__(self):
        self.first_link = None
    
    def isEmpty(self):
        return self.first_link == None

    def insert(self, d1, d2):
        if self.first_link == None : 
            self.first_link = Link( d1, d2 )
        else:
            tmp_next_link = self.first_link
            self.first_link = Link( d1, d2 )
            # first_link 의 next_link 초기화됨
            self.first_link.next_link = tmp_next_link
      
    def delete(self):
        rlink = self.first_link
        self.first_link = self.first_link.next_link
        return rlink

    def printList(self):
        curLink = self.first_link
        print ( "Link list" )
        while(curLink != None):
            curLink.printLink()
            curLink = curLink.next_link

def test():
    link_list = LinkList()
    link_list.insert( 1, 100 )
    link_list.insert( 2, 200 )
    link_list.insert( 3, 300 )
    link_list.insert( 4, 400 )
    link_list.insert( 5, 500 )
  
    link_list.printList()

    while( not link_list.isEmpty() ):
        deletedLink = link_list.delete()
        print ( "delete" )
        deletedLink.printLink()
      
    link_list.printList()

test()
# -

# ### 해쉬테이블
# * [참고자료](https://hsp1116.tistory.com/35)
#  - 설명, 코드 추가하기

# ## 순서리스트 자료구조
#
# ## 배열 자료구조
#
#

# ## 스택 자료구조
# * Last In First Out(LIFO)
# * PUSH: 데이터를 넣는 것
# * POP: 데이터를 꺼내는 것

# +
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)

print( "Stack:" )
print( stack)

while stack:
    print( "POP Value is ", stack.pop() )
# -

# ## 큐 자료구조
# * First In First Out(FIFO)

# +
queue = []
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
queue.append(5)

print( "Queue:" )
print( queue )

while queue:
    print( "Get Value: ", queue.pop(0) )
# -

# ## 데크 자료구조
#
# ## 트리 자료구조
#
# ## 이진 트리
#
# ## 힙
#
# ## 그래프 자료구조
#

StarcoderdataJupyterScriptsDedupFiltered