자료구조 02. Stack과 queue

2019.03.14 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

자료구조 Stack & Queue

1.Stack

stack이란 무언가를 쌓는다라는 의미를 갖는 자료구조이다.
stack의 사전적의미를 찾아보면
: [명사] 동적이고 순차적인 자료의 목록.
: [영어] 무더기, 많음 다량, 굴뚝.
이라고 나온다.

LIFO(Last in, First out)

후입선출.
스택은 접시를 쌓는 것과 같기 때문에 먼저 들어간 자료보다는 가장 늦게 쌓이고 가장 위에 있는 접시가 먼저 나오게 된다.
이것은 후입선출이라고 한다.

먼저 스택을 사용하기 위해서 ADT라는 개념을 배워보자.

ADT(abstract data type) : 추상 자료형

1. 어떤 자료구조가 가지고 있는 오퍼레이션(함수)의 나열(목록)
2. 함수 시그니처(인터페이스)만 나열할 뿐, 내부 구현은 표기하지 않음
3. 함수(operation)의 작동 방식 설명.

위의 조건을 꼭 지켜줘야한다. ADT에 대해 명쾌히 설명을 해준 블로그를 참고해보면,

추상 자료형(Abstract Data Type)

기능의 구현 부분을 나타내지 않고 순수한 기능이 무엇인지 나열한 것을 추상 자료형이라고 한다.

예를 들면, 사용 설명서와 같다. 선풍기의 사용 설명서를 본다고 가정하자. 사용 설명서에는 정지, 미풍, 약풍, 강풍, 회전, 타이머등의 기능 설명과 사용 방법이 나와있다. 하지만 버튼을 눌렀을 때 선풍기 내부회로에서 어떤 일이 발생하는지에 대해서는 전혀 나와있지 않다. 추상 자료형은 선풍기의 사용 설명서와 같이 기능과 사용 방법을 정의한 것이다.

추상 자료형의 필요성

추상 자료형은 구현자와 사용자를 분리해 준다. 라이브러리를 가져다 쓰거나 내장 함수를 사용하는 것도 추상 자료형이 정의되어 있기 때문이다. 또한 추상 자료형에 대한 구현은 외부로 부터 숨겨져 정보 은닉(Information Hiding)이 이루어지게 된다.

추상 자료형 정의

무선 마우스의 추상 자료형을 정의해 본다면,

ADT of Wireless Mouse

• Data

: Power, LeftButton, RightButton 전원, 왼쪽버튼, 오른쪽버튼

• Operation

: PowerOn() 전원 On

: PowerOff() 전원 Off

: LeftButtonClick() 왼쪽 버튼 클릭

: RightButtonClick() 오른쪽 버튼 클릭

출처: https://ledgku.tistory.com/41 [견우와 직녀]

위의 글을 참조하여 한번에 개념을 이해하였다.

선생님은 코드를 통해 ADT에 대해 이야기해주셨다.

>>>dir(list)
>>>
['__add__',
 '__class__',
 '__contains__',
 '__delattr__',
 '__delitem__',
 '__dir__',
 '__doc__',
 '__eq__',
 '__format__',
 '__ge__',
 '__getattribute__',
 '__getitem__',
 '__gt__',
 '__hash__',
 '__iadd__',
 '__imul__',
 '__init__',
 '__init_subclass__',
 '__iter__',
 '__le__',
 '__len__',
 '__lt__',
 '__mul__',
 '__ne__',
 '__new__',
 '__reduce__',
 '__reduce_ex__',
 '__repr__',
 '__reversed__',
 '__rmul__',
 '__setattr__',
 '__setitem__',
 '__sizeof__',
 '__str__',
 '__subclasshook__',
 'append',
 'clear',
 'copy',
 'count',
 'extend',
 'index',
 'insert',
 'pop',
 'remove',
 'reverse',
 'sort']

