대표적인 자료구조의 예시

• 선형 구조: 자료가 순서를 가지고 연속되어 있음
  ex) 스택, 큐
• 비선형 구조: 선형 구조에 해당하지 않는 자료구조
  ex) 트리, 그래프

스택

특징

• 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조
• 후입선출(LIFO, Last In First Out)
• python의 리스트를 이용해서 구현
• 의존관계가 있는 상태를 저장한다. 어떤 일보다 더 먼저 처리되어야 하는 일이 있다면 스택에 저장하여 관리한다. (ex: 재귀함수)

구현

class Stack:
    def __init__(self) :
        self.myStack = []

    def push(self, n) :
        self.myStack.append(n)

    def pop(self) :
        n = len(self.myStack)
        if n>0:
            del self.myStack[n-1]
        else:
            pass

    def size(self) : # stack 안에 들어있는 값의 수 return
        return len(self.myStack)

    def empty(self) : # 비어있으면 1, 아니면 0 return
        n = len(self.myStack)
        if n>0:
            return 0
        else:
            return 1

    def top(self) :
        '''
        stack의 가장 위에 있는 정수를 return
        만약 stack에 들어있는 값이 없을 경우에는 -1을 return
        '''
        n = len(self.myStack)
        if n>0:
            return self.myStack[n-1]
        else:
            return -1 

큐

특징

• 입구와 출구가 각각 한 쪽 끝에 존재하는 자료구조
• 선입선출(FIFO, First In First Out)
• python의 queue 모듈을 이용해서 구현
• 어떤 작업들이 의존관계가 없고, 병렬적으로(=동시에) 이루어져도 괜찮을 때 큐에 저장하여 관리한다.

구현

import queue

q = queue.Queue()

# PUSH
q.put(1)
q.put(2)
q.put(3)

# POP
q.get() # 1 - 맨 처음에 넣은 데이터 먼저 나옴

# SIZE
q.qsize() # 2