[얼레벌레 공부하는 CS] 자료구조와 Stack, Queue

0️⃣ 자료구조란?

자료구조란, 컴퓨터가 데이터를 효과적으로 다룰 수 있게 도와주는 데이터 보관방법이자 데이터에 관한 연산의 총체를 일컫는다.

이런 자료구조는 크게 두 가지로 나눌 수 있는데 단순자료구조와 복합자료구조로 나눌 수 있다.

 

1. 단순자료구조 (Primitive)
   • 프로그램에서 기본적으로 지원하는 자료형으로, 언어별로 상이하다.
   • ex) String, int, double, boolean...
2. 복합자료구조 (Non-primitive)
   • 단순자료구조를 기반으로 만들어낸 자료구조로 선형, 비선형으로 나뉜다.
     • 선형(linear) :  데이터 요소를 순차적으로 연결하고, 데이터 간의 관계는 1:1 구조를 가진다.
       • ex) Array, Stack, Queue
     • 비선형(non-linear) : 데이터 요소를 비순차적으로 연결하여 보다 복잡하고 계층구조를 가진다. 데이터 간의 관계는 1:N 또는 N/M 의 형태를 형성한다.
       • ex) Tree, Graph

💡 자료형이란?
 : 컴파일러 또는 인터프리터에게 프로그래머가 데이터를 어떻게 사용할지 알려주는 일종의 데이터 속성을 말한다. (Attribute)
  자료구조에 비해 훨씬 구체적이며, 기본적으로 제공되는 원시 자료형 뿐만 아니라 해당 언어가 지원하는 모든 자료형이 포함 된다.

1️⃣ Stack

Stack의 사전적 정의는 "쌓아올리다." 이다. 그 말 그대로 차곡차곡 쌓아올리는 데이터 구조를 가지고 있다.

Stack 구조

• 후입선출 (LIFO, Last-In-First-Out)
• 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다.
• 정해진 방향으로만 데이터를 쌓을 수 있으며, top으로 정한 곳에서만 접근이 가능하다.
• 삽입 연산은 'push', 삭제 연산은 'pop' 이라고 부른다.

2️⃣ Queue

Queue의 사전적 정의는 "줄을 서다."이다. 줄을 서는 것처럼 순차적으로 처리된다는 특징을 가지고 있다.

 

1. Linear Queue (선형 큐)

Linear Queue 구조

• 선입선출 (FIFO, First-In-First-Out)
• 한 쪽 끝에선 삽입, 반대쪽 끝에선 삭제하여 양방향에서 접근 및 작업이 가능하다.
• 삽입이 수행되는 방향은 Front, 삭제가 수행되는 방향은 Rear로 지칭한다.
• 삽입 연산은 'Enqueue', 삭제 연산은 'Dequeue'라고 부른다.

2. Priority Queue (우선순위 큐)

Priority Queue 구조

• 우선순위 큐의 각 요소는 값과 우선순위, 총 2개의 데이터가 있다.
• 우선순위가 높을 수록 먼저 삭제 되고 우선순위가 같을 경우 선형 큐와 동일하게 삽입 순서에 따라 삭제된다.
• 삽입, 삭제 시 우선순위에 따라 요소들을 재정렬 해야한다.

3. Circular Queue (원형 큐)

Circular Queue 구조

• 선형 큐의 단점을 보완하기 위해 나타난 큐다.
• 끝과 시작이 연결되어 있어 선형 큐와 달리 낭비하는 공간이 없다.
• 선형 큐는 데이터를 삽입,삭제 해도 나머지 데이터가 이동하지 않기 때문에 언젠가 Rear가 큐의 마지막 index를 가리키게 될 수 밖에 없다. 때문에 앞의 빈공간 활용이 어려워 현재 요소를 앞으로 재배치 하는 별도의 작업이 필요하다.

선형 큐의 문제점

4. Deque (덱)

Deque

• 덱은 큐를 2개 겹쳐놓은 것과 같아, Double Endend Queue의 축약어 Deque이라고 일컫는다.
• 양쪽에서 삽입, 삭제가 모두 가능하다.
• 스택과 큐에서의 Rear는 다음 요소가 삽입될 위치이지만 덱의 Rear는 마지막 index에 있다.
• JavaScript의 배열 메소드로 구현되어있다.

3️⃣ Stack과 Queue 비교

	Stack	Queue
장점	효율적인 메모리 관리 가능 재귀 알고리즘에 활용 웹 브라우저나 모바일 어플리케이션 등 다양한 분야에서 간단히 사용 가능	선입선출 원칙에 따라 데이터를 처리하므로 중복이나 누락이 없음 시간복잡도가 O(1) 이므로 빠른 처리가 가능
단점	후입선출 특성 때문에 특정 문제를 해결하기 어려울 수 있음 크기가 고정되어 있지 않아 동적인 메모리를 재할당 하는 과정이 복잡함 ➡️ 이 경우, 시간 복잡도가 O(N)를 가짐	데이터가 쌓이면 메모리 사용량이 증가함 모든 데이터를 순회하며 특정값을 찾는 것은 비효율적임
사례	함수 호출 스택	프로세스 스케줄링 (우선순위 큐) 버퍼링, 캐시 구현 (선형큐)

 

❗ 출처

참고 사이트1 : https://velog.io/@stresszero/ds-algorithm

자료구조 & 알고리즘 관련 개념 정리

참고 사이트2 : https://velog.io/@sisofiy626/자료구조-2.-스택Stack과-큐Queue-덱Deque

[자료구조] 2. 스택(Stack)과 큐(Queue), 덱(Deque)

참고 사이트3 : https://elisha0103.tistory.com/21

Stack, Queue