들어가기 전
계속해서 3편 스택과 큐에 대해 공부해보자.
-스택과 큐가 실제 생활에서 어떻게 응용될 수 있는지 간단한 예시 알아보기
1. 스택(Stack)과 큐(Queue)
1-1. 스택(stack)
제한적으로 접근할 수 있는 나열 구조로, 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 후입선출(LIFO)로 되어 있다.
실생활에서 볼 수 있는 간단한 예시로는, 사진처럼 책을 차곡차곡 쌓아올린 모습을 생각할 수 있다. 가장 밑단에 있는 책을 꺼내기 위해서는 맨 위에 있는 책부터 하나하나 꺼내야만 한다.
이처럼 스택(Stack)도 사진과 같이, 사전적 의미와 같이, 데이터를 차곡이 쌓아 올린 형태의 자료구조이다. 따라서 순차적으로 데이터가 쌓이고 가장 마지막에 쌓인 데이터가 가장 먼저 삭제되는 후입선출(LIFO)의 구조를 갖는다.
✏️스택의 특징들을 정리하자면
- 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있다.
- top으로 정한 곳을 통해서만 접근 가능하다.
- top을 통해 삽입하는 연산
push와 삭제하는 연산pop이 있다. - 구현 시 배열(Array)와 연결 리스트(Linked List)를 사용할 수 있다.
- 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다. (후입선출_LIFO)
- 빈 스택에서 원소를 추출하려고 할 때는
stack underflow, 넘치는 경우에는stack overflow라고 한다.
✏️스택의 활용예시로는
- 웹 브라우저 방문기록
뒤로 가기를 통해 가장 마지막에 방문한 페이지부터 다시 보여준다. - 역순 문자열 만들기
- 실행 취소(undo)
- 후위 표기법 계산
1-2. 큐(Queue)
먼저 삽입한 데이터가 먼저 나오는 선입선출(FIFO) 구조로 저장하는 자료구조이다.
실생활에서 볼 수 있는 가장 간단한 예시는 [줄서기]를 생각할 수 있다. 순서대로 차곡차곡 사람들이 줄을 서고 맨 앞이 가장 먼저, 맨 뒤가 가장 나중에 순서로 빠진다.
큐(Queue) 또한 사전적 의미는 줄, 줄를 서서 기다리는 것을 의미한다. 따라서 사진 속 줄서기와 같이 먼저 들어온 것이 먼저 나가는 선입선출(FIFO)의 구조를 갖는다.
✏️큐의 특징들을 정리하자면
- 한쪽 끝에서 삽입, 반대 끝에서 삭제가 양쪽으로 이루어진다.
- 삽입(Enqueue)은
Back(or Rear)에서, 삭제(Dequeu)는Front에서 이루어진다. - 스택과 같이 배열(Array)이나 연결 리스트(Linked List)를 사용해 구현할 수 있다.
✏️큐의 활용예시로는
- 은행 업무
- 서비스 센터 대기시간
- 프로세스 관리
- 캐시(Cache) 구현
2. 스택과 큐의 차이점
- 데이터의 삭제 순서
- 스택은 후입선출(LIFO)로 마지막 데이터 먼저 삭제
- 큐는 선입선출(FIFO)로 처음 데이터 먼저 삭제
- 데이터의 삽입과 삭제 위치
- 스택은 항상 맨끝에서 이루어짐
- 큐는 삽입는 뒤쪽(Back or Rear), 삭제는 앞쪽(Front)
=> 쏘 심플!! <=
참고
- 미트코딩(MeetCoding) 스터디
- 위키백과-스택
- 위키백과-큐
- TISTORY-[자료구조]스택(STACK),큐...
아직 공부 중이어서 틀린 내용이나 잘못 이해한 부분이 있을 수 있는데, 그럴 때는 댓글 남겨주세요~!!😊
👩💻시작이 반이다. 멋쟁이 개발자 되기 시작!