포인터 기반의 연결 방식(1) - 추상 데이터 타입(스택, 큐, 덱)

책 <파이썬 자료구조와 알고리즘>을 기본으로 배운 자료구조 내용입니다

 

목차

추상 데이터 타입이란?

추상 데이터 타입의 특징

추상 데이터 타입 - 스택, 큐, 덱

 

<추상 데이터 타입>

추상 데이터 타입(추상 자료형, ADT)이란?

• 자료형을 추상화시킨 형태.
• `자료` 및 `연산`을 모두 하나의 단위로 묶고, 외부로부터 내부 자료를 함부로 접근 못하게함.즉, 자료형에 대한 의도되지 않은 변화를 최소화하고, 이를 마치 블랙박스 처럼 취급할 수 있게 하는 것.
• 이를두고, 캡슐화(Encapsulation) 또는 정보은닉(Information Hiding) 라고도 함

 

추상 데이터 타입의 특징

• `자료` 및 `연산`을 모두 하나의 단위로 묶음
  
• 자료의 캡슐화 (data encapsulation) 또는 정보은닉(information hiding)을 도모함
  
• 즉, 내부적으로는 데이터와 함수(메소드)를 서로 연결짓고, 외부적으로는 데이터의 표현 방식을 사용자로부터 숨김
  

※ 자료 추상화(추상 자료형)에 의해, 비로소 객체지향 프로그래밍 기법이 가능하게 됨

 

<추상 데이터 타입 - 스택, 큐>

스택(Stack)

선형 리스트에서 자료가 리스트에 추가되는 순서와 반대로 처리되는 후입선출(LIFO) 리스트

 

스택의 동작

• push : 추가,집어넣기
• pop : 삭제,빼냄
• peek/top : 삭제 없이 top 내용 확인
• clear/empty : 초기화 또는 비어있는지 여부 확인
• full : 가득 찼는지 여부 확인
• size : 크기 확인

 

스택 구현 방법

리스트의 append(), pop()메소드로 구현 : 스택의 꼭대기에 항목을 넣으려면 append(), 스택의 꼭대기에서 값을 꺼내려면 명시적인 인덱스 없이 pop() 을 사용하면 된다.

# 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

 

노드(객체)의 컨테이너로 구현

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

 

 

큐(Queue)

한쪽 끝에서 삽입되고, 다른 한쪽 끝으로 삭제되는 선입선출(FIFO) 리스트

큐의 구분 : 입출력 순서/처리 방법에 따라 달라짐                  
- 일반 큐 : 삽입된 순서에 따라 삭제됨
   FIFO : 선입선출 (가장 일반적임)
   FILO : 선입후출
   LIFO : 후입선출
- 우선순위 큐 : 임의 순서로 삽입되나(입력/추가), 일정 순서로 삭제됨(출력/제거)

입력은 임의 순서이나, 출력은 반드시 일정/정해준 순서를 갖음

큐의 동작

• enqueue : 큐에 자료 추가
• dequeue : 큐에서 자료 제거 및 반환
• peek : 큐 자료 접근(자료 제거가 아닌 반환 만)
• front : 처음/전단 자료Front
• is_empty() : 공백 큐 여부

 

큐 구현 방법
리스트의 insert()메소드를 써서도 구현이 가능하지만, 이는 모든 요소가 메모리에서 이동될 수 있으므로 비효율적이다.(O(n)). 두 개의 스택(두 개의 리스트)를 사용하면 효율적인 큐로 구현가능하다.

# 리스트의 insert()메소드를 이용해 구현한 큐

class Queue(object):
    def __init__(self):
        self.items = []
        
    def isEmpty(self):
        return not bool(self.items)
        
    def enqueue(self, item):
        self.items.insert(0, item)
        
    def dequeue(self):
        value = self.items.pop()
        if value is not None:
            return value
        else:
			print("Queue is empty.")

    def size(self):
        return len(self.items)
        
    def peek(self):
        if self.items:
            return self.items[-1]
        else:
            print("Queue is empty.")
            
    def __repr__(self):
        return repr(self.items)

# 두개의 스택(리스트)를 이용해 구현한 큐

class Queue(object):
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def _transfer(self):
        while self.in_stack:
        self.out_stack.append(self.in_stack.pop())

    def enqueue(self, item):
    	return self.in_stack.append(item)

    def dequeue(self):
        if not self.out_stack:
            self._transfer()
        if self.out_stack:
            return self.out_stack.pop()
        else:
            print("Queue is empty!")

    def size(self):
        return len(self.in_stack) + len(self.out_stack)

    def peek(self):
        if not self.out_stack:
            self._transfer()
        if self.out_stack:
            return self.out_stack[-1]
        else:
            print("Queue is empty!")

    def __repr__(self):
        if not self.out_stack:
            self._transfer()
        if self.out_stack:
            return repr(self.out_stack)
        else:
            print("Queue is empty!")

    def isEmpty(self):
        return not (bool(self.in_stack) or bool(self.out_stack))

 

노드(객체)의 컨테이너로 구현

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

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

        return False

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

        if self.is_empty():
            self.head = new_node
            self.tail = new_node
            return

        self.tail.next = new_node
        self.tail = new_node

    def dequeue(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

 

 

덱(Deque) - double ended queue

스택과 큐의 결합체로 양방향 큐이다. 양 끝에서 항목의 CRUD 가능

 

덱의 동작

• append : 오른쪽에 요소를 추가
• pop : 오른쪽 요소를 삭제
• popleft : 왼쪽 요소를 삭제
• appendleft : 왼쪽에 요소를 추가

 

덱 구현 방법

리스트의 insert()메소드를 이용해 구현한 큐를 바탕으로 구현

• 끝이 아닌 다른 위치에 있는 항목을 삽입하거나 제거할 때 비효율적이다.

from queue import Queueclass Deque(Queue):
    def enqueue_back(self, item):
        self.items.append(item)

    def dequeue_front(self):
        value = self.items.pop(0)
        if value is not None:
            return value
        else:
            print("Deque is empty.")

 

collections 패키지의 deque 모듈 이용해 구현

• deque 모듈은 동적 배열이 아닌 이중 연결 리스트를 기반으로 한다.
• 덱의 크기 지정가능 ex) q = deque(maxlen=4)

>>>from collections import deque
>>>q = deque(["버피", "잰더", "윌로"])
>>> q
deque(['버피', '잰더', '윌로'])
>>> q.append("자일스")
>>> q
deque(['버피', '잰더', '윌로', '자일스'])
>>> q.popleft()
'버피'
>>> q.pop()
'자일스'
>>> q
deque(['잰더', '윌로'])
>>> q.appendleft('엔젤')
>>> q
deque(['엔젤', '잰더', '윌로'])