[ C.S 지식 정리 : 자료 구조 ] 자료구조 : 스택(Stack) & 큐(Queue)

 

 

 

 

 

[ C.S 지식 정리 : 자료 구조 ] 자료구조 : 스택(Stack) & 큐(Queue)

 

---

 

∇ CS지식 정리 _ 자료구조 : 스택(Stack) & 큐(Queue)

목  차

1. 스택(Stack)이란 무엇일까?
2. 큐(Queue)의 개념.

 

 

---

 

 

Ⅰ. 스택(Stack)이란 무엇일까?

---

 

후입선출

 

      ◇ 스택(Stack)은 "쌓다"라는 의미로, "데이터를 차곡차곡 쌓아 올린 형태의 자료구조" 입니다.

                 ++ 위 그림처럼, 데이터가 순서대로 쌓이며 '가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조' !

 

            ◎ '스택'은 정해진 방향으로만 쌓을 수 있으며, ' top으로 정한 곳을 통해서만 접근 ' 가능합니다.

                     -> 새로 삽입되는 자료는 top이 가리키는 가장 맨 위에 쌓이게 되며,

                                  자료를 삭제할 때도 top을 통해서 삭제가 가능합니다.

 

            ◎ '스택' 에서는 '삽입연산'을 'push',  '삭제연산'을 'pop' 이라고 하며,

                      이러한 스택의 구조를 '후입 선출'의 구조라고 하며,  LIFO(Last In First Out)이라고부릅니다. 

 

 

    ▣ 스택(Stack)의 사용 사례.

              - 웹 브라우저 방문기록(뒤로 가기)

              - 실행 취소(undo)

              - 역순 문자열 만들기

              - 후위 표기법 계산.

 

 

---

 

Ⅱ. 큐(Queue)의 개념.

---

 

선입선출

 

 

      ◇ 큐(Queue)는 스택(Stack)과 다르게, '먼저 들어온 것이 먼저 나가는 "선입선출" 구조로,

                 "FIFO(First In First Out)" 의 구조를 가지고 있습니다.

 

                ex)  먼저 들어온 차가 먼저 세차를 받는 것 으로 이해해보기.

 

 

      ◇ 삭제 연산이 수행되는 곳을 '프론트(front)', 삽입 연산이 이루어지는 곳은 '리어(rear)'로,

              FIFO 구조를 위해서 스택과 다르게

              큐의 한쪽 끝에는 삽입 작업이,  다른 한쪽에서는 삭제 작업이 나뉘어서 진행됩니다.

 

 

    ▣ 큐(Queue) 사용 사례.

              - 은행업무

              - 대기열 순서와 같은 우선순위의 작업 예약 등

              - 서비스 센터의 대기시간

              - 프로세스 관리.