1. Stack & Queue (스택과 큐)

리액트와 리덕스에 치이다 보니

내일 있을 알고리즘 스터디공부를 이제야...

 

이번 알고리즘 공부는 스택과 큐를 공부하기로했다.

 

이번 공부를 하다가 자료구조와 알고리즘에 차이를

알게 되었다.

 

자료구조 : 데이터의 표현과 저장 방법을 의미

알고리즘 : 저장된 데이터를 처리하는 과정

 

자주쓰는 배열이 자료구조에 포함되어 있다고 생각하면 된다.

 

 

 

스택 (Stack)

스택은 push와 pop만 할 수 있으며,

실행이 되는 특정한 순서를 따르는 선형적 데이터 구조

즉, 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조.

 

 

스택(Stack)의 특징

• 스택 내부의 데이터는 top을 통해서만 접근할 수 있다.
  
  
• 스택에 데이터를 삽입할 때는, top위에 쌓게 된다. (push)
  
  
• 스택에서 데이터를 삭제할 때는, top에 위치한 데이터를 삭제 (pop)
  
  
• 가장 마지막에 삽입된 데이터가 가장 먼저 삭제되는 특징
  즉, 스택은 시간 순서에 따라 데이터가 쌓인다.
  
  
• 따라서 스택의 구조를 후입선출(LIFO, Last in First Out)구조라고 부른다.

여기서 순서는 두가지가 존재한다.

 

1. LIFO(Last in First Out) : 마지막에 들어온 데이터가 먼저 나가는 데이터 구조

2. FILO(First in Last Out) : 처음 들어온 데이터가 마지막에 나가는 데이터 구조

 

 

스택은 3가지의 기본 작업이 실행된다.

 

• Push : 스택 안으로 데이터를 넣는다. 만약 스택이 꽉찬 상태에서
  데이터를 더 넣으면 오버플로우 상태(Overflow condition)이라고 한다.
  
  
• Pop : 스택 안에 있는 데이터를 제거한다. 데이터는 넣은순서의 역순으로 빠진다.
  만약 비어있는 스택에서 데이터를 꺼내려고 할때를 언더플로우 상태(Underflow condition)이라 한다.
  
  
• Peek or Top : 스택의 꼭대기 요소(Top)를 반환
  Top이란 가장 최근(마지막)에 들어온 자료를 의미한다.

 

 

근데... 스택이 꽉찬다?? 그게 무슨말일까

 

스택은 크기를 고정해서 사용하기 때문에,
고정된 크기의 스택에 데이터를 계속 넣어서 넘치면
다른 메모리 영역을 침범하게 된다. 이것이 (StackOverFlow)이다.

 

 

하지만 여기서 배열과 스택을 명확하게 구분해야한다.

배열로 스택을 표현할 수 있지만 배열===스택이 아닌 것이다.

 

스택이라는 자료구조는 프로세스 4대요소 중 하나이며, 함수의 호출에 관여한다.

 -> 프로세스 4대 요소(스택, 힙, 데이터, 코드 영역)

더 들어가면 골치아프므로 일단 여기까지 프로세스를 알아보는걸로...

 

 

그럼 스택을 어디다가 사용할 수 있을까??

 

• 웹 브라우저 방문기록 (뒤로 가기)
  가장 마지막에 열린 페이지부터 다시 보여줌
  
  
• 실행 취소 (undo)
  가장 마지막에 실행된 것부터 실행을 취소
  
  
• 역순 문자열 만들기
  가장 마지막에 입력된 문자부터 출력
  
  
• 후위 표기법 계산
  
  
• 수식의 괄호 검사
  연산자 우선순위 표현을 위한 괄호 검사

 

자바스크립트에서의 '콜 스택' 을 생각해보면

자바스크립트와 관련된 예시를 들 수 있다.

콜 스택은 실행 컨텍스트가 쌓이는 영역인데

저번에 작성해놓은 포스팅을 보면 어떤놈인지 알 것 이다.

 

2. 실행 컨텍스트, 렉시컬 환경 내용정리

 

---

 

큐 (Queue)

큐(Queue)는 "줄을 서서 기다린다."라는 의미이다.

따라서, 큐(Queue)는 먼저 들어온게 먼저 나가는 선입선출방식이기 때문에

