[자료구조] 스택과 큐, 연결 리스트 - 개념과 예상 기술 면접 질문

🕵️‍♀️ 스택과 큐, 연결리스트 

https://www.hanbit.co.kr/data/editor/20231027090450_wfludeql.png

 

https://xoxoxoxox.tistory.com/250

자료구조(Data Structure)란

앞서 정리해던 자료구조에서 소개했던 데이터를 순서대로 정렬하는  선형 동적 자료구조에 속하는 스택과 큐 그리고 연결리스트에 대해 간단히 정리하고, 여기에서 출제될 수 있는 기술 면접 질문에 대해 포스팅하려고 한다. 

 

👩‍💻 리스트 vs 스택 vs 큐

	공통점	차이점
리스트(List)	선형 자료 구조 (순서가 있음)	읽기, 삽입, 삭제 연산이 리스트의 어느 곳에서나 가능함
스택(Stack)		삽입, 삭제 연산이 리스트의 top에서만 가능함
큐 (Queue)		삽입은 리스트의 뒤쪽(rear)에서, 삭제는 리스트의 앞쪽(front)에서만 가능함

 

---

📚 스택 (Stack)

 

Stack은 영어로 쌓아놓은 더미를 의미한다. 식당에 쌓여있는 접시 더미나, 프링글스 통에 들어가있는 감자, 책상에 쌓여져 있는 책 과 같은 것으로 스택을 비유할 수 있다. 

 

스택의 특징

 - 후입선출; Last-In-First-Out (LIFO)
 - 삽입(Push)과 삭제(Pop) 연산 가능
 - 탑(Top) 접근: 스택의 맨 위에 있는 데이터 요소를 접근할 수 있다. 
 - 고정 크기, 동적 크기 둘다 구현 가능
 - 사용 예시 : 함수 호출, 문자열 역순 변환, 괄호 검사, DFS(깊이 우선 탐색)

 

java에서의 스택 사용법

import java.util.Stack;
Stack<Integer> stack = new Stack<>();

 

자바에서는 java.util 패키지를 import해서 Stack 클래스를 사용할 수 있다. 

 

더 자세한 구현 내용은 밑에 글에 정리해두었다. https://xoxoxoxox.tistory.com/160

[자료구조] 스택 (Stack) 구조 (Java)

 

 

✔️시스템 스택

 - 운영체제가 사용하는 스택

함수의 실행이 끝나면 자신이 호출한 함수로 되돌아가야 하는데, 이 때 스택을 이용해서 복귀할 주소를 쌓아두고 하나 씩 pop() 하면서 복귀하게 된다. 

https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbMm2iu%2FbtrAj4T8TpU%2FOEhnWi385M55WeYxC71yD1%2Fimg.png

시스템 스택에는 함수가 호출될 때마다 활성 레코드가 만들어지면서 여기에 복귀 주소가 저장된다. 활성 레코드에는 프로그램 카운터 뿐만 아니라 함수 호출시 매개변수와 함수 안에서 선언된 지역변수들이 같이 생성된다 

---

📚 큐(Queue)

 

큐(Queue)는 영어로 줄로 사용하는 것처럼 선입선출의 형태인 마켓의 계산대의 줄, 도로에서 줄 지어져 가고 있는 차 등으로 비유될 수 있다. 

큐(Queue)의 특징

- 선입선출 (FIFO) - First-In-First-Out
- 삽입(Enqueue)과 삭제(Dequeue) 연산 가능
- 프론트(front)와 리어(rear): 두개의 포인터/인덱스를 이용해서 관리
- 고정크기, 동적 크기 둘다 구현 가능
- 사용 예시 - 프로세스 스케줄링, 프린터 작업 관리, 너비우선탐색(BFS) 등

 

큐(Queue)의 종류 

 

• 일반 큐 (Regular Queue)
  • 구조: 기본적인 FIFO(First In, First Out) 구조를 따릅니다.
  • 연산: 데이터 삽입은 리어(rear)에서, 제거는 프론트(front)에서 이루어집니다.
  • 용도: 간단한 데이터 처리 작업, 프로세스 스케줄링 등.
