21.03.04

💡

Stack

속성
top	stack 최상위에 있는 데이터의 위치(index) 값. 새로 삽입되는 자료는 top이 가리키는 자료의 위에 쌓인다.

메소드
size	스택에 추가된 데이터의 크기(길이)를 리턴한다.
push	스택에 데이터를 추가한다.
pop	가장 나중에 추가된 데이터를 스택에서 삭제하고 삭제한 데이터를 리턴한다.
peek	가장 나중에 추가된 데이터를 확인한다.

• 쌓다, 포개다. 접시를 쌓아 놓은 형태와 비슷한 자료구조.

• 가장 마지막에 넣은 데이터가 가장 먼저 나온다. LIFO(Last In First OUt)
  먼저 들어간 자료일수록 나중에 나온다. FILO(First In Last Out)
  즉, 삽입과 삭제가 한쪽 끝에서만 일어난다. (바닥이 막힌 긴 관)

• 실사용 예제: 브라우저의 뒤로 가기, 앞으로 가기 / 주로 ctrl + Z로 사용하는 Undo 기능
  1) 새로운 페이지로 접속할 때 현재 페이지를 Prev Stack에 보관한다.
  2) 뒤로 가기 버튼을 눌렀을 때 현재 페이지를 Next Stack에 보관하고 Prev Stack에서 마지막에 보관된 페이지를 가져온다.
  3) 앞으로 가기 버튼을 눌렀을 때 현재 페이지를 Prev Stack에 보관하고 Next Stack에서 마지막에 보관된 페이지를 가져온다.

• Array의 push()로 데이터를 넣고, pop()으로 데이터를 꺼내는 형식으로 Stack과 유사하게 동작하도록 만들 수 있다.

• 배열로 구현했을 때의 단점

  • 스택의 크기가 정해져 스택의 용량을 초과하는 연산은 불가능해진다.

Queue

속성
front	Queue의 가장 앞에 있는 데이터의 위치(index) 값.
rear	Queue의 가장 뒤에 있는 데이터의 위치(index) 값. 새로 삽입되는 자료는 rear가 가리키는 자료의 뒤에 쌓인다.

메소드
size	큐에 추가된 데이터의 크기(길이)를 리턴한다.
enqueue	큐에 데이터를 추가한다.
dequeue	가장 먼저 추가된 데이터를 스택에서 삭제하고 삭제한 데이터를 리턴한다.

• 줄을 서서 기다리다, 대기 행렬. 티켓을 사려고 줄을 서서 기다리는 모습과 흡사한 자료구조.

• 먼저 들어간 자료가 먼저 나온다. FIFO(First In First Out)
  나중에 들어간 자료가 나중에 나온다. LILO(Last In Last Out)

• 실사용 예제: 프린터에서 문서를 인쇄 / 콜센터 고객 대기 시간 등 데이터가 입력된 시간 순서대로 처리되어야 할 때.
  컴퓨터 장치들 사이에서 자료(data)를 주고받을 때 각 장치들 사이에 존재하는 속도, 시간 차이를 극복하기 위한 임시 기억 장치로 Queue를 사용한다. 이걸 통틀어 버퍼(buffer)라고 한다. 보통 프린터는 속도가 느리고, 상대적으로 CPU는 속도가 빠르다.
  1) CPU가 빠른 속도로 인쇄 자료를 만든다.
  2) 인쇄 작업 Queue에 저장하고 다른 작업을 수행한다.
  3) 프린터가 인쇄 작업 Queue에서 자료를 가져가서 일정한 속도로 인쇄한다.

• Array의 push()로 데이터를 넣고, shift()로 데이터를 꺼내는 형식으로 Queue와 유사하게 동작하도록 만들 수 있다.

• 배열로 구현했을 때의 단점

  • 큐의 크기가 정해져 큐의 용량을 초과하는 연산은 불가능해진다.
  • 삽입 삭제 연산이 반복적으로 일어나면 front와 rear의 위치가 뒤로 점점 밀려나면서 앞에는 데이터가 들어올 수 있는 공간이 있지만 rear가 배열 인덱스의 마지막을 가리키고 있다면 데이터를 삽입할 수 없는 문제가 생긴다.
  • 위 문제점은 선형이 아닌 원형/환형 큐로 구현할 시에는 해결할 수 있다.

---

　

📝

유명한 Stack Overflow의 그 Stack을 배웠다! 이론만 읽었을 때는 어? 꽤 쉬운데? 했는데 실제로 알고리즘에 적용해 보니 음...ㅎㅎ 만만치 않다.