[자료구조] 스택(Stack) 과 큐(Queue)

스택(Stack) 

 

스택(Stack)이란?

한 쪽 끝에서만 자료를 넣고 뺄 수 있는  후입 선출의 구조로, LIFO(Last In First Out) 형식의 자료 구조

스택(Stack)의 연산

스택(Stack)는 LIFO(Last In First Out) 를 따른다. 즉, 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다. (입구와 출구가 동일지점으로 데이터의 삽입과 삭제가 한방향에서만 이루어진다.)

• push(item): 삽입연산. item 하나를 스택의 가장 윗 부분에 추가한다.
• pop(): 삭제 연산. 스택에서 가장 위에 있는 항목을 제거한다.
• top : 삽입과 삭제가 일어나는 위치를 Top이라고 한다.
• peek(): 스택의 가장 위에 있는 항목을 반환한다.
• isEmpty(): 스택이 비어 있을 때에 true를 반환한다.

 

스택(Stack)의 사용사례

• 웹브라우저 방문기록 (뒤로가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
• 실행 취소 : 가장 나중에 실행된 것부터 실행취소
• 역순 문자열 만들기 :가장 나중에 입력된 문자부터 출력
• 후위 표기법 계산
• 안드로이드의 액티비티
• 수식의 괄호 검사 : 연산자 우선순위 표현을 위한 괄호 검사

 

 

큐(Queue)

 

큐(Queue) 란?

먼저 들어온 것이 먼저 나가는 선입선출로 FIFO(First In First Out) 형식의 자료구조

 

큐(Queue) 의 연산

규에서 데이터의 삽입과 삭제 연산을 주로 enQueue와 deQueue라 칭한다. 

스택과 다르게 입구와 출구가 각각 나위어져 있다. 

이때 출구는 머리(Front)로 정해 삭제연산만 수행하고, 입구는 꼬리(Rear)로 정해 삽입연산만 수행한다. 

• enqueue(): 꼬리, 리어(rear)에서 이루어지는 삽입연산.
• dequeue(): 머리, 프론트(Front)에서 이루어지는 삭제 연산.\

 

큐(Queue)의 사용사례

큐는 주로 데이터가 입력된 시간 순서대로 처리해야할 필요가 있는 상황에 이용한다. 

• 은행업무
• 대기열 순서와 같은 우선순위의 작업예약
• 서비스 센터의 대기시간
• 프로세스 관리
• 너비 우선탐색(BFS, Breadth First Search) 구현
• 캐시(Cache) 구현