스택(stack)
자료를 차곡차곡 쌓아 올린 형태의 자료구조
스택에 저장된 내용은 top 에서만 접근 가능 = top 의 위치에서만 원소를 삽입/삭제
- 먼저 삽입한 원소는 밑에 쌓이고, 나중에 삽입한 원소는 위에 쌓이는 구조
마지막에 삽입(Last in)한 원소는 맨 위에 쌓여있다가 가장 먼저 삭제(First out) : LIFO
* push : 삽입, pop : 삭제
시스템 스택
프로그램에서 호출과 복귀에 따른 수행 순서 관리
가장 마지막에 호출된 함수가 가장 먼저 실행 완료 후 복귀(후입선출)
함수 호출 발생 -> 호출 함수 수행에 필요한 변수, 수행 후 복귀할 주소 등의 정보를 스택에 저장 -> 시스템 스택에 삽입
함수 실행 종료 -> 시스템 스택의 top 원소 삭제하면서 프레임에 저장되어있던 복귀 주소로 복귀
큐(Queue)
삽입과 삭제의 위치가 제한되어있는 유한 순서 리스트
뒤에서는 삽입만, 앞에서는 삭제만 할 수 있는 구조
삽입 순서대로 원소가 나열됨
가장 먼저 삽입한(First in) 원소는 맨 앞에 있다가 가장 먼저 삭제(Fisrt out)됨 : FIFO (선입선출)
줄의 맨 앞 : 큐 프런트
줄의 맨 뒤 : 큐 리어
큐 리어에 데이터 삽입 : 큐 애드 enQueue
큐 프런트의 데이터 삭제 : 큐 리무브 deQueue
순차 큐의 문제점
순차 큐에 삽입과 삭제를 반복하면 front 와 rear 가 뒤로 밀리게 됨
1차원 리스트 크키가 n 이라고 할 때, 크기가 고정된 배열 특성상 rear = n - 1 상태가 되면 앞이 비어있더라도 포화상태로 인식
해결책
1) 저장된 원소들을 배열의 앞부분으로 이동시키기 -> 효율성 떨어짐
2) 원형 큐 : 1차원 배열을 사용하면서 논리적으로 배열의 처음과 끝이 연결되어있다고 가정하고 사용
원형 큐
원형 초기 공백 상태 front = rear = 0
공백 상태와 포화 상태를 구분하기 위해 front 가 있는 자리는 사용하지 않고 항상 빈자리로 둠
나머지연 산자 mod 를 사용해서 삽입/삭제함
삽입 : rear = (rear+1) mod n
삭제 : front = (front+1) mod n
덱
큐 두개 중 하나를 좌우로 뒤집어서 붙인 구조
큐의 양쪽 끝에서 삽입 연산과 삭제 연산을 수행할 수 있도록 확장한 자료구조