[자료구조] 스택(Stack ) & 큐(Queue)

_kjwoooo·2023년 8월 16일

개발자 전공지식(CS)

목록 보기

5/8

스택 (Stack) 이란?

스택은 "쌓다" 라는 의미로, 데이터를 쌓아 올리며 관리하는 자료구조 중 하나입니다. 스택은 데이터를 일시적으로 저장하기 위하여 사용하는 자료구조 이며 가장 중요한 특징인 후입선출(LIFO:Last In First Out)의 데이터 입출력 순서를 가집니다. 이는 가장 최근에 추가된 데이터가 가장 먼저 제거되는 구조를 의미합니다.

스택(Stack)의 연산

	 Top은 스택의 삽입과 삭제가 일어나는 지점을 가리킨다.

push(x): 스택에 데이터 x를 추가합니다.
pop(): 스택의 맨 위의 데이터 원소를 제거하며, 반환합니다.
size(): 현재 스택에 들어 있는 데이터 원소 개수를 반환합니다.
isEmpty(): 현재 스택이 비어 있는지를 판단합니다.
비어있으면 True를 비어있지 않으면 False를 반환합니다.
peek(): 스택의 맨위의 데이터 원소를 반환합니다.

큐(Queue) 란?

큐(Queue)는 컴퓨터 과학에서 사용되는 중요한 자료구조 중 하나로, 데이터를 일렬로 나열한 후, 처음으로 들어온 데이터가 처음으로 나가는 "FIFO" (First-In-First-Out, FIFO) 원칙을 따르는 자료구조입니다.

큐(Queue) 사용법

Queue 값 선언

import java.util.LinkedList; //import
import java.util.Queue; //import
Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언, linkedlist 이용
Queue<String> queue = new LinkedList<>(); //String형 queue 선언, linkedlist 이용

자바에서 큐는 LinkedList를 활용하여 생성해야 합니다. Queue와 LinkedList가 다 import되어 있어야 사용이 가능합니다. Queue queue = new LinkedList<>(); 이렇게 선언해야 합니다.

큐(Queue)의 연산

Queue 값 추가

 Queue<Integer> stack = new LinkedList<>(); //int형 queue 선언
queue.add(1);     // queue에 값 1 추가
queue.add(2);     // queue에 값 2 추가
queue.offer(3);   // queue에 값 3 추가

자바에서 queue에 값을 추가하고 싶다면 add(value) 또는 offer(value) 라는 메서드를 활용하면 됩니다.
add(value) 메소드의 경우 만약 삽입에 성공하면 true를 반환하고, 큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생시킵니다.

Queue 값 삭제

 Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언
queue.offer(1);     // queue에 값 1 추가
queue.offer(2);     // queue에 값 2 추가
queue.offer(3);     // queue에 값 3 추가
queue.poll();       // queue에 첫번째 값을 반환하고 제거 비어있다면 null
queue.remove();     // queue에 첫번째 값 제거
queue.clear();      // queue 초기화

queue에서 값을 제거할 땐 poll()이나 remove() 메서드를 사용합니다.
poll() 함수는 큐가 비어있으면 null을 반환합니다.
pop()을 하면 가장 앞쪽에 있는 원소의 값이 제거됩니다.
queue의 모든 요소를 제거할 땐 clear()메서드를 사용합니다.

Queue 값 출력

  Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언
  
queue.offer(1);     // queue에 값 1 추가
queue.offer(2);     // queue에 값 2 추가
queue.offer(3);     // queue에 값 3 추가
queue.peek();       // queue의 첫번째 값 참조