파이썬으로 구현하는 자료구조 요약 정리 - 배열(Array), 큐(Queue), Stack, Linked List
장점: 인덱스를 통한 직접 접근으로 빠름
단점: 데이터 추가 삭제에 공간 자원 소모 많음.
선입선출 FIFO
#라이브러리 이용
import queue
data_queue = queue.Queue()
data_queue.put(1) # 1
data_queue.put(2) # 1 - 2
data_queue.put(3) # 1 - 2 - 3
data_queue.get() # 1 출력
data_queue.get() # 2 출력
#문제에서 큐 구현
class Queue:
def __init__(self):
self.queue = []
def push(self, x):
self.queue.append(x)
def pop(self):
return self.queue.pop(0) if self.queue else -1
def size(self):
return len(self.queue)
def empty(self):
return 1 if not self.queue else 0
def front(self):
return self.queue[0] if self.queue else -1
def back(self):
return self.queue[-1] if self.queue else -1
LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조로 Stack과 동일하다.
import queue #라이브러리 활
data_queue = queue.LifoQueue()
data_queue.put(1) # 1
data_queue.put(2) # 2 - 1
data_queue.put(3) # 3 - 2 - 1
data_queue.get() # 3 출력
data_queue.get() # 2 출력
#내가 구현한 것
class Stack:
def __init__(self):
self.stack = []
def push(self, x):
self.stack.append(x)
def pop(self):
return self.stack.pop() if self.stack else -1
def size(self):
return len(self.stack)
def empty(self):
return 1 if not self.stack else 0
def top(self):
return self.stack[-1] if self.stack else -1
양방향 출입이 가능함.
class Deque:
def __init__(self):
self.deque = []
def push_front(self, x):
self.deque.insert(0,x)
def push_back(self, x):
self.deque.append(x)
def pop_front(self):
return self.deque.pop(0) if self.deque else -1
def pop_back(self):
return self.deque.pop(-1) if self.deque else -1
def size(self):
return len(self.deque)
def empty(self):
return 1 if not self.deque else 0
def front(self):
return self.deque[0] if self.deque else -1
def back(self):
return self.deque[-1] if self.deque else -1