Stack, Queue, Deque

• OS 내부 많은 시스탬이 스택과 큐를 기반으로 한다.
• 이후 장에서 배울 내용인 트리 순회도 스택과 큐로 하게 된다.
• 1장에서 배운 스택 프레임도 스택이다.
  • 스택 프레임 : 함수가 호출될 때 메모리에서 생긴 공간

---

[ 개념 설명 ]

1. Stack : 접시 쌓기

• 새로 들어오는 접시는 언제나 가장 위에 쌓인다 (IN)
• 사용하기 위해 나가는 접시는 언제나 가장 위에서 나간다 (OUT)
• LIFO(Last In First Out)

---

2. Queue : 줄서기

• 새로 줄서는 사람은 언제가 가장 마지막에 줄을 선다 (IN)
• 줄에서 가장 첫번째 사람이 가장 먼저 나간다 (OUT)
• FIFO(First In Fist Out)

---

3. Deque : Stack 기능 + Queue 기능

• Stack과 Queue는 In & Out 방향이 오로지 하나

3-1. Stack

• Stack(접시 쌓기)는 top(위)에서 IN
• Stack(접시 쌓기)는 top(위)에서 OUT
• Deque은 가장 아래(bottom)에서 IN & OUT 가능

3- 2. Queue

• Queue(줄서기)는 raer(가장 마지막)에서 IN
• Queue(줄서기)는 front(가장 첫번째)에서 OUT
• Deque은 rear, front 둘 다 IN & OUT 가능

---

[ 구현 ]

1. Stack : 접시 쌓기

Operation (연산)

class Stack:
    def __init__(self):
        self.container = list()   # 내부 표현(representation): 실제로 데이터를 담는 객체는 동적 배열

    def empty(self):
        if not self.container:
            return True
        else:
            return False

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

    def pop(self):
        if self.empty():
            return None
        return self.container.pop()

    def peek(self):
        if self.empty():
            return None
        return self.container[-1]

s = Stack()

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

while not s.empty(): ## stack이 비어있지 않으면 마지막 값을 출력하라 
    print(s.pop(), end=" ")    

3 2 1 

그냥 list 쓰면 되지 않나요?

• 내부 표현은 python의 동적 배열인 list로 하지만, 리스트 함수를 wrapping(래핑)하여 추상화 시킴
• 프로그래머에게 가독성이 떨어지기 때문에
• 이게 동적배열인지, 스택인지를 찾기 위해 코드를 꼼꼼하게 분석해야한다고 합니다.
• 동의하시나요?

---

2. Queue : 줄서기

Operation (연산)

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):
        # 동적 배열의 맨 처음 데이터를 삭제하므로 빅오는 O(n)
        # 좀 더 효율적으로 구현할 수는 없을까?
        return self.container.pop(0)

    def peek(self):
        return self.container[0]

class CQueue:
    MAXSIZE = 10
    def __init__(self):
        self.container = [None for _ in range(CQueue.MAXSIZE)]   ## MAXSIZE 개수의 None 원소가 담긴 LIST 
        self.front = 0
        self.rear = 0  # 원형 큐의 내부 표현은 동적 배열인 리스트. 
        # front와 reear를 0으로 초기화 
        # 두개 갚이 같기 때문에 큐가 비어있음

    def is_empty(self):
        if self.front == self.rear:
            return True
        return False

    def __step_forward(self, x): ## 편의함수: front나 rear를 뒤로 이동했을 때 동적 배열을 벗어난다면 동적 배열의 맨 처음으로 이동
        x += 1 # 그 다음 포인트를 찾기위해서 +1 
        if x >= CQueue.MAXSIZE:
            x = 0
        return x
    # front와 rear가 이동할 때(enqueue : rear 이동, dequeue : front 이동) 무작정 1을 더할 수 없기 때문에 
    # 동적 배열의 끝에 도달하면 맨 처음으로 이동하게 만들어줌 (즉 1을 더하면서 원형으로 연결 시켜줌)

    def is_full(self):
        next = self.__step_forward(self.rear)  # 그냥 단순히 rear+1을 하면 큐 사이즈 벗어나면서 멀어지기만 함 그래서 __step_forward() 메서드로 +1칸 이동
        if next == self.front:
            return True
        return False

    def enqueue(self, data):
        if self.is_full():
            raise Exception("The queue is full")
        self.container[self.rear] = data  # 현재 마지막 다음(rear) 데이터로 입력 
        self.rear = self.__step_forward(self.rear) # 데이터가 하나 들어와서 rear 순서로 들어가게 되면 rear는 +1 (앞으로 전진) 해줘야함. 
        # rear는 맨 마지막 데이터가 아닌 맨 마지막 데이터의 다음을 가리키고 있기 때문에 

    def dequeue(self):
        if self.is_empty():
            raise Exception("The queue is empty")
        ret = self.container[self.front]  # 가장 앞(front)의 원소를 ret으로 할당
        self.front = self.__step_forward(self.front) 
        return ret  
        # 첫번째 데이터를 삭제한다고 해서 바로 front를 뒤로 이동시켜선 안됨. 
        # 데이터를 반환해야하기 때문에 먼저 ret 변수에 삭제될 요소를 담은 후 삭제하고 front를 뒤로 이동시키고 ret 값을 반환 해야함 
        # (따로 삭제 안해도되는게 어차피 rear가 첫 원소에 할당되어 있어도 enqueue 되는 다른 값으로 바뀔거라)

    def peek(self):
        if self.is_empty():
            raise Exception("The queue is empty")
        return self.container[self.front]

