스택과 큐

스택(stack)

1. 자료를 하나씩 쌓아 올린 형태로 가장 먼저 입력된 데이터는 맨 아래에 놓이고 그다음 입력되는 데이터가 그 위에 쌓이는 구조

2. 스택에서 입.출력이 이루어지는 부분을 상단(top)이라고 하고 반대쪽인 바닥 부분을 스택 하단(bottom)이라 함.

3. 가장 늦게 삽입한 원소가 가장 먼저 삭제되는 후입선출(LIFO: Last-In First-Out) 구조

4. 배열이나 연결 리스트로 구현 가능

5. 스택의 top에서 원소의 삽입과 삭제가 일어남. 

6. 스택의 삽입 연산은 push, 삭제 연산은 pop

 

시스탬 스택

1. 수행 중인 프로그램의 함수나 서브 프로그램들의 복귀 주소와 관련 정보들을 저장

2. 프로그램에서의 호출과 복귀에 따른 수행 순서를 관리하기 위한 스택

3. 함수 호출시 프로그램과 관련된 모든 정보(지역변수, 인수, 복귀 주소 등)를 시스템 스택에 활성 레코드의 형태로 저장

 

스택의 적용 분야

함수 찾기, 미로 찾기, 수식의 연산, 역순 문자열 출력

 

큐(queue) 

1.  한쪽 끝에서는 원소들의 삽입만 가능하고 반대쪽 끝에서는 원소들의 삭제만 가능

2. 가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 선입선출(FIFO: First-In First-Out) 구조

3. 큐의 rear에서 원소의 삽입이 일어남

4. 큐의 front에서 원소의 삭제가 일어남

5. 큐의 삽입 연산은 enqueue이고 삭제 연산은 dequeue

 

원형 큐(circular queue)

1. 큐를 원형으로 표현하는 방식

2. 큐의 처음과 끝을 연결해서 원형으로 구성하여 만든 것

3. 순차 큐의 이동 방식이 갖는 단점을 보완하기 위한 방법

 

큐의 적용 분야

CPU 스케줄링, 네트워크 프린터, 시뮬레이션 등의 대기열, 

컴퓨터 장치들 사이에서 시간이나 속도 차이를 극복하기 위한 임시 기억 장치인 버퍼(buffer)

 

데크(deque: double-ended queue)

1. 큐의 특수한 형태로 원소의 삽입과 삭제가 큐의 양쪽 끝에서 모두 허용되는 구조

2. 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐

3. 양쪽 끝에서 원소들의 삽입과 삭제에 제한을 둔 입력 제한 데크와 출력 제한 데크도 있음

 

입력 제한 데크 또는 스크롤(scroll)

새로운 원소의 삽입은 한쪽 끝에서만 가능하고 삭제는 양쪽에서 가능한 자료구조

 

출력 제한 데크 혹은 셀프(shelf)

특정 원소의 삭제는 한쪽 끝에서만 가능하고 삽입은 양쪽에서 가능한 자료구조0