스택 & 큐 (Stack & Queue)

💡 스택 & 큐

스택 & 큐 를 배열로 구현했을 때

배열은 순서가 있고 첫 부분을 제거하거나 추가하려면 요소들을 하나씩 뒤로 옮겨야 하며 시간복잡도는 O(n) 임
스택과 큐의 과정이 비효율적이기 때문에 스택과 큐에서는 기본적인 배열을 사용하지 않음

그래서 첫 부분을 제거하거나 추가하는 과정의 시간복잡도가 상수인 연결 리스트를 스택 & 큐에 적용하는게 좋음

 

배열로 스택 구현

• addLast, removeLast -> O(1)의 시간복잡도
• addFirst, removeFirst -> 배열의 원소들은 메모리 상에서 순차적으로 저장되기 때문에 맨 앞에서 삽입/삭제 연산이 일어나면 뒤로 한칸씩 미루거나 앞으로 한칸씩 당겨야 하므로 O(n)의  시간복잡도
• Last In First Out (LIFO, 후입선출, 나중에 들어온 원소가 제일 먼저 나간다.)
• top에서만 삽입/삭제가 일어나며, 배열로 구현하면 O(1)의 시간복잡도 (addLast, addFirst)

 

배열로 큐 구현

• addLast, removeLast -> O(1)의 시간복잡도
• addFirst, removeFirst -> O(n)의 시간복잡도
• First In First Out (FIFO, 선입선출, 먼저 들어온 원소가 먼저 나간다.)
• 삽입은 rear에서 삭제는 front에서 일어나므로 삽입은 O(1), 삭제는 O(n)의 시간복잡도
• front에서 배열 원소를 삭제할 때도 상수 시간을 보장하려면? 원형 배열
  (head와 tail의 위치가 고정적이지 않고, 배열의 시작과 끝이 연결되어 있는 구조)

 

Stack

• 입출력이 한 방향으로 이루어지는 제한적 접근
• LIFO & FILO
• 입력 = Push, 출력 = Pop
• stack 가죠구조는 데이터가 아무리 많아도 하나씩 데이터를 입&출력
• 무조건 단일방향 입출력, 방향이 여러개면 자료구조라고 볼 수 없음

 

브라우저의 앞으로가기&뒤로가기를 생각해보자

• 새 페이지 접속 시, 현재 페이지는 Prev Stack에 보관
• 뒤로 가기 버튼을 누르면 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 끝에 보관된 페이지 = 현재페이지
• 앞으로 가기 버튼을 누르면 Next Stack의 가장 처음 페이지를 가져오고 현재 페이지는 다시 Prev Stack 으로 넘김

 

LIFO 예시

 

Stack 구현

- Stack과 Queue가 어떤 동작방식인지 이해하기 위해 직접 custom 타입으로 Stack을 정의하고 new를 통해 객체 생성

 

• push(): 스택에 데이터를 추가할 수 있어야 합니다.
• pop(): 가장 나중에 추가된 데이터를 스택에서 삭제하고 삭제한 데이터를 리턴해야 합니다.
• size(): 스택에 추가된 데이터의 크기를 리턴해야 합니다.
• peek(): 가장 나중에 추가된 데이터를 리턴해야 합니다.
• show(): 현재 스택에 포함되어 있는 모든 데이터를 String 타입으로 변환하여 리턴합니다.
• clear(): 현재 스택에 포함되어 있는 모든 데이터 삭제합니다.
• remove(): 삭제와 삭제된 요소 반환이 동시에 됩니다.

 

Queue 구현

• add(): 큐에 데이터를 추가할 수 있어야 합니다.
• poll(): 가장 먼저 추가된 데이터를 큐에서 삭제하고 삭제한 데이터를 리턴해야 합니다.
• size(): 큐에 추가된 데이터의 크기를 리턴해야 합니다.
• peek(): 큐에 가장 먼저 추가된 데이터를 리턴해야 합니다.
• show(): 큐에 들어있는 모든 데이터를 String 타입으로 변환하여 리턴합니다.
• clear(): 큐에 들어있는 모든 데이터를 삭제합니다.