초보몽키의 개발공부로그

강의노트 19. 자료구조 - stack (스택)

18 Apr 2017 |

패스트캠퍼스 컴퓨터공학 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

stack

  • 수업자료
  • 참고자료
  • 참고글-큐와 스택의 실제 사용 예
  • stack과 queue는 search가 없다.
  • LIFO (Last Input First Out, 선입후출, 라이포)
  • 데이터 저장소에서 새로 들어오는 데이터의 위치가 저장소의 끝 부분(Top 혹은 Top pointer라고 한다)이고, 내보내는 데이터 역시 저장소의 Top에서 나간다. 입력은 push, 출력은 pop이다. peek는 Top의 위치에 있는 데이터를 확인하는 것을 말한다.
views

ADT(abstract data type) 추상 자료형

  • 참고 추상자료형-위키피디아
  • 참고 추상자료형
  • 기능의 구현 부분을 나타내지 않고 순수한 기능이 무엇인지 나열한 것을 추상 자료형이라고 한다
  • 메소드의 목록 (인터페이스)
  • 추상 자료형은 구현자와 사용자를 분리해 준다. 라이브러리를 가져다 쓰거나 내장 함수를 사용하는 것도 추상 자료형이 정의되어 있기 때문이다. 또한 추상 자료형에 대한 구현은 외부로 부터 숨겨져 정보 은닉(Information Hiding)이 이루어지게 된다. (출처)

stack ADT (인터페이스)

  • is_empty() -> boolean
  • push -> insert : push(data)
  • pop -> delete : pop return 맨위 값을 리턴하고 동시에 삭제
  • peek -> 엿보기 : 맨 위 값 반환만 하고 삭제는 안함

stack 구현 예시1 (python list 사용)

# Stack 클래스 정의 - python list 활용
class Stack(list):
    push = list.append    # Insert
                          # Delete - 내장 pop 메소드 활용
    def is_empty(self):   # 데이터가 없는지 확인
        if not self:
            return True
        else:
            return False

    def peek(self):        # 최상단 데이터 확인
        return self[-1]

if __name__=="__main__":
    s = Stack()
    s.push(1)
    s.push(2)
    s.push(3)

    while s:
        data = s.pop()
        print(data, end=' ') # 3 2 1

stack 구현 예시2 (node 사용)

  • 면접에서는 node를 사용한 stack 구현이 자주 출제된다.
  • head만 있어도 구현이 가능하다.
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

    def is_empty(self):
        if not self.head:
            return True

        return False

    def push(self, data):
        new_node = Node(data)

        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if self.is_empty():
            return None

        ret_data = self.head.data

        self.head = self.head.next

        return ret_data

    def peek(self):
        if self.is_empty():
            return None

        return self.head.data

if __name__ == "__main__":
    s = Stack()

    print(s.is_empty()) # True

    s.push(1)
    s.push(2)
    s.push(3)
    s.push(4)
    s.push(5)

    print("peek of data : {}".format(s.peek())) # 5

    while not s.is_empty():
        print(s.pop()) # 5, 4, 3, 2, 1

Related Posts