TIL

190426_TIL(Stack and Queue)

컴퓨터공학기초

스택과 큐

  • 제약을 갖는 배열

  • 임시 데이터를 처리할 수 있는 간결한 도구

  • 데이터를 순서대로 처리할 수 있으며 필요 없으면 버릴 수 있다.

  • 배열과 연결리스트, 파이썬의 리스트 등으로 구현할 수 있다.


스택(Stack)

스택의 세 가지 제약

  • 데이터는 스택의 끝에만 삽입할 수 있다.

  • 데이터는 스택의 끝에서만 읽을 수 있다.

  • 데이터는 스택의 끝에서만 삭제할 수 있다.

스택 쉽게 이해하기

  • 접시 더미
    • 접시의 가장 위를 제외하고는 접시를 추가할 수도 제거할 수도 없다.(스택의 끝을 위(top) 이라고도 부른다.)
  • 게으른 학생
    • 스택 연산을 LIFO("Last In, First Out") 이라고 한다. 스택에 푸시된 마지막 항목(가장 최근 항목)이 스택에서 팝 될 첫 번째 항목이라는 의미이다.
    • 교실에 가장 마지막에 들어와서 가장 먼저 나가는 학생과 유사하다.

스택 기본 용어

  • 푸시(push)

    • 스택의 끝(위)에 새 값을 삽입하는 것

  • 팝(pop)

    • 스택의 끝(위)에서 원소를 제거하는 것


큐(Queue)

큐의 세 가지 제약

  • 데이터는 큐의 끝에만 삽입할 수 있다 (스택과 동일)
  • 데이터는 큐의 앞에서만 읽을 수 있다. (스택과 정반대)
  • 데이터는 큐의 앞에서만 삭제할 수 있다.(스택과 정반대)

큐 쉽게 이해하기

  • 화장실 앞에 줄서기
    • 큐 연산을 FIFO("First In, First Out") 이라고 한다. 큐에 삽입된 첫번째 항목(가장 오래된 항목)이 큐에서 제거 될 첫 번째 항목이라는 의미이다.
    • 줄 맨 앞에 있는 사람(가장 먼저 줄 선 사람)이 가장 먼저 화장실에 들어간다.

큐 기본용어

  • 스택과 다르게 큐의 삽입과 삭제는 표준명칭이 없다.
  • 큐 삽입은 put, add, enqueue 등으로 부른다.
  • 큐 삭제는 get, dequeue 등으로 부른다.


스택 두개를 이용하여 큐 구현하기

  • LIFO("Last In, First Out") –> FIFO("First In, First Out")
  • class를 이용하여 구현
  • 이해를 위하여 많은 주석을 달았다.

스택 구현 with python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# adapter pattern
class Stack:
    def __init__(self):
        # 실제로 데이터가 저장되는 곳
        self.container=list()
    
    def empty(self):
        # 비어있지 않은 리스트는 True를 반환, 빈 리스트는 False를 반환
        # 리스트가 비어있지 않은 경우
        # True를 반환 --> if not true --> if false --> if문을 실행하지 않는다 --> False 반환
        # 리스트가 비어 있는 경우
        # False를 반환 --> if not False --> if true --> if문을 실행한다 --> True 반환
        if not self.container:
            return True
        return False
        
        
    def push(self, data):
        # data를 리스트의 끝에 삽입
        self.container.append(data)
    
    # 래퍼 함수(wrapper function) -함수를 감싸고 있는 함수, 안에서 다른 함수를 호출. 내장함수 pop()
    def pop(self):
        return self.container.pop()

스택 두개를 이용하여 큐 구현 with python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Queue:
    def __init__(self):
        # 스택 두개를 생성
        self.first=Stack()
        self.second=Stack()
    
    def empty(self):
        # and
        # 리스트가 비어있는 경우 True를 반환
        # True and True 일 때만, True를 반환
        # fitst stack 과 second stack이 모두 비어있는 경우에만 True를 반환한다.
        if self.first.empty() and self.second.empty():
            return True
        return False
        
    def enqueue(self, data):
        # data를 fitst stack의 끝(위)에 삽입
        self.first.push(data)
    
    def dequeue(self):
        if self.empty():
            return None
        # first에서 second로 옮기는 시점
        # second stack이 비어있을 때(True를 반환)
        if self.second.empty():
            # first stack이 빌 때까지
            while not self.first.empty():
                # second stack에 first stack을 pop한 값을 push하여 넣어준다
                self.second.push(self.first.pop())
        
        return self.second.pop()

테스트 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
q=Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)

print(q.dequeue())

q.enqueue(4)
q.enqueue(5)

# fitst stack 과 second stack이 모두 비어있는 경우에만 True를 반환한다.
# while not True --> while False --> 반복문을 실행하지 않는다.
# fitst stack 과 second stack이 모두 비어있는 경우에만 반복문을 실행하지 않는다.
while not q.empty():
    print(q.dequeue())

참고자료

참고도서

  • 누구나 자료구조와 알고리즘
Share