cq = CQueue() 

for i in range(8):
    cq.enqueue(i)  # 0부터 7까지 값 삽입 

for i in range(5):
    print(cq.dequeue(), end=" ")  # 5개 앞부분 삭제  (0부터 4까지 날림. 5부터 7까지만 존재하지만 값은 그대로)

for i in range(8,13): ## 8부터 13까지 6개 삽입  하지만 5개 앞부분이 날라갔기 때문에 자연스럽게 이어짐 (10,11,12,13,4,5,6,7,8,9,)     ## 만약에 18까지 한다면 Exception 에러 뜸 
    cq.enqueue(i)

print()
while not cq.is_empty(): # container가 비어있지 않다면 계속 수행
    print(cq.dequeue(), end=" ")  ## 5번부터 13까지 삭제 

print()
for i in range(10):
    print(cq.container[i], end=" ")  ## 실제 내부에 있는 동적 배열의 실제 모습 

0 1 2 3 4 
5 6 7 8 9 10 11 12 
10 11 12 3 4 5 6 7 8 9 

## SAMPLE ### 
print()
print(cq.peek())

Exception: The queue is empty

---

3. Deque

Operation (연산)

from collections import deque

print('*' * 20 + ' STACK ' + '*' * 20)

stack = deque()
for i in range(1,6): # 1부터 5까지 
    stack.append(i) # 뒤에 입력 (rear에 데이터 입력)
    print(stack)    

for i in range(5):
    print(stack.pop()) # 뒤에서 출력 및 삭제 (rear에 데이터 출력)


print('*' * 20 + ' QUEUE ' + '*' * 20)

queue = deque()
for i in range(1,6):
    queue.append(i)
    print(queue)

for i in range(5):
    print(queue.popleft())   # 앞에서 출력 및 삭제 (front에 데이터 출력)  //// 참고로 앞부분에 데이터 입력을 하기 위해선 appendleft()

******************** STACK ********************
deque([1])
deque([1, 2])
deque([1, 2, 3])
deque([1, 2, 3, 4])
deque([1, 2, 3, 4, 5])
5
4
3
2
1
******************** QUEUE ********************
deque([1])
deque([1, 2])
deque([1, 2, 3])
deque([1, 2, 3, 4])
deque([1, 2, 3, 4, 5])
1
2
3
4
5

---

[ 사용 사례 ]

1. Stack : 접시 쌓기

• 알게 모르게 다양한 곳에 쓰이고 있다.
• 스택 프레임 (함수가 호출될 때 메모리에서 생긴 공간)

---

2. Queue : 줄서기

• 스택보다 더 다양한 곳에서 사용된다
• OS는 task queue를 사용하여 스케줄링한다
  • 스케줄링이란
    • 컴퓨터는 동시에 여러 프로그램을 실행할 수 있는데 실제로 작업을 수행하는 CPU 개수는 제한적임
    • 이때 OS는 여러 프로그램에서 작업을 요청받아 이를 큐에 담은 후, 정해진 알고리즘에 따라 큐에서 테스크(작업)를 실행함
    • 이렇게 실행할 작업 순서를 정하는 것을 스케줄링이라 한다.

---

3. Deque : Stack 기능 + Queue 기능

• Deque를 사용하여 stack과 queue를 구현한다 (흉내낸다)