[c++] 알고리즘 개념공부 :: 자료구조 - 스택, 큐, 덱

1. 스택
   1. 특징
   2. 용도
   3. 연산
      1. 삽입
      2. 삭제
      3. 접근
   4. 구현
2. 큐
   1. 용도
   2. 종류
   3. 연산
      1. 삽입
      2. 삭제
      3. 접근
   4. 구현
3. 우선순위 큐
4.  덱
   1. 용도
   2. 구현

 

스택

스택은 LIFO(Last-In First-Out), 즉 후입선출의 자료구조이다. 구조는 다음과 같은 형태이며, 접시처럼 쌓여서 이후에 삽입된 데이터가 먼저 빠져나가도록 되어있다.

top 변수는 가장 최근에 들어온 요소를 가리키며 스택이 비어있으면 -1이다.

 

특징

• LIFO
• 내부 요소를 확인할 방법이 pop 말고는 없다.

 

용도

입력의 역순이 필요할 때 스택을 주로 사용하며, 함수의 호출에서 복귀 주소를 기억하기 위해서 시스템 스택이 사용되기도 한다. 또한 괄호 검사, 계산기, 미로 탐색 등의 경우에 스택이 유용하게 사용된다.

계산기에서 중위 표기식(infix)을 후위 표기식(postfix)으로 만들어 컴퓨터가 계산하기 좋게 만들기도 한다.

(표기식 따로 정리)

 

연산

 

삽입

삽입 연산(push) 시 top에 요소 하나를 추가한 후, top을 한 칸 위로 올려준다.

 

삭제

삭제 연산(pop) 시 top에서 요소 하나를 뺀 후, top을 한 칸 아래로 내려준다.

 

접근

접근 연산은 없다. 다만 top의 요소를 꺼내지는 않고 확인만 하는 용도의 연산(peek)은 있다.

 

구현

스택은 배열 또는 연결리스트로 구현할 수 있다. 연결리스트로 구현 시 스택의 크기 제한이 없다고 볼 수 있으며, 기타 장단점은 '연결리스트' 파트에서 설명한 바와 같다.

C++에서는 import <stack>; 로 C++ STL 라이브러리를 불러온 후, stack<int> stk;과 같이 stack<자료형> 스택이름으로 변수를 생성한다.

STL : Standard Template Library (표준 템플릿 라이브러리)

 

자세한 설명은 STL을 따로 정리해서 올리겠다.

(STL 정리)

 

큐

큐는 FIFO(First-In First-Out), 즉 선입선출의 자료구조이다. 구조는 다음과 같으며, 대기열처럼 밀려서 먼저 삽입된 데이터가 먼저 빠져나가도록 되어있다.

삽입은 back에서 일어나며, 삭제는 front에서 발생한다.

 

용도

큐는 대기열을 구현할 때 자주 사용되므로, 통신에는 패킷의 모델링에 이용되고 시스템 소프트웨어에서는 버퍼링, 스케줄링, 캐시 등에 이용된다. 시뮬레이션을 위한 수학적 모델링에서 큐잉이론을 사용하기도 한다. 또한 이후에 나올 BFS(너비 우선탐색)에서도 사용된다.

 

종류

• 선형 큐

• 원형 큐

  오버플로우가 일어날 걱정이 없다.

• 우선순위 큐

  요소들의 우선순위를 매겨, 우선순위에 맞게 삽입 / 삭제 연산을 구현한 큐이다.

 

 

연산

 

삽입

삽입 연산(put == Enqueue) 시 back에 요소 하나를 추가한 후, back을 하나 뒤로 옮겨준다.

 

삭제

삭제 연산(get == Dequeue ) 시 front에서 요소 하나를 삭제한 후, front를 하나 뒤로 옮겨준다.

 

접근

peek 연산을 이용하여 front에서 요소를 확인할 수 있다.

 

 

구현

큐 또한 주로 배열로 구현되고, 연결리스트로도 구현할 수 있긴 하다. 연결리스트로 큐를 구현하였을 때는 굳이 환형 큐가 아니더라도 오버플로우가 발생할 걱정은 없다.

C++에서는 import <queue>; 로 C++ STL 라이브러리를 불러온 후,queue<int> q;과 같이 queue<자료형> 큐이름으로 변수를 생성한다.

STL : Standard Template Library (표준 템플릿 라이브러리)

자세한 설명은 STL을 따로 정리해서 올리겠다.

(STL 정리)

우선순위 큐

(해야함 => 자료구조 책)

 

덱

덱은 deque(double-ended queue)이며 front와 rear에서 삽입/삭제 연산이 모두 가능한 큐이다.

 

용도

보통 스케줄링에 사용하며, 우선순위 조절 시 큐나 스택보다 더 유용하다.

 

구현

일반적으로 이중 연결리스트를 이용하여 구현한다.

C++에서는 `import ;`로 C++ STL 라이브러리를 불러온 후, `deque dq;`와 같이 `deque<자료형> 큐이름;`으로 변수를 생성한다.

STL : Standard Template Library (표준 템플릿 라이브러리)

자세한 설명은 STL을 따로 정리해서 올리겠다.

(STL 정리)