Stack / Queue

---

---

스택 ( Stack )

 

스택이란 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조이다.

스택에 저장된 자료는 선형 구조를 갖는다.

스택은 후입선출구조 (LIFO, Last in first Out) 구조를 갖는다

 

주요 연산

• push : 저장소에 자료를 저장한다.
• pop : 저장소에서 자료를 꺼낸다
• peek : 스택의 top에 있는 item(원소)를 반환한다 => 원소를 꺼내는 것이 아닌 확인하는 것

 

빈 스택에 원소 ABC를 차례로 삽입 후 한번 삭제하는 연산과정

 

---

중위 표기식, 후위 표기식 ( 스택 활용)

 

1. 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.

2. 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다.

3. 괄호를 제거한다.

 

예 ) A * B - C / D

1 단계 : ( (A * B) - ( c / D ) )

2 단계 : ( (A B) * (C D)/ ) -

3 단계 : AB*CD/-

 

후위 표기법의 수식을 스택을 이용하여 계산

1. 피연산자를 만나면 스택에 push한다.

2. 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고, 연산결과를 다시 스택에 push한다.

3. 수식이 끝나면, 마지막으로 스택을 pop하여 출력한다.

 

 

---

큐 ( Queue )

 

• 큐도 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조
• 선입선출구조(FIFO, First In First Out)

 

 

큐의 기본 연산

삽입 : enQueue ( offer(); )

삭제 : deQueue ( poll(); )

 

일반적으로

큐의 front는 맨앞을 가리키고, rear는 맨뒤요소를  가리킨다.

삽입 연산시 rear값은 증가하고, 삭제 연산시에도 front값은 증가한다.

---

< 큐의 삽입 연산 >

 

---

< 큐의 삭제 연산 >