스택, 큐

김하영·2023년 5월 28일
0

선형자료구조

목록 보기
4/5

스택

특징

  • 후입 선출 구조이다. (LIFO)
  • 데이터가 입력된 순서의 역순으로 처리되어야 할때 사용한다.
  • ex) 함수호출 스택, 괄호 쌍 찾기, 문자열 역순 출력 등

메소드

import java.util.Stack;

Stack stack = new Stack();

stack.push(5); // 스택에 데이터 입력
stack.pop(); // 스택에서 데이터 꺼내기
stack.peek(); // 스택에서 top 데이터 확인
stack.constains(5); // 스택 내 데이터 포함 여부 확인
stack.isEmpty(); // 스택이 비어있다면 true, 아니면 false
stack.clear(); // 스택 비우기
stack.size(); // 스택의 크기 반환

시간 복잡도

삽입삭제탐색조회
O(1)O(1)O(N)O(N)

특징

  • 선입 선출 구조이다. (FIFO)
  • 입력 순서대로 데이터 처리가 필요할 때 사용
  • ex) 프린터 출력 대기열, BFS, 급식줄..

메소드

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

Queue q = new LinedList();
q.add(3); // 큐에 추가
q.poll() / q.remove(); // 큐에서 제거
q.peek(); // 큐의 다음 데이터 보기
q.contains(3); // 큐에 데이터 포함 여부
q.clear(); // 큐 비우기
q.isEmpty(); // 큐가 비었는지 여부

시간 복잡도

삽입삭제탐색조회
O(1)O(1)O(N)O(N)
profile
백엔드 개발자로 일하고 싶어요 제발

0개의 댓글