스택(stack) : 자료의 입력과 출력을 한 곳(방향)으로 제한한 자료구조, 깊이우선탐색-DFS

함수의 콜스택에 쓰이고 문자열을 역순으로 출력할 때, 연산자 후위표기법등에 쓰인다.

LIFO ( Last In First Out ) : 후입선출 이라고 불린다.

스택에서 사용되는 함수로는 Push와 Pop가 있다. (Push : 자료넣기&입력, Pop : 자료빼기&삭제 )
변수는 Top (초기값 : -1 , 꼭데기 즉 가장 위의 변수를 가리키는 변수 )

임시데이터의 저장에 사용하기가 편하다.

프린터의 출력 처리나, 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 순서대로 처리해야할 필요가 있는

상황에 이용된다

  • 에러 자료가 없을 때 Pop을 한다면 자료가 없기에 뺄수없는데 이때 발생하는 Err를 “Stack Underflow”라고 한다.
    또한 반대로 스택의 크기, 즉 배열의 크기 이상의 자료를 Push 할 때도 자료를 넣을 수 없으므로 “Stack Overflow” Error가 발생한다.

  • Stack의 용도

    • 함수 호출의 순서를 제어
    • 인터럽트가 발생하여 복귀주소를 저장할 때
    • 후위 표기법으로 표현된 산술식 연산시
    • 부 프로그램 호출 시 복귀주소를 저장할 때
    • 0 주소지정방식 명령어의 자료 저장소
    • 재귀(Recursive) 프로그램의 순서를 제어
    • 컴파일러를 이용해 언어 번역 시

큐(queue) : 자료의 입력과 출력을 한 쪽 끝(front, rear)으로 제한한 자료구조, 너비우선탐색-BFS

FIFO(First In First Out)구조 put(), get(), 선입선출 이라고 불리며, 프로세스 처리, CPU 관리 에서 많이 사용된다.

컴퓨터 버퍼에서 주로 사용한다, 입력이 되었으나 처리를 하지 못할 때, 버퍼(큐)를 만들어 대기 시킨다.

일반적인 큐의 단점 : 속도가 빠른 장점이 있지만 크기가 제한되어 있다는점. 큐 오버플로우(큐가 꽉차서 더이상 들어갈수 없는 상태)가 발생한다, 수의 자료의 경우는 상관이 없지만 많은 데이터의 경우 연산에 많은 시간이 걸린다, 앞의 데이터가 pop 될 시 front가 뒤로 가 앞의 공간이 남아있게 된다, rear가 배열의 끝에 닿아있으면 자료가 꽉 차 있는 상태로 인식하기 때문에 앞공간이 비어도 끝까지 비기전까진 앞공간을 활용할수없다.

  • 원형(환형) 큐 : 배열의 마지막 인덱스에서 다음 인덱스로 넘어갈 때 ‘(index+1) % 배열의 사이즈’를 이용하여 OutOfBoundsException이 일어나지 않고 인덱스 0으로 순환되는 구조를 가집니다.
    • 원형 큐의 단점 : 메모리 공간은 잘 활용하나 배열로 구현되어 있기 때문에 큐의 크기가 제한되는 단점이 존재
  • 링크드리스트 큐 : 자료 반환은 큐의 제일 앞(front)에서만 가능하고 자료 추가는 큐의 제일 끝(rear)에서만 가능하다.
    • 링크드 리스트로 구현한 큐는 큐의 크기가 제한이 없고 삽입, 삭제가 편리하다.

  • 우선순위 큐 : 우선순위가 설정된 자료부터 먼저 사용한다.

  • 큐의 용도
    • 서비스의 순서를 기다리는 등 대기행렬의 업무처리
    • 운영체제의 작업 스케줄링

덱(deque) : 자료의 입력과 출력을 양 쪽 끝에서 가능하게 하는 자료구조.

  • 스크롤(scroll) : 입력이 한쪽 끝으로만 가능하도록 제한한 덱
  • 셸프(shelf) : 출력이 한쪽 끝으로만 가능하도록 제한한 덱
  • 정리
    • 스택은 자료의 입출력이 한방향에서만 가능한 것이다. 가장 마지막에 들어온것을 처음으로 꺼낼 수 있어 순서를 제어할 수 있다.
      임시 데이터의 저장에 사용하기 편하다. 큐는 입출력이 한쪽끝(front와 rear)로 제한한 자료구조이고 선입선출 데이터구조이다. rear가 배열의 끝에 있으면 꽉 찬상태로 인식하기때문에 효율성이 떨어지고 크기가 제한되어있는 문제가 있는데 이를 보완하기위해 원형큐, 링크드리스트큐등이 있다.