📌 스택 자료구조

스택의 특징 : 후입선출, LIFO (Last-In- First-Out)

• 가장 최근에 들어온 데이터가 가장 먼저 나감
• 후입선출은 삽입과 삭제가 한 쪽에서만 일어남

  * 스택 용어

  1) 위치
  top : 삽입과 삭제가 일어나는 위치
  2) 연산
  push : top 위치에 새로운 데이터를 삽입하는 연산
  pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
  top : top 위치에 현재 있는 데이터를 단순 확인하는 연산

✅ 스택 클래스 설계

1) 클래스명
ArrayStack
2) 멤버 변수( - ; private의 접근 권한)
-top : int --> 스택의 top 변수
-data[ ] : int --> 항목을 저장할 배열
3) 멤버 함수
생성자
스택 연산

✅ C++ Stack container

#include <stack>
stack<int> st; 

bool empty() const; //스택이 비어 있는지 확인
ex) st.empty();

size_type size() const; //사이즈 반환(스택의 사이즈, 현재 데이터가 몇 개 들어갔는지)
ex) st.size();

const value_type& top() const; //맨 위에 있는 인자 반환
ex) st.top();

void push(const value_type&val); // 데이터(value)삽입, 데이터를 스택에 넣음 
ex) st.push(999); //999를 스택에 삽입

void pop(); //맨 위에 있는 인자 삭제 
ex) st.pop(); //** 맨 위에 있는 데이터가 무엇인지 확인하고(top) 삭제하는(pop) 개념

📌 큐 자료구조

= 먼저 들어온 데이터가 먼저 나가는(=선입선출) 자료구조

• FIFO : First-In First-Out (먼저 온 사람 먼저 처리해주는 방식)
• ex) 매표소, 공항, 대기줄, 컴퓨터와 프린터 사이의 버퍼링
  

* 큐 용어

- enqueue(a) : 데이터 삽입(뒤), 늦게 온 사람은 뒤에 줄 세움
- dequeue() : 데이터 삭제(앞), 먼저 온 사람 처리해줌

1) 선형 큐 linear Queue

= '배열'을 사용하여 큐를 구현

• 앞과 뒤가 어딘지 알아야 사용
• 뒤에 데이터 삽입, 앞에서 데이터 삭제
  

✅ C++ linear queue container

#include <queue>
queue<int> q; //linear queue

bool empty() const; //비어 있으면 true, size()가 0이면 true

size_type size() const; //큐에 저장된 원소 개수 반환

value_type& front(); //첫번째 원소에 접근(데이터를 알아야 삭제할 수 있음!!)

value_type& back(); //마지막 원소에 접근(데이터를 알아야 삽입할 수 있음!!)

void push(const value_type& val); //삽입 연산(데이터를 뒤에 삽입)

void pop(); //삭제 연산(맨 앞에 있는 데이터 삭제, 리턴값이 없는 void 타입)

⚠️ pop()은 반환값이 없는 void 이므로 앞의 원소를 참조하려면 front 사용

• front() : 큐의 맨 앞에 있는 요소를 반환하는 함수
  --> pop()은 값을 반환하지 않으므로 삭제될 값이 필요하면
  pop()을 호출하기 전에 front()으로 그 값을 확인!!

* 선형 큐의 단점

• '데이터 삽입'을 계속하기 위해선 요소들을 앞으로 이동시켜야 함
• 앞이 맨날 비어서 2차원 배열을 효율적으로 사용할 수 없음

이러한 문제를 해결하기 위해 '원형 큐'가 사용됨 !!

2) 원형 큐 Circular Queue

• enqueue(int data) ; 삽입 : 데이터를 큐의 뒷 부분에 삽입
• int data = dequeue( ) ; 삭제 : 큐의 앞 부분에서 데이터 삭제

✅ 원형 큐 클래스 설계

1) 클래스명
= CircularQueue
2) 멤버 변수

• '#'(protected의 접근 권한) : 상속을 위해 사용, 자식 클래스까지 접근 가능
• int 변수 : front,rear (#front : int, #rear : int)
• int 배열 : 원형큐에 저장할 데이터 (#data[] : int)
  3) 멤버 함수
• CircularQueue() : 생성자
• enqueue(int item), dequeue() : 삽입, 삭제
• peek() : 원형 큐에서 가장 앞에 있는 값을 확인
• isEmpty(), isFull() : 큐 공백상태, 포화상태 체크
• display() : 큐 내용 표시

3) 덱 deque

= front와 rear 모두 삽입과 삭제가 가능한 큐

• 덱은 double-ended queue의 줄임말
• 앞에서도 add,delete 뒤에서도 add,delete가 가능
  

✅ <C++ deque container>

#include <deque>
deque<int> del // dequeue

dq.size(); // 원소의 개수 반환
dq.empty(); // dq가 비어 있으면 true 반환

dq.front(); // 첫 번째 원소에 접근
dq.push_front(3); // dq의 첫 번째 원소 앞에 원소 3을 삽입
dq.pop_front(); // dq의 첫 번째 원소를 제거

dq.back(); // 맨 마지막 원소에 접근
dq.push_back(5); // dq의 마지막 원소 뒤에 원소 5를 삽입
dq.pop_back(); // 마지막 원소를 제거