TIL 221111

1. 자료구조

1) 스택(Stack)

학습목표

1. 스택 이해하기
2. 스택의 기본연산 이해하기
3. python으로 스택 구현하기

스택이란?

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료구조. (후입선출)
실생활에서는 바벨을 예로 들 수 있겠다.
원판을 제거할 때 마지막으로 추가된 원판을 빼야하니까.

데이터를 자주 넣고 뺄 필요가 있을 때 사용하는 자료구조.

스택에서 사용하는 연산

• push(item) : item을 스택의 가장 위에 추가한다.
• pop() : 스택에서 가장 위에 있는 항목을 제거한다.
• peek() : 스택의 가장 위에 있는 항목을 반환한다.
• isEmpty() : 스택이 비어 있을 때에 true를 반환한다.

스택 구현하기

스택은 링크드리스트로 구현할 수 있다.

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


class Stack:
    def __init__(self):
        self.head = None

    # 데이터를 입력받아 맨 앞에 삽입
    def push(self, value):
        new_head = Node(value)
        new_head.next = self.head 
        self.head = new_head

    # 맨 앞에 있는 데이터를 꺼내기
    def pop(self):
        if self.is_empty():
            return "Stack is empty!"
        deleted_head = self.head
        self.head = self.head.next
        return deleted_head
    
    # 맨 앞의 데이터 보기
    def peek(self):
        if self.is_empty():
            return "Stack is empty!"
        return self.head.data

    # isEmpty 기능 구현
    def is_empty(self):
        return self.head is None

python에서의 스택

실제 파이썬에서는 list를 이용해 스택을 사용한다.

• append()
  • 해당 item을 스택의 맨 앞에 삽입
• pop()
  • 스택의 맨 앞에 있는 item을 삭제하고 해당 item을 반환

2) 큐

학습목표

1. 큐 이해하기
2. 큐의 기본연산 이해하기
3. python으로 큐 구현하기

큐란?

먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 형식의 자료구조. (선입선출)
실생활에서는 대기줄을 예로 들 수 있다.
먼저 줄 선 사람이 먼저 들어가니까.

순서가 중요할 때 사용하는 자료구조.

큐에서 사용하는 연산

• enqueue(item) : item을 큐의 끝부분에 추가한다.
• dequeue() : 큐 앞의 데이터를 뽑는다.
• peek() : 큐에서 가장 위에있는 항목을 반환한다.
• isEmpty() : 큐가 비어 있을 때에 true를 반환한다.

큐의 구현

큐는 링크드리스트로 구현할 수 있다.

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


class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, value):
        new_node = Node(value)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
            return

        self.tail.next = new_node
        self.tail = new_node

    def dequeue(self):
        if self.is_empty():
            return "Queue is empty!"
        delete_head = self.head
        self.head = self.head.next

        return delete_head.data

    def peek(self):
        if self.is_empty():
            return "Queue is empty!"

        return self.head.data

    def is_empty(self):
        return self.head is None

python에서의 큐

파이썬에서는 deque(덱)이라는 라이브러리를 이용한다.

• append(item)
  • 큐의 끝부분에 원소를 삽입.
• popleft()
  • 큐 앞의 데이터를 뽑는다.