stack & queue

stack

LIFO (Last In First Out). 마지막으로 들어온 데이터가 가장 먼저 나가는 방식

ref) Data Structure: Stack and Queue

 

python 으로 간단한 stack 예제를 만들어보자.

class Stack:
    def __init__(self):
        self.state = []

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

    def pop(self): # 하나씩 꺼내고 꺼낸 값을 리턴한다.
        return self.state.pop()

    def getPeak(self): # 스택의 최상위 값을 리턴한다.
        return self.state[-1]

    def empty(self):
        if len(self.state) == 0:
            return True
        return False


st = Stack()
st.push(1)
st.push(2)
st.push(3)
st.push(4) # 1~4 를 차례대로 push 한다.
print(st.state) # [1, 2, 3, 4]
print(st.pop()) # 4 return 후 제거 
print(st.pop()) # 3 return 후 제거
print(st.getPeak()) # 1 출력
print(st.empty()) # False ... st.state = [1, 2]

 

Queue

FIFO (First In First Out). 처음으로 들어온 데이터가 가장 먼저 나가는 방식으로, 입구와 출구가 정해져 있는 작은 통로라고 생각하면 된다. 들어오는 곳을 enqueue, 나가는 곳을 dequeue 라 한다. 비동기처리에 많이 쓰인다.

 

ref) Data Structure: Stack and Queue

list queue

별도의 import 없이 간단한 queue 예제를 만들어보자.
insert 없이 append 로도 만들 수 있다. 이 경우 dequeue 의 인덱스 값을 변경해주어야 한다. 다만 위의 그림처럼, 들어온 순서대로 표기되지 않으므로 insert 를 사용하였다.

class Queue:
    def __init__(self):
        self.state = []

    def enqueue(self, data):
        self.state.insert(0, data)

    def dequeue(self): # 먼저 들어온게 먼저 나간다.
        return self.state.pop(-1)

    def getFront(self): # 먼저 들어온 값을 출력한다.
        return self.state[-1]

    def empty(self):
        if self.state == []:
            return True
        return False

q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.state) # [3, 2, 1]
print(q.dequeue()) # 1 이 return 된 후 제거된다.
print(q.state) # [3, 2]
print(q.getFront()) # 2가 return 된다.
print(q.empty()) # 비어있지 않으므로 False

내장함수 queue

queue.Queue(size) 의 형식으로 쓰인다. size 를 비워두면 메모리의 범위 내에서 무한하다.
사용된 명령어의 출처는 공식문서이다.

import queue

q = queue.Queue(4)

q.put(1)
q.put(2)
q.put(3)
print(q.qsize()) # 3개가 들어있으므로 3 출력
print(q.get()) # 1을 제거하면서 출력
print(q.empty()) # False 출력
print(q.full()) # False 출력 = size 가 4 인데 3이 들어있으므로.

queue.PriorityQueue

우선순위 queue 객체를 생성한다. (priority, value)의 튜플로 입력할 수 있으며, priority 가 작을수록 우선순위가 높다.

import queue

q = queue.PriorityQueue()

q.put((15, '일'))
q.put((10, '이등'))
q.put((5, '삼등'))
print(q.qsize()) # 3
print(q.get()) # (5, '삼등') 을 제거하면서 출력. priority 가 가장 작다.
print(q.qsize()) # 2

collection deque

collection 모듈은 파이썬의 범용 내장 컨테이너 dict, list, set 및 tuple에 대한 대안을 제공하는 특수 컨테이너 데이터형을 구현한다.
collection.deque 는 double-ended queue 의 줄임말로, 양방향에서 데이터를 처리할 수 있는 queue형 자료구조를 의미한다.

ref) Implementation of Deque using circular array

 

deque는 stack과 queue를 일반화 한 것으로, 양쪽 끝에서의 append와 pop에 대해 최적화된 연산 속도를 제공한다.

list 도 deque 와 유사한 연산을 지원하지만, list 의 경우 빠른 고정 길이 연산에 최적화되어 있어 하부 데이터 표현의 크기와 위치를 모두 변경하는 pop(0)과 insert(0, v) 연산에 대해 deque 보다 더 메모리 비용을 소모한다. 따라서 dequ는 in/out이 빈번한 알고리즘에서 list 보다 월등한 속도를 자랑한다.

deque 객체는 다음과 같은 method 들을 지원한다. 출처는 공식문서이다.

• deque.append(item): item을 데크의 오른쪽 끝에 삽입한다.
• deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입한다.
• deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
• deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
• deque.extend(array): 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가한다.
• deque.extendleft(array): 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가한다.
• deque.remove(item): item을 데크에서 찾아 삭제한다.
• deque.rotate(num): 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).

from collections import deque

deq = deque()

deq.append(1)
deq.append(2)
deq.appendleft(3)
print(deq) # deque([3, 1, 2])
deq.pop()
print(deq) # deque([3, 1])
deq.popleft()
print(deq) # deque([1])
deq.extend([4, 5]) 
print(deq) # deque([1, 4, 5])
deq.rotate(1)
print(deq) # deque([5, 1, 4]) 145 에서 오른쪽으로 회전하여 514
deq.rotate(2)
print(deq) # deque([1, 4, 5]) 514에서 회전 415, 415 에서 회전 145
deq.rotate(-1) 
print(deq) # deque([4, 5, 1]) 145 에서 왼쪽으로 회전하여 451