Stack
LIFO(Last In First Out)로 후입선출이라는 구조적 특징을 가져서 한쪽 끝에서만 자료를 넣고 빼는 자료구조이고, 데이터를 넣은 순서를 이용해야될 경우 필요하다.
-
자료가 추가될 때 마지막 자료 위로 쌓이고, 마지막 자료부터 먼저 나오게 된다.
=> 최상단에서만 데이터의 삽입 및 삭제가 이뤄진다. -
함수가 실행되고 값이 반환된다면 Stack에서 제거된다. (Call Stack)
-
Call Stack이 가득 차게 된다면 Stack overflow Error가 발생하게 된다.
-
JS - push(), pop()을 이용하여 구현할 수 있다. (Python - append(), pop())
-
웹 브라우저 방문기록, 실행 취소 등 많은 곳에서 이용된다.
-
삽입 및 삭제에는 O(1), 검색에는 O(N) 소요된다.
Stack 구현
class Node:
def __init__(self, item, next=None):
self.item = item
self.next = next
# Linked List로 구현한 스택이다.
class Stack:
def __init__(self):
self.top = None
def push(self, item):
self.top = Node(item, self.top)
def pop(self):
if self.is_empty():
print("Stack is empty!")
return None
top = self.top
self.top = self.top.next
return top.item
def peek(self):
if self.is_empty():
print("Stack is empty!")
return None
return self.top.item
def is_empty(self):
return self.top is None
# python list기능으로 구현한 스택이다.
class Stack2:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if self.is_empty():
print("Stack is empty!")
return None
return self.stack.pop()
def peek(self):
if self.is_empty():
print("Stack is empty!")
return None
return self.stack[-1]
def is_empty(self):
return not self.stack
Queue
Rear에서 입력되고 반대편 Front에서 출력이 되는 FIFO(First In First Out) 자료구조로 순서대로 처리되야 하는일에 유용하다.
-
삽입 연산을 Enqueue(rear), 삭제 연산을 Dequeue(front)라고 부른다.
-
JS에서 비동기 함수가 이벤트나 특정 시점이 되었을때 넣어지는 곳이다.
-
데이터가 입력된 시간 순서대로 처리해야될 경우 많이 이용된다.
-
막대 모양의 선형 Queue 원형으로 연결된 환형 Queue가 있다.
-
unshift(), shift()로 구현할 수 있다. (Python - insert(0,val), pop(0))
-
삽입 및 삭제에는 O(1), 검색에는 O(N) 소요된다.
Queue 구현
class Node:
def __init__(self, item, next=None):
self.item = item
self.next = next
# Linked List로 구현한 큐다.
class Queue:
def __init__(self):
self.front = None
def enqueue(self, item):
if not self.front:
self.front = Node(item)
return
node = self.front
while node.next:
node = node.next
node.next = Node(item)
def dequeue(self):
if self.is_empty():
print("Queue is empty!")
return None
node = self.front
self.front = node.next
return node.item
def peek(self):
if self.is_empty():
print("Queue is empty!")
return None
return self.front.item
def is_empty(self):
return self.front is None
# Python list 기능으로 구현한 큐다.
class Queue2:
def __init__(self):
self.queue = []
def enqueue(self, item):
self.queue.append(item)
def dequeue(self):
if self.is_empty():
print("Queue is empty!")
return None
front = self.queue[0]
self.queue = self.queue[1:]
return front
def peek(self):
if self.is_empty():
print("Queue is empty!")
return None
return self.queue[0]
def is_empty(self):
return not self.queueReference
요리사에서 프론트엔드 개발자를 준비하는중 입니다.