[테크 톡 - 21주차] 스택(Stack)과 큐(Queue)

📌 스택이란?

- 함수의 호출과 관계되는 임시데이터 (지역변수, 매개변수, 리턴 값 등)를 저장

- 클래스 내부에서 최상위 타입 배열인 Object 배열을 사용하여 데이터를 관리 

- LIFO (Last In First Out 후입선출) 구조
  : 후입선출 구조로 나중에 들어온 데이터가 가장 먼저 나가는 구조

- 선형 자료구조이다.
  ** 선형 자료구조 : 하나의 자료 뒤에 하나의 자료가 존재하는 형태의 자료구조.(1:1)
  ** 비선형 자료구조 : 하나의 자료 뒤에 여러개의 자료가 존재 (1:N) ex) 트리구조 등 

- 스택의 사용 예시 : 뒤로가기 (뒤로가기 키를 누르면 현재 수행되던 어플리케이션이 종료되고 직전에 수행되던 앱이 나타남), 되돌리기 (문서 편집기 등에서 되돌리기 실행 시최근 실행했던 작업 취소 됨.)

 

📌 스택의 구조

이름	설명
Top	가장 위에 있는 인덱스
Bottom	가자 아래에 있는 인덱스
Size	스택에 담겨있는 데이터 개수
Capacity	스택에 담을 수 있는 총 용량

 

위 그림에서 Top은 인덱스 4번의 데이터5가 되고
Bottom은 인덱스 0번이 Bottom이 되며,
Size는 5, Capacity는 6이 된다.

 

📌 스택의 작동 원리 

◾ 데이터를 넣을 때 (Push)

아래부터 차례대로 쌓인다.

- 데이터를 넣으면 스택의 가장 아래쪽부터 차례대로 차곡 차곡 쌓인다.
  스택의 가장 아래쪽은 높은 주소이기 때문에, 스택이 쌓일수록 높은 주소에서 낮은 주소로 자라나는 형태를 가지게 된다. 
  이렇게 가장 아래부터 데이터를 추가하는 이유는 커널 영역을 침범하지 않기 위해서이다.

커널 영역을 침범하지 않는다는 말은 무슨말인가?
  ** 메모리는 크게 커널 영역과 유저 영역으로 나뉘고 유저영역은 다시 스택 영역, 힙영역, 코드영역으로 나뉜다.
      → 커널 영역 : 운영체제의 핵심.  하나의 프로세스에 할당되는 총 메모리 공간 중에서 유저 영역을 제외한 나머지 영역
      → 유저 영역 : 프로그램이 동작하기 위해 사용되는 메모리 공간
  ** 여기서 스택영역은 커널영역을 침범 할 수 없는데, 높은주소에서 낮은 주소로 자라나게되면, 스택영역이 엄청 커지더라도 커널영역을 침범하지 않게 된다. 아래 그림으로 알아보자

커널이 가장 높은주소에 위치하고, 커널영역 이후에 스택영역이 위치해있다. 그리고 높은주소에서 낮은 주소로 자라난다.그렇기 때문에 스택영역이 커지더라도, 커널영역을 침범하지 않는다.

 

◾ 데이터를 뺄 때 (Pop)

위에서부터 차례대로 빠져나간다.

- 데이터를 빼면 쌓여있는 데이터 중 가장 위 (가장 나중에 들어온) 데이터부터 차례대로 빠져나간다.

 

📌 스택 연산 종류

연산	기능
pop()	스택에서 가장 위에 있는 항목을 꺼내면서 제거한다.
push()	스택의 가장 윗 부분에 추가한다.
peek()	스택에서 가장 위에 있는 항목을 꺼낸다
isEmpty()	스택이 비어있으면 True를 반환
isFull()	스택이 비어있으면 False를 반환

 

📌 큐(Queue)란?

- 한쪽 끝에서만 삽입이 이루어지고 다른 한쪽에서는 삭제연산만 이루어진다.

- FIFO (First in First Out 선입선출)  구조
 : 선입선출 구조로 먼저 들어온 데이터가 먼저 나간다.

- 데이터가 입력 된 시간 순서대로 처리해야 할 필요가 있을 때 사용한다.

- 데이터의 접근 / 삽입 / 삭제가 빠르지만 크기가 제한적이며, 중간에 위치한 데이터는 접근이 불가능하다.

- 고객센터 고객 대기시간 및 캐시(Chashe)구현, 프린터 인쇄 대기 등에 사용 된다. 

- 큐에서 데이터를 빼내면 가장 앞에 있던 값이 빠져나가고, front가 한칸씩 뒤로 밀려나게되면서 큐의 가용범위가 줄어든다는 문제점이 있다. 또한, 큐의 재사용 또한 불가능하다. 이를 해결하기 위해서는 불필요한 연산이 많아진다.

 

📌큐(Queue)의 구조

 

📌 큐(Queue)의 연산 종류

연산	기능
enQueue()	큐에 데이터를 넣는다.
deQueue()	큐에서 데이터를 뺀다. (삭제O)
isEmpty()	큐가 비어있는지 확인한다.
isFull()	큐가 꽉 차있는지 확인한다.
peek()	앞에 있는 원소를 반환한다 (삭제X)

 

 

💌 Reference

- https://cwjuns.tistory.com/18

스택이란? (Stack)

- https://velog.io/@alkwen0996/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack

[자료구조] | 스택(Stack)

- https://roi-data.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-4-%EC%8A%A4%ED%83%9DStack%EC%9D%B4%EB%9E%80-%EC%97%B0%EC%82%B0-%EA%B5%AC%ED%98%84%EB%B0%A9%EB%B2%95#google_vignette

[자료구조] 4. 스택(Stack)이란? / 연산, 구현방법

- https://donggu1105.tistory.com/163

[자료구조] 큐(Queue) 란? 한번에 쉽고 간단하게 이해하기!

- https://velog.io/@colorful8315/Queue%EB%9E%80-%EB%AC%B4%EC%97%87%EC%9D%B8%EA%B0%80

Queue란 무엇인가?