📍Stack
🔎 Stack 특징
- 선형 구조이다.
- LIFO (Last in First Out): 후입선출, 나중에 들어간 데이터가 먼저 나오는 구조이다.
- 아래부터 차곡차곡 쌓이는 것이기 때문에 위의 것부터 꺼낸다.
- 스택이 가득 차서 더 넣을 수 없는 경우를 오버플로우, 비어있어서 자료를 꺼내지 못하는 경우를 언더플로우라고 한다.
- 데이터를 순서대로 a, b, c를 넣으면 꺼낼 때는 c, b, a 순서로 꺼낸다.
🔎 Stack 예시
- 웹 브라우저 방문 기록(뒤로 가기)
- 물류창고에서 박스를 수납할 때 기존 박스 위에 새로운 박스를 올리고, 꺼낼 때는 위에 있는 박스부터 꺼낸다.
🔎 Stack 연산
- top() - 스택의 가장 위의 데이터 반환
- pop() - 스택의 가장 위의 데이터 삭제
- push() - 스택의 가장 위에 메모리를 생성하고 데이터를 넣음
- isfull() - 스택에 데이터가 있다면 1(true) 반환, 없다면 0(false) 반환
- empty() - 스택이 비었다면 1(true) 반환, 아니라면 0(false) 반환
- size() - 스택의 크기 반환
🔎 Stack 구현
- 스택의 정적 구현
- 1차원 배열
- 스택의 동적 구현:
- 연결 리스트로 구현
- 크기에 제한 없음
- 구현이 복잡하고 삽입과 삭제가 오래 걸림
📍Queue
🔎 Queue 특징
- FIFO (First In First Out): 선입선출, 먼저 들어온게 먼저 나간다.
스택과 반대 - 입력된 시간 순서대로 처리할 때 사용한다.
- 큐가 가득 차서 더 넣을 수 없는 경우를 오버플로우, 비어있어서 자료를 꺼내지 못하는 경우를 언더플로우라고 한다.
- 데이터를 순서대로 a,b,c 넣으면 a, b, c 순서대로 나온다
🔎 Queue 예시
- 인쇄 작업 시 작업을 시작한 순서대로 결과물 도출
- 너비 우선 탐색(BFS) 구현 시 사용
- 식당 웨이팅 할 때, 먼저 온 사람부터 입장하는 것과 동일.
🔎 Queue 종류
- 선형 큐
- 막대 모양으로 된 큐이다.
- 크기가 제한된다.
- 빈 공간을 사용하려면 모든 자료를 이동해야한다는 단점이 있다.
- 환형 큐
- 선형 큐의 마지막 배열에 도달 후 실제 공간이 있지만 오버플로우가 발생하는 문제를 보완한 큐
- front가 큐의 끝에 닿으면 큐 맨 앞으로 자료를 보내 원형으로 연결된 구조이다.
🔎 Queue 연산
- Enqueue() - 큐의 끝에서 데이터 추가
- Dequeue() - 큐의 앞에서 데이터 제거
- Peek() & front() - 큐의 가장 앞 노드에서 데이터를 반환
- rear() - 큐의 가장 끝 노드에서 데이터를 반환
- isFull() - 큐가 가득 찼는지 확인
- isNull() - 큐가 비어 있는지 확인
📍스터디 회고
📍공부한 곳
위키백과 : stack, queue 검색
스택 & 큐 정리
https://devuna.tistory.com/22
https://roi-data.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-4-%EC%8A%A4%ED%83%9DStack%EC%9D%B4%EB%9E%80-%EC%97%B0%EC%82%B0-%EA%B5%AC%ED%98%84%EB%B0%A9%EB%B2%95
공부하자