• 원형 큐 (Circular Queue)
  • 구조: 배열을 사용하여 구현된 큐로, 마지막 위치가 다시 처음 위치로 연결되는 형태입니다.
  • 특징: 고정된 크기의 배열을 사용하여 메모리 효율성을 높입니다.
  • 연산: 리어와 프론트가 배열의 끝에서 다시 시작으로 돌아옵니다.
  • 용도: 제한된 메모리 공간에서의 작업, 네트워크 버퍼 관리 등.
• 우선순위 큐 (Priority Queue)
  • 구조: 각 요소가 우선순위를 가지며, 높은 우선순위의 요소가 먼저 처리됩니다.
  • 특징: FIFO 순서가 아닌 우선순위에 따라 요소가 제거됩니다.
  • 연산: 힙(Heap), 이진 탐색 트리 등을 사용하여 구현됩니다.
  • 용도: 작업 스케줄링, 다익스트라 알고리즘 등.
• ++  덱 - 이중 끝 큐 (Deque, Double-Ended Queue)
  • 구조: 양쪽 끝에서 삽입과 제거가 모두 가능한 큐입니다.
  • 특징: 스택과 큐의 기능을 모두 가질 수 있습니다.
  • 연산: 데이터의 삽입과 제거가 양쪽 끝에서 이루어질 수 있습니다.
  • 용도: 복잡한 자료 처리, 브라우저 히스토리 관리 등.

 

java에서의 큐(Queue) 사용법

import java.util.Queue;
import java.util.LinkedList;

//Queue 선언 및 초기화
Queue<Integer> queue = new LinkedList<>();

//Queue에 요소 추가
queue.add(1); 

//요소 제거
int removedElement = queue.poll();

//맨 앞 요소 조회
int frontElement = queue.peek();

//큐의 크기 확인 
int size = queue.size();

//큐가 비어있는 지 확인
boolean isEmpty = queue.isEmpty();

 

자바에서는 java.util 패키지를 import해서 Queue를 사용할 수 있다. 

 

✔️ ✔️ Java에서 Queue는 인터페이스만 제공

전 글에서 언급했던 것과 마찬가지로, Java에서 Queue는 인터페이스로만 제공한다. Queue 인터페이스를 직접 구현한 ㅋ르래스는 존재하지 않기 때문에 보통 LinkedList를 구현체로 초기화 한다. 

 

더 자세한 구현 내용은 밑에 글에 정리해두었다 https://xoxoxoxox.tistory.com/162

[자료구조] 큐 (Queue) 구현 (Java)

 

---

📚 연결리스트 (Linked List)

우리는 일상생활에서 리스트를 많이 사용하고 있다. 오늘 해야할 일을 정리하거나, 장 볼 때 사와야하는 항목을 비유할 수 있다. 

 

연결 리스트의 특징

1. 노드 구조:
   • 데이터(Data): 노드가 저장하는 실제 데이터이다.
   • 포인터(Next/Link): 다음 노드를 가리키는 참조입니다. 단일 연결 리스트의 경우 한 개의 포인터만을 가지며, 이중 연결 리스트의 경우 다음 노드와 이전 노드를 가리키는 두 개의 포인터를 가진다.
2. 메모리 사용:
   • 동적 메모리 할당: 요소들이 메모리상에 연속적으로 저장되지 않으며, 필요에 따라 동적으로 메모리가 할당된다. 따라서 배열과 달리 크기를 사전에 지정할 필요가 없다.
   • 메모리 효율성: 요소 삽입과 삭제 시 전체 요소들을 이동시키지 않아도 되므로 메모리 효율성이 높다.
3. 삽입과 삭제의 용이성:
   • 삽입: 리스트의 중간에 요소를 삽입할 때 간단히 포인터만 조정하면 되므로 매우 빠르게 수행된다.
   • 삭제: 리스트의 중간에서 요소를 삭제할 때도 포인터만 조정하면 되므로 매우 빠르게 수행된다.
   • 연산 시간: 삽입과 삭제 연산이 O(1)O(1)O(1) 시간 복잡도를 가지며, 배열의 O(n)O(n)O(n)보다 효율적이다.
4. 랜덤 액세스 미지원:
   • 직접 접근 불가: 연결 리스트는 인덱스를 사용한 직접 접근(random access)을 지원하지 않으므로, 특정 위치의 요소에 접근하려면 순차적으로 탐색해야 한다.
   • 탐색 시간: 요소에 접근하기 위해서는 평균적으로 O(n)의 시간이 소요된다다.

 

 

연결 리스트의 종류

