Songzi Vong
YoungJin
공부한 내용을 기록하기 위한 공간

[CS]자료구조(스택, 큐) 정리

Intro

CS와 코딩테스트를 준비하던 중 스택과 큐 자료구조에 대해서 계속 노출되어 반드시 정리가 필요할 것으로 생각되어 정리해보려 한다.

자료구조

자료구조란, 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다.

스택(Stack)

스택이란, 쌓다의 의미로 데이터를 차곡차곡 쌓아 둔 형태를 가진 자료구조이다.

  • 선입후출 방식(=후입선출) 으로 먼저 들어온 데이터가 나중에 나가는 형식의 자료 구조이다.
  • 가장 최근에 들어온 자료를 top이라 한다. 데이터를 꺼낼 때 가장 위쪽(top) 데이터부터 꺼낼 수 있는 구조.
    • 스택에 데이터를 삽입할 때 : POP
    • 스택에 데이터를 삭제할 때 : PUSH
  • 스택은 입구, 출구가 동일한 형태로 되어있으며, 쉽게 생각하면 박스를 쌓는다고 생각하면 된다.**
  • 스택 오버플로우(overflow)/스택 언더플로우(underflow)
    • 스택이 꽉 차있을 때 자료를 넣으려고 하면 스택 오버플로우
    • 스택이 비어있을 때 자료를 꺼내려고 시도하면 스택 언더플로우
  • 스택 활용 예시
    • 웹 브라우저 방문기록(뒤로가기) : 가장 나중에 열린 페이지부터 보여준다.
    • 실행 취소(undo) : 가장 나중에 입력된 문자부터 출력한다.
  • 코드
    • 메서드(python) : append(삽입), pop(제거) 
      1
2
3
4
5
6
7
8

      stack = []
stack.append(5) # 5
stack.append(3) # 3 5
stack.append(2) # 2 3 5
stack.pop() # 제일 상단에 있는 데이터 삭제 => 2를 삭제함.

print(stack) # 출력 결과 : 5 3 (최하단 원소부터 출력함.)
print(stack[::-1]) # 출력 결과 3 5(최상단 원소부터 출력함.)
    • 메서드(java) : push(삽입), peek(최상단 값 출력), pop(제거), clear(모두 제거) 
      1
2
3
4
5
6
7
8
9
10
11
12

      import java.util.Stack; // import
Stack<Integer> stack = new Stack<>(); // int형 스택 선언
Stack<String> stack2 = new Stack<>(); // String형 스택 선언

stack.push(1); // 1
stack.push(2); // 2 1
stack.push(3); // 3 2 1
System.out.print(stack.peek()) // 출력 : 3(최상단에 있는 3 출력.)
System.out.print(stack.size()) // 출력 : 3(stack 사이즈 출력)
System.out.print(stack.contains(1)) // 출력 : true(1이 있는 지 여부 확인)
stack.pop(); // 3을 제거함
stack.clear(); // 모두 제거

큐 (Queue)

큐는 대기 줄과 같이, 데이터가 먼저 들어온 순서대로 먼저 나가는 형태로 구성된 자료구조이다.

  • 선입선출 방식으로 먼저 들어온 데이터가 먼저 출력되는 자료구조이다.
  • 입구 및 출구가 모두 뚫려있는 터널과 같은 형태로 생각하면 된다.
  • 큐는 파이썬에서 deque 자료구조를 활용한다.
    • deque는 스택, 큐의 장점을 혼합한 것으로 “앞으로, 뒤로 어느 방향이든 넣고 뺄 수 있는 자료구조”라 할 수 있다.
  • 큐 활용예시
    • 은행창구 번호표 대기 : 먼저 번호표를 받은 사람이 먼저 업무를 본다.
    • 프린트 출력 : 가장 먼저 대기열에 오른 프린트가 먼저 출력된다.
    • 너비 우선 탐색 알고리즘(BFS)
  • 코드
    • 메서드(python)
      • append(삽입), pop(제거), popleft(첫 번째 데이터 삭제), pop(마지막 데이터 삭제) 
        1
2
3
4
5
6
7
8
9
10

          from collections import deque
  # deque 라이브러리를 이용
  queue = deque()
  queue.append(3)
  queue.append(4)
  queue.append(5)
  print(queue) # deque([3, 4, 5])
  queue.popleft() # 제일 처음 삽입된 3이 삭제된다.
  print(queue) # deque([4, 5])
  queue.pop() # 제일 마지막에 삽입된 5가 삭제된다.
    • 메서드(java)
      • add(추가), offer(추가), poll(첫 번째 값 반환, 비어있으면 null), remove(첫 번째 값 제거), clear(모두 제거) 
        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

          import java.util.LinkedList;
  import java.util.Queue;
  // 자바는 Queue를 LinkedList를 활용해야 한다.
  Queue<Integer> queue = new LinkedList<>();
  Queue<String> queue2 = new LinkedList<>(); 
  // add, offer 두 가지 모두 값을 추가한다는 공통점이 있다.
  // 하지만, add의 경우 큐가 꽉 찬 경우 예외를 발생시키지만, offer의 경우는 추가 실패를 의미하는 false를 리턴한다.
  queue.add(1);
  queue.add(2);
  queue.offer(3);
  System.out.print(queue); // [1 ,2 ,3 ]

  // poll, remove도 값을 제거한다는 공통점이 있다.(맨 앞의 값 삭제)
  // 하지만, poll은 비어있다면 null을 반환하지만 remove는 NoSuchElement 에러를 반환한다.
  queue.poll(); // 1 삭제
  queue.remove(); // 2 삭제
  queue.clear(); // 모두 삭제

목차