스택과 큐
스택이란?
데이터를 차곡 차곡 쌓아 올린 형태의 자료구조이다.
데이터가 순서대로 쌓이며,
가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조이다.
특징
후입 선출(LIFO - Last In First Out)
데이터를 한 방향으로만 저장 할 수 있고 최상층(Top)으로 정한 곳에 위치한 데이터만 삽입/조회/삭제 할 수 있다.
스택의 활용 예시
- 웹 브라우저 방문 기록(뒤로가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
- 역순 문자열 만들기: 가장 나중에 입력된 문자부터 출력
- 실행 취소: 가장 나중에 실행된 것부터 실행을 취소
- 후위 표기법
- DFS
Java의 Stack 구현
인터페이스 정의
public interface MyStack<T> {
boolean isEmpty();
boolean isFull();
void push(T element);
T peek();
T pop();
void clear();
}클래스 구현
/*
isEmpty(), isFull() : 각각 스택이 비어있는지, 가득찼는지를 boolean 형태로 리턴하는 메서드.
push() : 스택에 새로운 원소를 삽입한다. 가득 차 있다면 예외를 던진다.
peek() : 최상층에 위치한 데이터를 읽어온다.
pop() : 최상층에 위치한 데이터를 읽어오고 해당 데이터를 스택에서 제거한다.
* */
public class MyStackImpl<T> implements MyStack<T> {
private List<Optional<T>> myStack;
private int limit;
public MyStackImpl(int size) {
this.myStack = new LinkedList<>();
this.limit = size;
}
@Override
public boolean isEmpty() {
return this.myStack.isEmpty();
}
@Override
public boolean isFull() {
return this.myStack.size() == limit;
}
@Override
public void push(T element) throws FullException {
if (this.myStack.size() == limit) {
throw new FullException();
}
this.myStack.add(Optional.ofNullable(element));
}
@Override
public T peek() throws EmptyException {
try {
return this.myStack.get(myStack.size() - 1).orElseThrow(EmptyException::new);
} catch (IndexOutOfBoundsException e) {
throw new EmptyException();
}
}
@Override
public T pop() throws EmptyException {
try {
return myStack.remove(myStack.size() - 1).orElseThrow(EmptyException::new);
} catch (IndexOutOfBoundsException e) {
throw new EmptyException();
}
}
@Override
public void clear() {
myStack.clear();
}
}예외 처리
public class FullException extends RuntimeException {
public FullException() {}
public FullException(String message) {
super(message);
}
}public class EmptyException extends RuntimeException {
public EmptyException() {}
public EmptyException(String message) {
super(message);
}
}Stack 시간복잡도
삽입,삭제: O(1)
조회: O(n) 단, top의 데이터 조회는 O(1)
큐(Queue)
Queue란?
큐(Queue)는 한쪽 끝에서만 삽입이 이루어지고, 다른 한쪽 끝에서는 삭제 연산만 이루어지는 유한 순서 리스트이다
특징
First in First Out (FIFO) 선입선출 구조
Queue(이하 '큐')란 데이터를 순서대로 줄을 세운 형태의 자료구조를 뜻한다.
프론트(Front)로 정한 곳에서는 조회/삭제 연산이 일어나고, 리어(Rear)로 정한 곳에서 삽입 연산 발생.
큐의 활용 예시
- 티켓 판매부스에서 줄을 기다리는 사람들
- 한줄로 나란히 가야만하는 차들
- 컴퓨터 운영체제의 테스크 스케줄링
- 버퍼
- BFS
- 캐시 구현
- 프린터의 인쇄 작업 관리
큐 구현
자바에서는 스택을 클래스로 구현하여 제공하지만,
큐는 Queue인터페이스만 있고 별도의 클래스가 없다.
그래서 Queue인터페이스를 구현한 클래스들을 사용해야 한다.
인터페이스 정의
public interface MyQueue<T> {
boolean isEmpty();
boolean isFull();
void enqueue(T element);
T peek();
T dequeue();
void clear();
}클래스 구현
/*
isEmpty(), isFull() : 앞서 설명한 스택과 동일, 각각 큐가 비었는지, 가득 찼는지를 boolean 형태로 반환.<br/>
enqueue() : 큐에 새로운 원소를 삽입한다. 가득 차 있다면 예외를 던진다.
peek() : 최하층에 위치한 데이터를 읽어온다.
dequeue() : 최하층에 위치한 데이터를 읽어오고 해당 데이터를 큐에서 제거한다.
* */
public class MyQueueImpl<T> implements MyQueue<T> {
private List<Optional<T>> myQueue;
private int limit;
public MyQueueImpl(int size) {
this.myQueue = new LinkedList<>();
this.limit = size;
}
@Override
public boolean isEmpty() {
return this.myQueue.isEmpty();
}
@Override
public boolean isFull() {
return this.myQueue.size() == limit;
}
@Override
public void enqueue(T element) throws FullException {
if (isFull()) {
throw new FullException();
}
myQueue.add(Optional.ofNullable(element));
}
@Override
public T peek() throws EmptyException {
try {
return this.myQueue.get(0).orElseThrow(EmptyException::new);
} catch (IndexOutOfBoundsException e) {
throw new EmptyException();
}
}
@Override
public T dequeue() throws EmptyException {
try {
return this.myQueue.remove(0).orElseThrow(EmptyException::new);
} catch (IndexOutOfBoundsException e) {
throw new EmptyException();
}
}
@Override
public void clear() {
this.myQueue.clear();
}
}예외 처리
public class FullException extends RuntimeException {
public FullException() {}
public FullException(String message) {
super(message);
}
}public class EmptyException extends RuntimeException {
public EmptyException() {}
public EmptyException(String message) {
super(message);
}
}큐 직접 구현 방법 2가지
큐를 구현하는 방법에는 두 가지가 있다.
- 배열 사용
장점 : 구현하기 쉬움.
단점 : 크기가 동적이 아님. 런타임 시 필요에 따라 늘어나거나 줄어들지 않음.
- 연결 리스트 사용
장점 : 크기가 동적임. 런타임시 필요에 따라 크기가 확장 및 축소될 수 있음.
단점 : 포인터를 위한 추가 메모리 공간이 필요함.
Array-Base
/*
queuelsEmpty() : 큐 안이 비었는지 판단하는 함수
queueIsFull() : 배열의 최대크기를 벗어나면 안되기에 큐에 더이상 들어갈 공간이 없는지 판단하는 함수
size() : queue에 현재 들어가 있는 데이터의 개수를 return하는 함수
push(int value) : 큐 안에 데이터를 집어넣는 함수
peek() : 큐 안의 데이터들중 가장 먼저 나오는 데이터를 return 하는 함수
pop() : 큐 안의 데이터들 중 가장 먼저 나올수 있는 데이터를 return 하고 삭제하는 함수
* */
public class ArrayQueue {
int MAX = 1000;
int front; //머리 쪽에 위치할 index값, pop할때 참조하는 index
int rear; //꼬리 쪽에 위치할 index값, push할때 참조하는 index
int [] queue;
public ArrayQueue() {
front = rear = 0; //초기값 0
queue = new int[MAX]; //배열 생성
}
public boolean queueisEmpty() { //queue에 아무것도 들어있지 않은지 판단하는 함수
return front == rear;
}
public boolean queueisFull() { //queue가 가득 차 공간이 없는지 판단하는 함수
if(rear == MAX-1) {
return true;
}else
return false;
}
public int size() { //queue에 현재 들어가 있는 데이터의 개수를 return
return front-rear;
}
public void push(int value) {
if(queueisFull()) {
System.out.println("Queue is Full");
return;
}
queue[rear++] = value; //rear가 위치한 곳에 값을 넣어주고 rear를 증가시킨다.
}
public int pop() {
if(queueisEmpty()) {
System.out.println("Queue is Empty");
return -1;
}
int popValue = queue[front++];
return popValue;
}
public int peek() {
if(queueisEmpty()) {
System.out.println("Queue is Empty");
return -1;
}
int popValue = queue[front];
return popValue;
}
}배열을 이용한 선형큐의 단점
- 선형 큐에서 삽입 및 삭제를 반복하다 보면, rear가 맨 마지막 인덱스를 가리키고, 앞에는 비어 있을 수 있지만 이를 꽉 찼다고 인식한다.
- Rear가 배열의 끝까지 이동이 되면 더이상 새로운 데이터를 받을 수 없음.
가득 찼다고 판단
이런경우를 해결하려면 재정렬이 필요하다.
이를 개선한 것이 '원형 큐'
논리적으로 배열의 처음과 끝이 연결되어 있는 것으로 간주함!
원형 큐는 초기 공백 상태일 때 front와 rear가 0
공백, 포화 상태를 쉽게 구분하기 위해 자리 하나를 항상 비워둠
(index + 1) % size로 순환시킨다원형 큐(Circular queue)
Rear를 다시 첫번째를 가리키게 하여 저장공간을 순환적으로 사용하는 큐
선형큐의 단점을 보완하기 위해 만들어졌다.
rear와 front가 같은 곳을 가리키는 경우 빈 원형큐를 의미
rear+1%size가 front와 같으면 가득찬 것
원형 큐 구현
/* 원형 큐
* front : int - 초기 값 0, 처음 데이터의 바로 전 인덱스
* rear : int - 초기 값 0, 마지막 데이터의 인덱스
* isEmpty() : boolean - 큐가 비어있는가
* isFull() : boolean - 큐가 가득 찼는가
* enqueue() : void - 데이터 넣기
* dequeue() : void - 데이터 빼기
* diplay() : void - 데이터 출력
* */
public class Queue {
private final int MAX_SIZE = 5;
private int front, rear;
private int[] queue;
public Queue2() {
front = rear = 0;
queue = new int[MAX_SIZE];
}
// front와 rear이 같은 위치에 있다면 큐가 비어있다는 뜻이다.
private boolean isEmpty() {
return front == rear;
}
// rear이 front의 바로 전 위치에 있다면 큐가 가득찼다는 뜻이다.
private boolean isFull() {
return (rear+1) % MAX_SIZE == front;
}
// 데이터가 들어갈 땐 rear만 움직인다.
// rear의 위치는 최근에 들어온 데이터의 위치이다.
// 즉, 새로운 데이터가 들어오기 위해 먼저 이동해야한다.
public void enqueue(int data) {
// 큐가 가득차면 들어갈 수 없다 -> 리턴
if (isFull())
System.out.println("It's FULL!!!");
// 큐에 자리가 있다면 데이터를 넣는다.
else {
rear = (++rear) % MAX_SIZE; //원형 큐이기 때문에 순환한다.
queue[rear] = data;
}
}
// 데이터가 나갈 땐 front만 움직인다.
public int dequeue() {
int preIndex;
// 큐가 비어있다면 데이터를 뺄 수 없다. 나는 데이터가 없다는 신호로 -1을 리턴했다(임시 정의)
if (isEmpty())
return -1;
// 큐에 데이터가 있다면 데이터를 뺀다. front 이동(증가)
else {
preIndex = front;
front = (++front) % MAX_SIZE;
}
return queue[preIndex];
}
public void display() {
System.out.println("FRONT :"+front+" REAR :"+rear);
System.out.print("QUEUE DATA: ");
for(int index = front + 1; index != (rear+1) % MAX_SIZE; index = (index+1) % MAX_SIZE)
System.out.print(queue[index] + " ");
System.out.println();
System.out.println();
}
}원형 큐의 단점 : 메모리 공간은 잘 활용하지만, 배열로 구현되어 있기 때문에 큐의 크기가 제한
이를 개선한 것이 '연결리스트 큐'
연결리스트 큐는 크기가 제한이 없고 삽입, 삭제가 편리
List-Base
public class QueueNode {
int value; //값을 넣음
QueueNode queueNode; //다음 노드를 가리킴
public QueueNode(int value) {
this.value = value;
queueNode = null;
}
public int getValue() {
return value;
}
public QueueNode getNextNode() {
return queueNode;
}
public void setNextNode(QueueNode queueNode) {
this.queueNode = queueNode;
}
}
public class QueueNodeManager{ //큐의 기능을 만들 클래스
QueueNode front,rear;
public QueueNodeManager() {
front = rear = null;
}
public boolean queueisEmpty() {
if(front == null && rear == null) {
return true;
}else {
return false;
}
}
public void push(int value) {
QueueNode queueNode = new QueueNode(value);
if(queueisEmpty()) { //큐안에 데이터가 없으면 첫번째 Node에 front와 rear를 연결
front = rear = queueNode;
}else {
front.setNextNode(queueNode); //큐 안에 데이터가 있으면 front를 다음 노드에 연결 후 front의 값을 마지막 노드로 삽입
front = queueNode;
}
}
public QueueNode pop() {
if(queueisEmpty()) {
System.out.println("Queue is Empty");
return null;
}else {
QueueNode popNode = rear;
rear = rear.getNextNode();
return popNode;
}
}
public QueueNode peek() {
if(queueisEmpty()) {
System.out.println("Queue is Empty");
return null;
}else {
return rear;
}
}
public int size() {
QueueNode front2 = front;
QueueNode rear2 = rear;
int count = 0;
while(front2 != rear2 && rear2 !=null) { //큐가 비어있는 경우가 있을수도 있을때도 생각해야함
count++;
rear2 = rear2.getNextNode();
}
return count;
}
}LinkedList로 Queue를 만들게 되면 구현은 복잡하지만 큐의 크기도 무한하고 Queue안에 원하는 기능을 넣을수도 있다는 장점이 있다.
선형 큐, 원형 큐 시간 복잡도
삽입, 삭제 : O(1)
조회 : O(n)
우선순위 큐(Priority queue)
큐는 먼저 들어오는 데이터가 먼저 나가는 선입선출 (FIFO) 형식의 자료구조지만
우선순위 큐는 들어오는 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.
우선순위 큐는 힙(Heap)을 이용하여 구현하는 것이 가장 효율적이다.
🍰 예상 질문
- Stack은 어떤 자료구조인가요?
- Queue는 어떤 자료구조인가요?
- 원형큐(Circular queue)는 무슨 자료구조인가요?
- 큐 구현할 때 Array-Base와 List-Base의 경우 어떤 차이가 있나요?
- Stack 두 개를 이용하여 Queue를 구현해보세요.
- 시간복잡도는 어떻게 되는지 설명해주세요
- 시간복잡도는 어떻게 되는지 설명해주세요
- Queue 두 개를 이용하여 Stack을 구현해보세요.
- Queue vs priority를 비교하여 설명해주세요.
- 우선순위 큐의 구현 방법은?
- Stack과 Queue의 차이점은 무엇인가요?
- Stack과 Queue의 실사용 예를 들어 간단히 설명해주세요.
- Stack 클래스를 손코딩으로 구현해주세요.
기본부터