1. 단일 연결 리스트(Singly Linked List):
   • 각 노드가 다음 노드를 가리키는 하나의 포인터를 가집니다.
   • 단방향으로만 이동할 수 있습니다. 

class Node {
    int data;
    Node next;
}

 

 2. 이중 연결 리스트(Doubly Linked List):

• 각 노드가 다음 노드와 이전 노드를 가리키는 두 개의 포인터를 가집니다.
• 양방향으로 이동할 수 있습니다.

class Node {
    int data;
    Node next;
    Node prev;
}

 

java에서의 연결리스트

import java.util.LinkedList;

LinkedList<Integer> list = new LinkedList<>();
// 요소 추가 (append)
list.add(1);
list.add(2);
list.add(3);

// 요소 삽입 (insert)
list.add(1, 4); // 인덱스 1 위치에 4를 삽입

// 요소 삭제 (delete)
list.remove(2); // 인덱스 2 위치의 요소 삭제

// 요소 접근 (access)
int element = list.get(0); // 인덱스 0 위치의 요소 접근

 

더 자세한 구현 내용은 밑에 글에 정리해두었다. https://xoxoxoxox.tistory.com/164

[자료구조] 리스트 (List) 구현 (Java)

 

---

 

💡자료구조 기술 면접 질문 

 

✔️✔️ 어떤 경우에 어떤 자료구조가 효율적인지 알기 

 

🕵️‍♀️자료구조를 왜 사용하나요?

 

메모리를 효율적으로 사용하면서 데이터를 빠르고 안정적으로 처리하기 위해 필요합니다. 알맞은 자료구조는 효율적인 알고리즘을 만들고, 이는 프로그램의 성능에 큰 영향을 미치기 때문에 적절한 자료구조를 사용하는 것이 중요합니다. 

 

🕵️‍♀️자료구조와 알고리즘에 대해 설명해주세요. 

 

흔히 프로그램은 자료구조와 알고리즘으로 이루어져 있다고 표현합니다. 프로그램은 자료를 처리하는데, 이 자료들은 자료구조에 저장됩니다. 또 알고리즘으로 주어진 문제를 처리하는 절차가 필요합니다. 효율적인 자료구조가 성능이 좋은 알고리즘을 만들기 때문에 성능 좋은 프로그램을 만들기 위해서는 자료구조와 알고리즘을 활용하는 것이 중요합니다. 

 

🕵️‍♀️Java Collection에 대해 설명해주세요. 

 

자바의 대표 Collection에는 List, Map, Set, Stack, Queue 등이 있습니다. 이 추상화된 Collection 인터페이스와 그에 대한 구현체로 이루어져있다. 예를 들어, List라는 인터페이스의 구현체로  ArrayList와 LinkedList가 있다. 또 제공되는 API는 검증된, 고도로 최적화되다는 장점이 있습니다. 

 

연결 리스트

 

🕵️‍♀️ Linked List에 대해 설명해주세요.

 

Linked List는 노드라는 구조체로 이루어져 있고, 각 노드는 데이터와 다음 노드의 주소를 저장해 물리적으로는 비연속적이지만 논리적으로는 연속성을 갖는 자료구조입니다.

데이터가 추가되는 시점에 메모리를 할당하기 때문에 메모리를 효율적으로 사용할 수 있습니다. 

 

⭐ 🕵️‍♀️ ⭐  Array와 Linked List를 비교해서 설명해주세요. (N사 전화면접)

 

Array는 인덱스로 원하는 원소에 접근할 수 있어서 찾고자 하는 원소의 인덱스 값을 알고 있으면 O(1)에 해당 원소로 접근할 수 있습니다. 즉, RandomAccess가 가능해 속도가 빠르다는 장점이 있습니다. 

하지만 삽입이나 삭제 같은 경우는 각 원소들을 shift 해줘야하는 비용이 생겨서 시간 복잡도가 O(n)이 된다는 단점이 있습니다. 

이 문제를 해결하기 위한 자료구조가 Linked List인데, 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하게 해서, 이 부분만 다른 값으로 바꾼다고 하면 삽입과 삭제가 O(1)로 해결할 수 있습니다. 하지만 반대로 LinkedList는 원하는 위치에 한번에 접근 할 수 없어 원하는 위치에 삽입을 하고자 한다면 원하는 위치를 먼저 찾아야한다는 단점이 있습니다. 

