자료구조: 2-1. Stack&Queue 개요

1. Stack

후입선출 자료구조이다. '후입선출'이란, 가장 나중에 들어온 데이터가 가장 먼저 밖으로 나간다는 의미이다. 메모리 안에서 데이터를 효율적으로 관리하기 위해 만들어진 자료구조이다.

Stack 구조 및 기능

스택을 추상화해서 설명하기 위해 대부분 길다란 원통을 사용한다. 메모리 안에서 연속적으로 공간을 할당할지, 비순차적으로 할당할지에 따라 구현방법은 달라질 것이다.
하지만 기본적인 구조와 원리는 다 똑같다. 주요 기능은 아래 3가지로 요약된다.

• push() -> 데이터 삽입
• pop() -> 데이터 삭제, 가장 먼저 들어온 데이터를 제거
• peek() -> 가장 먼저 들어온 데이터 검색

Stack의 시간복잡도

1. 삽입 O(1)
-> 탐색할 필요 없이, 포인터가 가르키는 위치에 삽입하면 된다.
2. 삭제 O(1)
-> 맨 앞에 위치한 데이터를 제거하면 되기 때문.
3. 조회 peek이면 O(1), peek이 아니면 O(N)
-> peek이 아니면, 탐색 시 pop이 빈번히 호출된다.

Stack의 활용예시

활용사례를 정리하자면 아래와 같다.

• 웹 브라우저 방문기록
  뒤로가기를 클릭하면, 우리가 직전에 방문했던 페이지를 보여준다.

• 역순 문자열 만들기
  0번 인덱스부터 stack에 담고 하나씩 출력하면, 자연스럽게 역순 문자열을 만들 수 있다.

• 실행 취소(undo)
  문서 작업을 하다가 내용을 잘못 입력했다면, Ctrl + Z 를 누르면 이전으로 돌아갈 수 있다.

• 수식의 괄호검사
  연산자 우선순위에 맞게 계산하여 올바른 결과가 나올 수 있도록 유도

2. Queue

Queue는 선입선출 자료구조이다. '선입선출'이란, 가장 먼저 들어온 데이터가 먼저 나간다는 이야기이다. 역시 메모리 공간을 효율적으로 관리하기 위한 자료구조이다.

Queue의 구조 및 기능

큐 역시 추상화해서 설명하기 위해 길다란 원통을 사용해서 설명한다. 하지만 이 역시 연속할당이나 비순차할당이냐에 따라서 구현방법은 달라진다.
주요 3가지 기능은 아래와 같다.

• enqueue -> rear 위치에 데이터 삽입
• dequeue -> front 위치에서 데이터 뽑아와서 삭제
• peek -> front 위치의 데이터 조회

Queue의 시간복잡도

삽입 O(1)
스택과 마찬가지로, 포인터의 도움을 받아서 데이터를 삽입하므로 탐색시간이 필요하지 않음.
삭제 O(1)
스택과 마찬가지로, 특정 위치(FRONT) 영역에서 데이터를 꺼내오기만 하면되서 탐색시간 필요하지 않음.
조회 peek = O(1), non-peek = O(N)
Peek이 아닐 땐, 앞에서부터 데이터를 하나씩 꺼내서 확인해야하므로 탐색시간이 필요하다.

Queue의 활용예시

• 우선 순위가 같은 작업 예약
  우선순위가 같은 경우, 먼저 들어온 작업을 먼저 처리한다.

• 은행 업무
  먼저 은행에 온 고객의 업무를 먼저 처리한다.

• 콜센터 고객 대기시간
  시간 상 가장 먼저 전화를 건 고객의 이슈를 처리한다.

• 캐시 구현

3. 순차적 할당과 비순차적 할당

이 방식은 사실 연결리스트로 구현할 것이냐 배열로 구현할 것인가를 선택하는 문제이다. 연결리스트는 메모리에 데이터가 비순차적으로 할당되고, 배열은 순차적으로 할당된다.

• 배열로 구현 시 장단점
  순차적으로 메모리에 할당되기 때문에, 단편화 이슈를 줄일 수 있다. 하지만 정해진 공간만 사용해야하고, 배열 크기에 비해 삽입된 데이터의 규모가 작으면 공간이 낭비가 된다. 따라서 유연성이 떨어질 수 있다는 문제점이 있다. 또한 삽입-삭제 시 데이터를 shift 해야하므로 오버헤드가 크다. 오버헤드 이슈는 원형 큐를 구현해서 상쇄시킬 수 있다.
  다음 챕터에선 원형 큐 구현법을 소개하고자 한다.

• 연결리스트로 구현 시 장단점
  메모리를 필요한 만큼 사용할 수 있다. 즉, 공간을 유연하게 사용할 수 있다. 하지만 연결리스트로 구현한만큼, 단편화 이슈는 여전히 존재할 수 밖에 없다.