Ch3. 스택과 큐
코딩 인터뷰 완전 분석(저 : 게일 라크만 맥도웰) 참조
스택 구현하기
스택은 데이터를 쌓아올리는 자료구조이다. 스택은 LIFO(Last-In-First-Out)에 따라 자료를 배열한다.
즉, 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이 된다.
스택에는 다음과 같은 연산이 존재한다.
pop(): 스택에서 가장 위에 있는 항목을 제거한다.
push(item): item을 스택의 가장 위에 추가한다.
peek(): 스택의 가장 위에 있는 항목을 반환한다.
isEmpty(): 스택이 비어있을 때에 True를 반환한다.
파이썬을 통해 스택을 아래와 같이 구현할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28class Stack():
def __init__(self):
self.stack = []
def __len__(self):
return len(self.stack)
def isempty(self):
if self.stack:
return False
else:
return True
def push(self, num):
self.stack.append(num)
def pop(self):
if self.stack:
return self.stack.pop()
else:
raise Exception("stack is empty")
def peek(self):
if self.stack:
return self.stack[-1]
else:
raise Exception("stack is empty")
큐 구현하기
큐는 FIFO(First-In-First-Out)에 따라 자료를 배열한다.
즉, 큐에 저장되는 항목들은 추가되는 순서대로 제거된다.
큐에는 다음과 같은 연산이 존재한다.
add(item): item을 리스트의 끝부분에 추가한다.
remove(item): 리스트의 첫 번쨰 항목을 제거한다.
peek(): 큐에서 가장 위에 있는 항목을 반환한다.
isEmpty(): 큐가 비어있을 때 True를 반환한다.
파이썬을 통해 아래와 같이 큐를 구현할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27class Queue():
def __init__(self):
self.queue = []
def push(self, num):
self.queue.append(num)
def pop(self):
if self.queue:
item = self.queue[0]
self.queue = self.queue[1:]
return item
else:
raise Exception("Queue is empty")
def peek(self):
if self.queue:
return self.queue[0]
else:
raise Exception("Queue is empty")
def isEmpty(self):
if not self.queue:
return True
else:
return False