이점이 스택과 다르다.

하지만, 큐는 스택과 같은 선형적 구조

 

 

큐(Queue)의 특징

• 스택과 다르게 큐는 삽입, 삭제가 다른 방향으로 이루어진다.
  
  
• 삭제 연산만 수행되는 곳을 프론트(Front), 삽입 연산만 수행되는 곳을 리어(rear)라고 한다.
  프론트(Front)에서 이루어지는 삭제 연산을 디큐(Dequeue)라고 하고,
  리어(rear)에서 이루어지는 삽입 연산을 인큐(Enqueue)라고 한다.
  
  
• 즉, 큐(Queue)는 가장 먼저 삽입된 데이터가 가장 먼저 삭제된다.
  
  
• 큐의 구조를 선입선출(FIFO, First In First Out)구조 라고한다.

꼭 헷갈리지 않게 기억하자!!
스택은 가장 마지막에 쌓인 데이터를 제거하고,
큐는 가장 앞에 추가된 데이터를 제거한다.

 

 

큐(Queue)의 동작

 

• Enqueue : 큐에 데이터를 추가한다. 만약 큐가 꽉차면,
  오버플로우 상태(Overflow condition)가 된다.
  
  
• Dequeue : 큐에서 데이터를 제거한다. 데이터는 들어온 순서대로 제거된다.
  만약 큐가 비어져있다면, 언더플로우 상태(Underflow condition)이 된다.
  
  
• Front : 큐의 앞부분의 데이터를 가진다.
  
  
• Rear : 큐의 뒷부분의 데이터를 가진다.

 

큐의 동작원리를 쉽게 예를 들어 설명을하면,

 

아주 맛있는 맛집에 사람들이 줄을 서있다.

맛집에 자리가 생기면 먼저 온사람부터 줄에서 빠져 식당으로 들어간다.

그리고 새로온 사람들은 줄의 맨뒤로 줄을 서게 된다.

 

여기서 줄을 큐(Queue)라고 할 수 있고,

새로온 사람들이 뒤로 줄을 서는건 (Enqueue)라고 할 수 있고,

먼저 온사람부터 줄에서 빠져 식당으로 들어가는건 (Dequeue)라고 할 수 있다.

 

 

그럼 큐(Queue)는 어디다가 쓸 수 있을까??

 

• 데이터가 입력된 순서에 따라 처리되어야 할 때 사용
  
  
• 프로세스 관리
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
  
  
• 캐시(Cache) 구현

 

 

큐의 종류

 

큐를 구현하기 위해서는 front, rear 이 두가지 지표를 추적해야한다.

 

만약, 우리가 심플하게 front와 rear의 지표를 증가시키면,
front가 rear에 도달할 수도 있기 때문에 문제가 될 수 있다.

이걸 해결하기 위해 2가지의 큐(Queue)로 원형 큐, 우선순위 큐가 있다

 

 

1. 원형 큐(circular Queue)

 

front와 rear가 연결되어 있다.

예를 들어, 원래의 1,2,3의 큐에서는

3에서 끝나지만, 원형 큐는 rear인 3에서

다시 front인 1로 넘어가는 것이다.

 

출처 : geeksforgeeks

 

2. 우선순위 큐

 

우선순위 큐는 Enqueue와 Dequeue는 같지만,

Enqueue할 때 , 제일 뒤에 넣는 것이 아니라

우선순위를 따져 데이터를 넣는 것이다.

우선순위는 프로그래머가 직접 정하는 것이다.

 

다만, 우선순위 큐는 일반 큐와 같이 구현하면 데이터를 삽입하기

힘들다는 단점이 있기 때문에

주로 힙(heap)이라는 자료구조를 사용해서 구한다.

 

 

멀리서 듣기만하고 스택이라고는 콜스택밖에 몰라서

언젠가 해야지... 했던 자료구조의 기초중의 기초

스택 / 큐를 공부해봤는데,

자료구조 하나하나 알아가면서 자료구조를 통한 알고리즘도

열심히 공부해보자!

 

 

 

 

 

 

참고

 

[Algorithm] Stack & Queue: 스택과 큐에 대해 알아보자!

 

[자료구조] Stack 과 Queue