자료구조 - stack and Queue

Stack

Stack은 삽입과 삭제를 한쪽 끝(top)에서만 할 수 있도록 제한된 선형 자료구조이다. 자료를 넣으면(push), 꺼낼 때(pop)는 반대의 순서로 나오게 된다. (후입선출, LIFO)

stack의 활용

stack은 다음과 같을 때 주로 사용된다.

1. '최근에 임시저장한' 데이터를 가장 먼저 활용:
함수의 안에서 선언되는 매개변수,지역변수들은 스택에 저장된다.
함수가 끝나면 메모리에서 변수가 사라져야한다. 스택에 저장했으므로 바로 최근에 저장된 것들을 팝 하면 된다.

2. 쌍을 맞추기:
문자열에 주어진 괄호가 쌍이 맞는지 검사
'(':push
')':pop
문자열이 끝나고 stack에 남은 것이 있거나 빈 stack에서 pop하는 경우에는 쌍이 맞지 않는다는 것이다.
3. 뒤로 가기 기능:
웹페이지, 컨트롤제트, 그래프탐색에서 뒤로가기 등에 활용

stack 구현

# in python, stack and queue are made with list
class Stack:
    def __init__(self):
        self.items = list()
    # check list is empty
    def is_empty(self):
        return self.items == []
    # 넣기
    def push(self, item):
        self.items.append(item)
    # 가장 최근에 삽입된 자료 꺼내기
    def pop(self):
        if self.is_empty():
            return None
        return self.items.pop(-1)
    # 가장 최근에 삽입된 자료 확인
    def top(self):
        if self.is_empty():
            return None
        return self.items[-1]
    # 현재 입력된 자료 갯수 출력
    def size(self):
        return len(self.items)
    # 전체 비우기
    def empty(self):
        while self.pop():
            True

Queue

삽입과 삭제를 정해진 반대쪽 양끝에서만 할 수 있도록 제한된 선형 자료구조이다. 자료를 넣으면(enqueue), 꺼낼 때(dequeue)는 넣은 순서로 나오게 된다. (선입선출, FIFO)

Queue 활용

큐는 대기열, 버퍼등을 구현하는데 사용된다. 또한 스케쥴링 알고리즘을 만들 때 쓰인다.

Queue 구현

# in python, stack and queue are made with list
class Stack:
    def __init__(self):
        self.items = list()
    # check list is empty
    def is_empty(self):
        return self.items == []
    # 넣기
    def push(self, item):
        self.items.append(item)
    # 가장 먼저 삽입된 자료 꺼내기
    def pop(self):
        if self.is_empty():
            return None
        return self.items.pop(0)
    # 가장 먼저 삽입된 자료 확인
    def front(self):
        if self.is_empty():
            return None
        return self.items[0]
    # 가장 최근 삽입된 자료 확인
    def rear(self):
        if self.is_empty():
            return None
        return self.items[-1]
    # 현재 입력된 자료 갯수 출력
    def size(self):
        return len(self.items)
    # 전체 비우기
    def empty(self):
        while self.dequeue():
            True