5.1. 스택

데이터를 접시쌓듯이 차곡차곡 쌓는다 : 맨 마지막에 들어온 데이터 먼저 차출됨(LIFO)

1) ADT

1-1) Object

• LIFO 객체

1-2) Operation

1) empty() : Boolean 타입
2) push(data) : data를 스택 맨 위에 삽입
3) pop() : 스택 맨 위에 있는 값 삭제 후 해당 값 반환
4) peek() : 스택 맨 위에 있는 데이터를 반환

2) 구현

2-1) 동적배열로 구현

• append()와 pop()을 사용하면 손쉽게 구현 가능
• 성능 : O(1)

2-2) 코드

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):
        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():
    print(s.pop(), end='')

• self.container = list() : list()를 활용하여 실제 데이터를 담을 객체를 동적 배열로 활용

5.2. 큐

줄 서기 : 먼저 온 사람이 먼저 입장, FIFO

• front : 맨 처음에 들어온 데이터
• rear : 맨 마지막에 들어온 데이터

1) ADT

1-1) Object

• FIFO 객체

1-2) Operation

1) empty() : Boolean 타입
2) is_full() : 큐가 가득 찼으면 T, 아닌 경우 F
3) enqueue(data) : 큐 맨 뒤에 데이터 삽입
4) dequeue() : 큐 맨 처음 데이터 삭제하면서 해당 데이터 반환
5) peek() : 큐의 맨 처음 데이터 값을 삭제없이 반환

2) 구현

2-1) 동적배열

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]

• 이전 스택 구현과 마찬가지로 list()를 통한 큐 구현

  dequeue() : 동적 배열의 맨 처음 값 삭제이므로 O(n)

2-2) 원형 큐(circular queue)

2-2-1) 동작 원리

• front : dequeue를 할 때 모든 데이터를 이동시키지 않고 front를 한 칸 씩 이동
• rear : 맨 마지막 데이터 다음을 가리킴. rear가 맨 마지막에 도착했을 경우 맨 처음의 값을 가리키게 하여 선형적인 동적 배열을 원형으로 이어 붙임

  큐가 빈 경우 : front = rear
  큐가 가득 찬 경우 : rear + 1 = front

• 추가적으로 front나 rear가 배열의 마지막에 도달 시 맨 처음으로 이동시켜줄 메서드 필요

2-2-2) 코드

class CQueue:
    MAXSIZE = 10
    def __init__(self):
        self.container = [None for _ in range(CQueue.MAXSIZE)]
        self.front = 0
        self.rear = 0
    
    def is_empty(self):
        if self.front == self.rear:
            return True
        return False
    #front=rear면 큐가 비었다.

• self.container = [None for _ in range(CQueue.MAXSIZE)] : 원형 큐의 내부표현은 동적배열임
• if self.front == self.rear : return True : 큐가 비었다.

def __step_forward(self, x):
        x += 1
        if x >= CQueue.MAXSIZE:
            x = 0
        return x 

• 편의 함수 __step_forward() : front나 rear 이동 시 동적배열 크기 초과 시 처음으로 이동 시킴.
• enqueue, dequeue 연산 전 동적 배열의 끝에 도달했는지 아닌지 판단 후 연산 수행

def is_full(self):
        next = self.__step_forward(self.rear)
        if next == self.front:
            return True
        return False

• is_full() : 원형 큐가 가득 찼는지 확인하는 메서드
  -> rear에 +1하기 전에 편의 함수를 통해 front와 비교 필수

def enqueue(self, data):
        if self.is_full() : 
            raise Exception("The queue is full")
        self.container[self.rear] = data
        self.rear = self.__step_forward(self.rear)

• if self.is_full() : : 큐에 삽입 전에 큐가 가득찼는지 확인
• self.container[self.rear] = data : 큐의 맨 마지막 부분에 원하는 데이터 삽입
• self.rear = self.__step_forward(self.rear) : rear를 기존보다 한 칸 뒤로 미룸.

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

• ret = self.container[self.front] : 삭제된 데이터를 반환해야 하므로 ret라는 변수에 삭제될 값 저장
• self.front = self.__step_forward(self.front) : front 값 한 칸 뒤로 미룸

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

• peek() : 단순히 front 값 반환

cq = CQueue()

for i in range(8):
    cq.enqueue(i)

for i in range(5):
    print(cq.dequeue(), end=" ")

for i in range(8, 14):
    cq.enqueue(i)

while not cq.is_empty():
    print(cq.dequeue(), end=" ")

print()
for i in range(10):
    print(cq.container[i], end=" ")

• 결과 :

5.3. 덱

스택으로도, 큐로도 사용 가능 : front, rear에서 모두 입출력 가능

1) ADT

1-1) Operation

1) is_empty() : Boolean, 덱이 비어있으면 T, 아니면 F
2) is_full() : Boolean, 덱이 가득 차 있으면 T, 아니면 F
3) insertFront(data) : 덱의 맨 앞에 데이터 삽입
4) insertRear(data) : 덱의 맨 뒤에 데이터 삽입
5) popFront() : 덱의 맨 처음 데이터 삭제하면서 해당 값 반환
6) popRear() : 덱의 맨 마지막 데이터 삭제하면서 해당 값 반환
7) peekFront() : 덱의 맨 처음 데이터 값만 반환
8) peekRear() : 덱의 맨 마지막 데이터 값만 반환

2) deque를 이용하여 스택과 큐 구현

from collections import deque

print('*'*20 + 'STACK' + '*'*20)
stack =deque()
for i in range(1,6):
    stack.append(i)
    print(stack)

for i in range(5):
    print(stack.pop())

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())

• 삽입 : rear에 append(), front에서는 appendleft()
• 삭제 : rear에 pop(), front에서는 popleft()

스택 : rear에 append 및 pop
큐 : rear에 append, front에서 pop

파이썬 덱 : 이중연결리스트로 구현되어 있음