Stack (based LinkedList) 실습

1. top = tail 노드

 

2. Class Node

- int data : 노드의 값

- Node* next : 다음노드 포인터

 

 

 

3. Class LinkedList

- Node* head

- Node* tail

 

4. LinkedList() : 리스트 생성자

- this->head = NULL

- this->tail = NULL

 

5. empty()

- 만약 head, teil 둘다 NULL 인 경우 1 반환

- 그외의 경우 0 반환

 

6. peek()

- tail->data 반환

7. append(data)

- 새로운 노드를 생성하여 data를 저장한다

- 만약 empty() 상태라면 head, tail을 새로운 노드로 저장한다

- 그외의 경우 tail->next에 새로운 노드를 저장한다

- tail을 새로운 노드로 저장한다

 

8. delete()

- 이전노드, 현재노드를 각각 head 값으로 설정한다

- 현재노드의 next 가 NULL이 아닐동안 이전노드, 현재노드를 옮긴다

- tail에 도달하면 현재노드의 값을 임시로 저장한다

- 이전노드의 next를 NULL로 설정한다

- tail을 이전노드로 저장한다

- 임시저장된 값을 반환한다

 

 

 

9. class Stack (based LinkedList)

- int n : 스택의 개수

- LinkedList* Stack : 스택에 쓰이는 LinkedList의 포인터

 

10. Stack() : 스택 생성자

- this->Stack = new LinkedList()

- this->n = 0

 

11. size()

- 스택의 개수인 n을 반환한다

 

12. empty()

- 스택이 비었는지 여부를 반환한다 (n == 0)

 

13. top()

- 스택의 상단값인 list의 peek()을 반환한다

 

14. push(val)

- 스택크기인 n을 증가시킨다

- 스택에 추가하기위해 list의 append(val) 해준다

 

15. pop()

- 스택이 비어있는 경우 -1을 반환한다

- 그외의 경우 크기 n을 감소시킨다

- list의 delete()를 반환한다

 

16. 스택의 응용 - 후위표기식 (연산자 우선순위 없음)

- 연산자를 피연산자(숫자) 뒤에 표기하는 방법 : (A*B) - (C/D) → AB*CD/-

- 1. 피연산자(숫자) -> 스택에 push 한다 

- 2. 연산자 -> 피연산자를 스택에서 pop하여 연산 후 스택에 push 한다

- 3. 수식이 끝나면 pop하여 출력한다