[자료구조] 스택 (Stack), 큐(Queue)

woonie·2022년 4월 27일
0

프로젝트 기간이 짧다보니 시간적 여유가 없다는 핑계로 자료구조에 대해 깊게 공부하지 못했다.
이번 프로젝트를 끝으로 개발자에 대한 꿈을 접을 생각이 없고 나는 앞으로 계속 나아가야 하기에 조금씩, 하나하나 공부해 나가려고 한다.

1. 스택 (Stack)

1-1. 스택(Stack)이란?

쉽게 얘기하자면 쌓아 올린다는 것을 의미한다.
따라서 스택 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.

1-2. 스택(Stack)의 특징

  • LIFO (Last In First Out) 즉 후입선출 방식으로 동작하며 가장 최근 스택에 삽입(push)된 자료의 위치를 top이라 한다.

  • 스택의 push는 top에 새로운 데이터를 추가하고 pop은 가장 최근에 삽입된 데이터가 스택에서 삭제된다.
    (Last In First Out / 후입선출)

  • 스택의 가장 위에 있는 요소, 즉 top에만 접근이 가능하기에 top이 아닌 위치의 데이터에 대한 접근, 삽입, 삭제는 불가능하다.

  • 스택이 비어있는 경우에 pop을 시도하면 stack underflow라 하며 스택이 넘치는 경우 stack overflow라고 한다.
    (개발자라면 반드시 접속하게되는 그 유명한 "stack overflow"의 사이트도 여기서 유래되었다고 한다.)

1-3. 시간복잡도

  • top 위치의 데이터에 바로 접근이 가능하기에 데이터 삽입, 삭제의 시간 복잡도는 O(1)이다.

1-4. 스택(Stack)의 활용

스택의 특징인 후입선출을 활용하여 여러 분야에서 활용 가능하다.

  • 웹 브라우저 방문기록(뒤로가기) : 가장 나중에 연린 페이지부터 다시 보여준다.
  • 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력
  • 실행 취소 : 가장 나중에 실행된 것부터 실행을 취소한다.

2. 큐(Queue)

2-1. 큐(Queue)란?

줄 , 혹은 줄을 서서 기다리는 것을 의미한다.

2-2. 큐(Queue)의 특징

  • 한쪽에서만 데이터의 삽입 삭제가 이루어졌던 스택과 달리 큐는 양쪽 끝에서 데이터의 삽입과 삭제가 각각 이루어진다.

  • FIFO (First In First Out) 즉 선입선출 방식으로 동작하며 데이터가 삽입되는 곳을 리어(rear), 데이터가 삭제되는 곳을 프론트(front)라 한다.

  • 큐의 offer는 리어(rear)에 새로운 데이터를 추가하고 poll은 가장 처음에 삽입된 데이터가 프론트(front) 에서 삭제된다.
    (First In First Out / 선입선출)

  • 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue)
    프론트에서 이루어지는 삭제연산을 디큐(dnQueue)라고 한다.

2-3. 시간복잡도

  • 큐 역시 front, rear 의 위치로 데이터 삽입 삭제가 바로 이루어지기 때문에 원소 삽입, 삭제의 시간 복잡도는 O(1) 이다.

2-4. 큐(Queue)의 활용

큐는 주로 데이터가 입렫된 시간 순서대로 처리해야 할 필요가 있는 상황에 사용된다.

  • 작업 예약(프린터의 인쇄 대기열)
  • 은행 업무
  • 콜센터 고객 대기시간
  • BFS(너비 우선 탐색)
profile
동료들과 함께하는 개발의 중요성에 관심이 많습니다. 언제나 호기심을 갖고 꾸준히 노력하는 개발자로서 성장하고 있습니다.

0개의 댓글