[Computer Science] 자료구조 - ADT(추상자료형) / linked-list/ Stack / Queue !!!

ADT(Abstract Data Type)

ADT는 추상적으로 필요한 기능을 나열한 일종의 명세서(로직)이다.

• ADT는 기본자료형(대표적으로 리스트, 숫자, 문자열)을 활용하여 사용자에 의해 구현된다.

 

파이썬의 리스트와 자료구조의 리스트.

• 파이썬은 리스트 자료형이 자료구조의 연결리스트로 기능을 지원한다.
• 리스트는 임의의 메모리(위치)에 자료를 동적으로 처리할 수 있다.
• 파이썬의 리스트는 자료구조의 배열과 연결리스트의 특징을 모두 갖고 있다.
  • 배열의 특징 : 인덱스 사용하여 노드에 접근가능
  • 연결리스트의 특징 : 인덱스 크기를 자유롭게 확장가능, 서로 다른 자료형을 노드로 갖을 수 있다.
  • 즉, 파이썬이라는 프로그래밍 언어는 기존 프로그래밍에서 발생한 어려운 점을 부분적으로 개선시켰다는 것을 알 수 있다.

• 

 

파이썬의 리스트

• 자료구조의 기본은 배열(고정된 길이)이라 할 수 있고, 파이썬에서는 리스트와 튜플로 구현할 수 있다.
• 리스트나 튜플의 핵심은 인덱스를 사용하는 것이다.
• 파이썬의 리스트는 자료구조와 알고리즘에서 가장 많이 볼 수 있는 활용법이므로 자주 보면서 익숙해지자.

 

linked-list(연결리스트)

별도의 인덱스를 지정할 필요없이 리스트들이 연결되는 구조로, 연결은 프로그래밍에서 참조의 기능으로 구현되고 '위치바꾸기'라고 생각해도됨. 리스트의 길이를 별도로 지정해줄 필요없다.

• 각 노드는 연결리스트의 다음 노드에 대해 참조(또는 '포인터')를 한다.
  • 참조기호 : . 으로 지칭
  • 삽입, 할당기호 : = 로 표현
• 연결리스트도 리스트의 메소드와 같은 기능들을 구현할 수 있다.
  • 삽입
  • 삭제
  • 검색
• 노드간의 '동적'이라는 개념을 컴퓨터 프로그래밍에서는 '연결'이라는 개념으로 접목시켰다.
  • 연결하면서 값의 위치가 바뀌고 위치가 바뀌면 값도 바뀌는 것이다.
  • 위의 소스코드와 같은 경우는 주소의 위치를 바꿔주면서 '교체'를 해준다.
• 기존방식이었던 인덱스를 통해 함수로 삽입/삭제/검색이 가능했었지만, 연결리스트는 인덱스의 기능을 할 수 있도록 노드별로 위치를 변경해줘야하는 다른 점이 있다.

 

Stack(스택)

선입후출(FILO)의 자료구조 = 입구와 출고가 동일한 형태로 시각화 할 수 있음

리스트를 활용하여 동적 메소드. 

stack의 기본 구조 소스코드 예제

stack = []

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5) # 스택은 append 모듈로 쌓아준다.
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()       # 스택은 pop을 사용하여 마지막 삽입된 인자를 삭제 한다
stack.append(1)
stack.append(4)
stack.pop()


print(stack[::-1]) #최상단 원소부터 출력
print(stack) # 최하단 원소부터 출력

'''
[1, 3, 2, 5]
[5, 2, 3, 1]
'''

기본 스택의 시간 복잡도 = O(1) 

''' stak의 함수형 소스 코드'''
class Stack:
    def __init__(self): # 기본 스택 생성성
        self.data = []

    def push(self, item): # 스택 쌓기 함수수
        self.data.append(item)

    def pop(self): # 삭제 함수 
        if len(self.data) > 0:
            return self.data.pop()
        return "The stack is empty"

 

Queue(큐)

선입선출(FIFO)의 자료구조 = 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 가능, 대기열 형태

queue의 기본 구조 소스코드 예제

• 리스트를 이용하여 큐를 구현 할 수 있지만 기능적으로는 가능하나 시간복잡도가 높아져서 deque라이브러리를 꼭 써야한다.
• deque 라이브러리는 스택과 큐의 장점을 모두 합친 자료구로 보아도 된다.

기본 deque의 시간 복잡도 = O(1) 

from collections import deque

# Queue 구현을 위해 deque 라이브러리 사용
queue = deque()
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5) # deque라이브러리를 사용하여 queue를 삽입하는것도 append 사용가능 
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft() # 삭제 함수 선입선출이기때문에 popleft사용하여 삭제
queue.append(1)
queue.append(4)
queue.popleft()

print(queue)    # 먼저 들어온 순서대로 출력
queue.reverse() #역순으로 변경
print(queue)    # 나중에 들어온 원소부터 출력되는것 확인인

'''
deque([3, 7, 1, 4])
deque([4, 1, 7, 3])
'''

Time and Space Complexity(시간, 공간 복잡도)

• Enqueue(대기열에 넣기): 데이터를 큐에 추가하면 (데이터를 큐 rear에 추가) O(1) 시간이 걸린다.
• Dequeue(대기열에서 빼기) : 데이터를 큐에서 빼면 (데이터를 큐 front에서 제거) O(1) 시간이 걸린다.

'''queue 의 함수형 소스코드'''
class Queue:
    # Queue 클래스의 경우, 먼저 init 메서드를 정의해야하는데 front(앞)와 rear(뒤) 인스턴스변수를 초기화 해야한다.
    def __init__(self):
        self.front = None
        self.rear = None
    
    # queue에 새로운 노드 item을 삽입할 수 있는 저장공간을 만들어 주는 함수
    def enque(self, item):
        new_node = LinkedListNode(item)
        # queue가 비었는지 체크
        if self.rear is None: 
            self.front = new_node
            self.rear = new_node
        else: # rear가 비어있지 않는 상황
            self.rear.next = new_node # 새로운 노드를 rear다음에 삽입
            self.rear = new_node # 새로운 노드를 rear로 재할당

    # old front에 삭제할 변수를 만들어 큐의 저장공간에서 삭제하는 함수수
    def dequeue(self):
        #queue가 비어 있는지 체크, 안비어있다면면
        if self.front is not None:
            #front 값을 old front에 삽입
            old_front = self.front
            # old front다음 값을 front 값에 삽입
            self.front = old_front.next
        # 큐가 비어있다면
        if self.front is None:
            # rear를 None으로 대체
            self.rear = None
            
        return old_front

 

 

ref. https://www.youtube.com/watch?v=OH7prOt3vQA 

• 파이썬의 문법을 활용한 자료구조

5. 자료 구조 — Python 3.9.7 문서

• 파이썬 복잡도 상세내용

• 데이터의 7V

7v로 알아보는 빅데이터의 정의 및 데이터셋과의 차이점

ref. https://docs.python.org/ko/3/tutorial/datastructures.html

 

5. 자료 구조 — Python 3.9.7 문서