간단히 정리하면, Array는 검색이 빠르지만, 삽입/삭제가 느리고, LinkedList는 삽입/삭제가 빠르지만, 검색이 느립니다. 

 

🕵️‍♀️ ArrayList와 Array를 비교해서 설명해주세요.

 

Array는 크기가 고정적이지만, ArrayList는 크기가 가변적입니다. Array는 초기화 할 때 메모리에 할당되어서 ArrayList보다 속도가 빠르고, ArrayList는 데이터 추가 및 삭제를 할 때 메모리를 재할당하기 때문에 속도가 Array보다 느립니다. 

 

🕵️‍♀️Array(List)의 가장 큰 특징과 그로 인해 발생하는 장점과 단점에 대해 설명해주세요.

 

Array의 가장 큰 특징은 고정적인 길이로 초기화 시 할당되고, 순차적으로 데이터가 저장된다는 것입니다. 순차적으로 저장되기 때문에 index가 존재하며, index를 통해 특정 요소를 찾고 조작이 가능하다는 장점이 있습니다. 하지만 순차적인 저장이다 보니, 데이터 중간의 요소가 삽입/삭제 되는 경우 그 뒤에 모든 요소들을 shift해줘야하는 단점이 있습니다. 이러한 이유로 Array는 정보가 자주 삭제되거나 추가되는 데이터를 담기에는 적절하지 않습니다. 

 

 

스택/큐

스택/큐는 면접에서 단독으로 물어보는 경우가 많지 않다. 

 

🕵️‍♀️ Stack에 대해 설명해주세요.

 

🕵️‍♀️ Queue에 대해 설명해주세요.

 

🕵️‍♀️ 원형 큐에 대해 설명해주세요.

배열을 사용하여 구현된 큐로, 원형으로 마지막 위치가 다시 처음 위치로 연결되는 형태입니다. 고정된 크기의 배열을 사용하여 메모리 효율성을 높입니다.

 

🕵️‍♀️Stack과 Queue의 차이점은 무엇인가요? (N사 전화면접)

Stack과 Queue는 저장/삭제 되는 순서가 다릅니다. Stack은 후입선출로, 마지막에 넣은 자료가 가장 먼저 나오게 되는 구조입니다. top을 통해서 push, pop을 하면서 삽입 삭제가 일어납니다. 역순위로 출력되는 것이 필요한 DFS나 재귀에서 주로 사용됩니다. 반면에 Queue는 선입선출로, 먼저 넣은 자료가 가장 먼저 나오는 구조입니다. 한쪽에서는 삽입 작업을, 다른 한쪽에서는 삭제 작업을 진행합니다. 이는 BFS나 스케줄링에 사용됩니다. 

 

🕵️‍♀️Stack과 Queue의 실제 사용 예시를 들어 설명해주세요. 

Stack - 시스템 스택

 - 운영체제가 사용하는 스택

함수의 실행이 끝나면 자신이 호출한 함수로 되돌아가야 하는데, 이 때 스택을 이용해서 복귀할 주소를 쌓아두고 하나 씩 pop() 하면서 복귀하게 된다. 

 

Queue - OS의 스케줄러

자원의 할당과 회수를 하는 스케줄러 역할을 큐가 할 수 있습니다. 가장 단순한 형태의 스케줄링 정책인 선입선처리 즉, 큐를 이용한 방법이라고 할 수 있습니다. 

 

⭐ 🕵️‍♀️ ⭐ 우선순위 큐에 대해 설명해주세요. 

우선순위 큐는 들어간 순서와 상관없이 설정한 우선순위가 높은 데이터를 먼저 꺼내기 위해서 고안된 자료구조입니다. 우선순위 큐의 구현 방식에는 배열, 연결리스트, 힙이 있고, 그 중 힙 방식이 O(logN)을 보작하기 때문에 일반적으로는 완전 이진트리 형태의 힙을 이용해 구현합니다. 

---

[출처]

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

[자료구조] 4. 스택(Stack)이란? / 연산, 구현방법

면접 질문

https://pinopino.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%A9%B4%EC%A0%91-%EB%8C%80%EB%B9%84-%EC%A7%88%EB%AC%B8-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EC%97%85

자료구조 면접 대비 질문 리스트업

 

⭐⭐⭐⭐https://dev-coco.tistory.com/159 

신입 개발자 기술면접 질문 정리 - 자료구조