위와 같이 list라는 객체의 내장 메소드들이 나오게 되는데
(#_method_ 와 아래 나온 메소드들의 차이를 알아보자!)

여기서 아래에 나오는 append, clear, copy와 같은 메소드들을
다시 코드를 통해 검색해보면

>>>help(list.append)
>>>Help on method_descriptor:

append(...)
    L.append(object) -> None -- append object to end

위와 같은 것을 얻을 수 있다. 즉 ADT가 요구하는 3가지 조건에 부합하는
설명을 볼 수 있다.
함수의 작동방식에 대해 설명해주고 있고(help on method_descriptor)
함수의 시그니처(인터페이스)만 설명하고 내부구현에 대해서는 언급하지 않으므로 추상자료형의 표기법으로 적합하다.

위와 같은 표기법으로 append, clear, copy, count, extend,,, sort까지 모아놓으면 그게 list의 ADT이다

Stack의 ADT

Stack의 ADT (operation list , operation의 시그니처만 나열)

1. S.empty() --> Boolean (스택이 비어있으면 True, 아니면 False)
2. S.push(data) ---> None (스택의 맨 위에 데이터를 쌓는다.) None->무조건들어간다
3. S.pop() ---> data (스택 맨 위의 데이터를 삭제하면서 반환)
4. S.peek() ---> data (스택 맨 위의 데이터를 반환)

• ADT 구현

>>>class Stack:
>>>    def __init__(self):
>>>        self.container=list()
>>>
>>>    def empty(self):
>>>        if not self.container:
>>>            return True
>>>        else:
>>>            return False
>>>
>>>    def push(self, data):
>>>        self.container.append(data)
>>>
>>>    def pop(self):
>>>        return self.container.pop()
>>>
>>>    def peek(self):
>>>        return self.container[-1]

위와 같이 스택의 ADT를 표시할 수 있다.

코드를 통한 Stack

스택을 사용하기 위해서는 stack 모듈을 불러와야 한다.

>>> from stack import Stack
>>> st=stack()       #스택이 만들어진다. list와 비슷하다.
>>> st.push(1)
>>> st.push(2)
>>> st.push(3)
>>> st.push(4)
>>> st.push(5)
>>> while not st.empty():
>>>     data = st.pop())
>>>     print(data)
>>> 5
>>> 4
>>> 3
>>> 2
>>> 1
>>> 

Stack과 함께 또 봐야하는 것이 있는데 바로 queue이다.

Queue(큐)

지금 놓치지 말아야 할 것은 stack와 queue는 모두 자료구조에서 자료가 저장되는 형태를 나타는 것이다.
queue의 사전적의미를 보면

: 규, 대기 행렬, 줄을 서서 기다리다
: 꼬리, 끝, 후미.

를 말한다. stack과는 다른 형태로 자료구조가 쌓인다.
Stack의 단점은 늦게 온 사람이 먼저 일을 처리하는 형태로 먼저 온 사람은 지속적으로 기다려야 하는 단점이 있다.
그에 비해 우리가 일반적으로 줄서기와 같은 것이 queue인데
먼저 기다린 사람이 먼저 나간다. FIFO(First in First Out) : 선입선출이며 보통 프로세스 처리, cpu관리에서 많이 쓰인다.

큐의 문제점은 일반적으로 배열을
[1][2][3][4][5]
이런 직선 형태로 보왔을 때,
[Pop][2][3][4][5] 가장 오래기다린, 처음 들어온 [1]이라는 데이터가 Pop이 되면 다른 데이터들을 차례대로
땡겨주어야 한다.
( 소수의 자료의 경우는 상관이 없지만 많은 데이터의 경우 연산에 많은 시간이 걸린다. )

이러한 문제점을 해결하기 위해 나온게 원형 큐, 순환 큐, 환영 큐 라고 불리는 방벙인데 배열을 직선이 아니라 원형으로 보는 것이다. (#다음에 추가적인 공부가 필요하다)

Queue의 ADT

Queue의 ADT (operation list , operation의 시그니처만 나열)

1. Q.empty() —> Boolean
   1. 큐가 비어있으면 true, 비어있으면 False
2. Q.enqueue(data) —> None
   1. 큐의 맨 뒤에 데이터를 쌓는다.
3. Q.dequeue(data) —> data
   1. 큐의 맨 앞에 데이터를 삭제하면서 반환
4. Q.peek() —> data
   1. 큐의 맨 앞의 데이터를 반환

• ADT 구현

>>>class Queue:
>>>
>>>    def __init__(self):
>>>        self.container = list() 
>>>    
>>>    def empty(self):
>>>        if not self.container:
>>>            return True
>>>        else:
>>>            return False
>>>    def enqueue(self, data):
>>>        self.container.append(data)
>>>
>>>    def dequeue(self):     
>>>        return self.container.pop(0)
>>>
>>>    def peek(self):
>>>        return self.container[0]

위와 같이 Queue의 ADT를 표시할 수 있다.

위에서 배운 것을 바탕으로 다음에는 Stack을 활용하여 계산기를 구현한다!