[자료구조] 4. 원형 linked 리스트, Stack

• 원형 linked 리스트
• 스택 자료구조의 이해와 응용

 

원형 linked 리스트

기존 linked 리스트의 한계 → 데이터 삭제의 경우, prev를 알아야 했음

원형 linked 리스트는 첫 노드~ 마지막 노드를 연결한 자료구조

• 장점

** 마지막 노드를 참조하는 Last가 단방향 linked 리스트의 head 역할을 함

→ 마지막 노드와 첫 노드를 O(1) 시간에 접근 가능하다는 장점

→ 리스트가 Empty가 아니라면, 어떤 노드도 None을 갖지 않아 프로그램에서 None 조건 검사 안 해도 됨

• 단점

반대 방향으로 노드를 방문하기 쉽지 않음

양방향 원형 linked 리스트

양방향 linked 리스트에서 첫 노드와 마지막 노드를 이어 만든 자료구조

• 시간 복잡도 (단방향, 양방향, 원형 linked 리스트)
  • 삭입 및 삭제
  • O(1)
  • 탐색last부터 순차적으로 탐색..
  • O(n)

 

 

스택

 

쌓아놓은 더미

데이터를 위로 층층이 쌓아 올린 형태의 자료구조

→ 최상단 Top에서 원소 삽입 및 삭제 수행… 즉 상단으로만 입출력 가능

“선입후출”.. LIFO.. Last In First Out

단방향 linked 리스트..

• 스택 연산

push(data) : 상단에 데이터 추가

pop() : 상단의 데이터 삭제

재귀호출과 스택

재귀호출 : 함수의 정의부에서 자기 자신을 재귀적으로 호출하는 것

e.g., 피보나치, 팩토리얼

함수 최초로 호출 : 함수가 스택에 push 된 것으로 간주

함수 실행 종결 : 함수가 스택에서 pop 된 것으로 간주

class Stack:
	# 빈 리스트를 생성해서 빈 스택 생성.. item 저장됨
	def __init__(self):
		self.items = list()
	
	# 데이터 삽입
	def push(self, item):
		self.items.append(item
	
	# 데이터 삭제
	def pop(self):
		return self.items.pop()
	
	# 데이터 반환
	def peek(self):
		return self.items[-1]
		
	# 빈 스택인지 검사
	def isEmpty(self):
		return not self.items

스택의 응용

• 괄호 검사하기

[조건]

1. 왼쪽 괄호와 오른쪽 괄호의 개수가 같아야 하고
2. 서로 다른 타입의 괄호 쌍이 교차하면 안 되고
3. 왼쪽 괄호가 오른쪽 괄호보다 먼저 나와야 함