Doubly Linked Lists, Stacks

Doubly Linked Lists

Linked List의 한계점 : prev()를 하면 O(n) 시간이 걸린다.

 

-> pointer를 두 개 만들자!

 

앞 객체를 가리키는 포인터가 존재한다

기존의 Linked List에서는 head만 null을 가지고 있었지만, Doubly Linked Lists는 tail도 null이다.

 

tail이 있으면 boundary condition을 check하는데 편하다(코딩하기 편하다).

단점으로는 additional storage를 사용하게 된다.

 

 

 

Stacks

LIFO : Last In, First Out

-> 최근에 추가된 element가 제거될때 먼저 제거된다.

 

기본적인 Notation은 PUSH, POP, TOP이 있다.

 

PUSH : element 하나를 추가한다.

POP : stack에 있는 element들 중 가장 최근에 추가한 element를 제거한다.

TOP : stack에 있는 element들 중 가장 최근에 추가한 element를 반환한다.

 

 

 

Array-Based Stack

Array-Based Stack

 

Array를 바탕으로 한 Stack이다.

 

이때 Stack은 element들이 들어올 수 있는 충분한 공간을 확보해야 한다.

 

그래서 element들이 적게 들어왔을 경우 공간이 노는 경우가 생기기도 한다.

 

또 확보한 공간보다 더 많은 element가 들어왔을 경우, 새로운 더 큰 Array를 만들어 stack에 있는 element들을 옮기고 element를 추가해야 한다.

이 경우 PUSH를 할 때 O(n)이 걸리게 된다(기존에 있는 원소들을 옮겨야 하므로).

이 경우를 제외한다면 PUSH, POP, TOP 전부 O(1) 시간이 걸린다.

 

Linked Stack

Linked List를 이용하여 Stack을 구현한 것이다.

 

Array-based stack과 비교할 때 pointer를 저장할 추가적인 공간이 필요하다.

 

대신 Array-based stack과 다르게 worst case일때도 PUSH, POP, TOP 전부 O(1) 시간이 걸린다.

 

 

 

Stack의 사용 사례

1. java compiler가 code를 translation할 때 post-fix notation을 사용하는데 이때 stack 구조를 사용한다.

-> 기존에 우리가 사용하는 것은 중위 표기법이다. 바꾸는 방법은 다음과 같다.

(1)숫자가 나오면 그대로 출력한다.

(2) (,*,/가 나오면 stack에 push한다

(3) +와-연산자가 나오면 여는 괄호가 나올때까지 stack을 pop하여 출력한다. 여는 괄호가 없다면 stack의 끝까지 pop하여 출력하고 그 후 연산자를 stack에 push한다.

(4) 닫는 괄호가 나오면 여는 괄호가 나올때까지 pop하여 출력한다.

 

2. Browser에서 뒤로가기를 사용할 때 Stack을 사용한다(최근에 사용한 것 부터 사용하니까)

 

3. 하노이문제

 

 

 

출처 : 서울대학교 컴퓨터공학부 강유 교수님 자료구조 수업