DataStructure: Stack & Queue

Stack

• LIFO(Last In First Out), 마지막으로 저장한 데이터가 처음으로 읽힌다.
• 저장은 push, 데이터를 읽어들이는 건 pop이라고 하는데, pop은 읽어들임과 동시에 stack에서 삭제한다.

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

   def push(self, data):
     self._stack.append(data)

   def pop(self):
     if len(self._stack) == 0:
       return None

     data = self._stack[-1]
     del self._stack[-1]

     return data

   def peek(self):
     if len(self._stack) == 0:
       return None

     data = self._stack[-1]

     return data

언제 사용할까?

• 프로그램에서 함수 호출 기록을 stack으로 저장한다.
• web browser 내역 흑등 내역인데 최신 내역이 먼저 나와야 하는 경우
• 웹브라우저 방문기록(뒤로가기), 실행 취소
• 미로 찾기 알고리즘(방문한 곳을 좌표로 표기하고, 다음 방문할 곳을 탐색한 후 stack에 간으한 곳 전부를 push하고, 다시 pop하면서 현재 경로로 변경하는 것을 반복)

Queue

• FIFO(First In First Out), 먼저 push 된게 먼저 pop 된다.
• 일반적인 queue 말고도 double ended queue, priority queue등 도 있다.

class Queue:
    def __init__(self):
        self._queue = []

    def push(self, data):
        return self._queue.append(data)

    def pop(self)
        if len(self._queue) == 0:
            return None

        return self._queue.pop()

    def peek(self):
        if len(self._queue) == 0:
            return None

        return self[0]

언제 사용할까?

• 맛집 예약, 티켓 카운터 등의 예약 시스템
• OS 프로세서 스케쥴링 시스템(priority queue 사용)
• CPU의 프로세스 스케쥴링
• 프린터의 인쇄 대기 목록