3. 스택 (Stack) & 큐 (Queue)

본 게시글은 책 : 면접을 위한 CS 전공지식 노트 (출판사 : 길벗, 주홍철 지음) 을 참조하여 작성하였습니다. + 구글링

---

*선형 자료 구조 : 요소가 일렬로 나열되있는 자료구조

 

◆  스택 (Stack)

- 스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오게 되는 자료구조

- Last in First Out (LIFO) 구조

- 재귀적인 함수 or 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰임

-  삽입 및 삭제에 O(1), 탐색에 O(n)

#include <iostream>
#include <stack>

using namespace std;

int main() {

stack<int> stackSample;
	
    // 0~9까지 차례대로 삽입
    for(int i =0; i < 10; i++)
    	stackSample.push(i);
    
    // 9~0 까지 역순으로 출력 (Last in First Out)
    for(int i =0; i < 10; i++) {
    	cout << stk.top() << " ";		// 마지막 원소 출력
        stk.pop(); 					// 마지막 원소 제거
    }
    
    
	return 0;
}

 

---

◆  큐 (Queue)

- 큐는 가장 먼저 삽입된 데이터가 가장 먼저 나오게되는 자료구조

- First in First Out (FIFO) 구조

- CPU 작업을 기다리는 프로세스, 스레드 행렬 or 네트워크 접속을 기다리는 행렬 BFS 등에 사용

-  삽입 및 삭제에 O(1), 탐색에 O(n)

- BFS에 큐 사용 문제 예시 :

  ex)  https://heih.tistory.com/25

- 큐 구조 예시 :

#include <iostream>
#include <queue>

using namespace std;

int main() {
	queue<int> queueSample;
    
    // 0~ 9까지 삽입
    for(int i = 0; i < 9; i++)
    	queueSample.push(i);
        
    // 0~ 9까지 출력 ( First in First out)
    for(int i = 0; i < 9; i++) {
    	q.front(i);
        q.pop();
    }


	return 0;
}

---

무언가 같은 책인데 앞에서는 javascript로 보여주고 뒤에서는 C++로 보여주고 있는데 예제 코드만 봐서는

왠지 모르게 각자 다른 사람이 작업한 느낌이 드네요. 이 책에 나오는 C++ 예제는 가독성 및 연관성이 너무 좋지 않아서 제가 임의로 수정하거나 작성하였습니다.

 

 위의 글과 관련하여 추가적인 내용이나 피드백은 언제나 환영입니다 :)