스택과 큐
스택
스택의 개념
- 스택 (STACK) : 데이터를 쌓아올리는 형태의 자료구조
- 예 : 접시 더미, 책상에 쌓여있는 책, 창고에 쌓여있는 상자 등
스택의 특징
- 후입선출 (LIFO: Last-In First-out) 방식
- 가장 최근에 들어온 데이터가 가장 위에 있으며 가장 먼저 나간다.
- 데이터의 들어오는 방향과 나가는 방향이 같은 단방향 입출력 구조이다.
- 스택에서 입출력은 맨 위에서만 일어나며 스택의 중간에서는 데이터를 삭제할 수 없다.
- 예: 스택에 A, B, C, D 순서대로 입력한 후 하나를 삭제하면 맨 위에 놓여진 D가 삭제된다.
스택의 구조
- 스택 상단 (stack top) : 입출력이 이루어지는 부분
- 스택 하단 (stack botton) : 스택 상단 반대쪽인 바닥 부분
- 요소 (element) : 스택에 저장되는 것
- 공백 스택 (empty stack) : 요소가 하나도 없는 스택
주요 메소드
- is_full :
- 스택이 포화상태에 있는지 검사하는 함수
- 반환 타입 boolean
- is_empty :
- 스택이 공백상태에 있는지 검사하는 함수
- 반환 타입 boolean
- push :
- 스택 맨 위에 요소 삽입
- 스택이 가득차서 입력이 불가능하면 오류 발생
- pop :
- 스택의 맨 위의 요소를 스택에서 완전히 삭제하면서 반환
- 공백 스택일 경우 출력이 불가능하여 오류 발생
- peek :
- 스택의 맨 위의 요소를 삭제하지 않고 반환 (보기만 하는 연산)
- 공백 스택일 경우 출력이 불가능하여 오류 발생
스택의 구현
import java.util.Stack; // 스택(Stack) 제공 클래스
public class stack {
public static void main(String[] args) {
// 스택(Stack) 선언
Stack<Integer> stackInt = new Stack<>(); //int형
Stack<String> stackString = new Stack<>(); //string형
Stack<Boolean> stackBoolean = new Stack<>(); // boolean형
// Push
stackInt.push(1); // 1 삽입
stackInt.push(2); // 2 삽입
stackInt.push(3); // 3 삽입
System.out.println(stackInt); // 출력 : [1, 2, 3]
// Peek
stackInt.peek();
System.out.println(stackInt.peek()); // 출력 : 3
// Pop
stackInt.pop(); // 3 삭제
System.out.println(stackInt.pop()); // 2 삭제, 출력 : 2
System.out.println(stackInt); // 출력 : [1]
// isEmpty
System.out.println(stackString.isEmpty()); // 출력 : true
stackString.push("a"); // "a" 삽입
System.out.println(stackString.isEmpty()); // 출력 : false
}
}
public class ArrayStack {
int size;
int top;
Object[] stack;
public ArrayStack(int size) {
this.size = size;
top = -1;
stack = new Object[size];
}
// isEmpty
public boolean isEmpty() {
return (top == -1);
}
// isFull
public boolean isFull() {
return (top == (this.size - 1));
}
// push
public void push(Object element) {
if (isFull()) {
System.out.println("스택 포화 에러");
return;
}
else {
stack[++top] = element;
}
}
// pop
public Object pop() {
if (isEmpty()) {
System.out.println("스택 공백 에러");
return null;
}
else {
return stack[top--];
}
}
// peek
public Object peek() {
if (isEmpty()) {
System.out.println("스택 공백 에러");
return null;
}
else {
return stack[top];
}
}
public static void main(String[] args) {
ArrayStack arrStack = new ArrayStack(10);
arrStack.push(1); // 1 삽입
arrStack.push(2); // 2 삽입
arrStack.push(3); // 3 삽입
System.out.println(arrStack.peek()); // 출력 : 3
System.out.println(arrStack.pop()); // 출력 : 3
System.out.println(arrStack.pop()); // 출력 : 2
System.out.println(arrStack.pop()); // 출력 : 1
}
}
큐
큐의 개념
- 큐 (QUEUE) : 데이터를 일렬로 줄을 세운 형태의 자료구조
- 예 : 매표소 대기 줄 등
큐의 특징
- 선입선출 (FIFO: First-In First-out) 방식
- 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제된다.
- 삽입과 삭제가 다른 쪽에서 일어난다.
- 예: 큐에 A, B, C, D 순서대로 입력한 후 하나를 삭제하면 맨 앞에 놓여진 A가 삭제된다.
큐의 구조
- 후단 (rear) : 삽입이 일어나는 곳
- 전단 (front) : 삭제가 일어나는 곳
주요 메소드
- is_full :
- 큐가 포화상태에 있는지 검사하는 함수
- 반환 타입 boolean
- is_empty :
- 큐가 공백상태에 있는지 검사하는 함수
- 반환 타입 boolean
- enqueue :
- 큐의 맨 뒤에 새로운 요소 추가
- 큐가 가득차서 입력이 불가능하면 오류 발생
- dequeue :
- 큐의 맨 앞에 있는 요소를 꺼내서 삭제하고 반환
- peek :
- 큐의 맨 앞의 요소를 삭제하지 않고 반환 (보기만 하는 연산)
큐의 구현
// 큐(Queue) 제공 클래스
import java.util.Queue;
import java.util.LinkedList;
public class queue {
public static void main(String[] args) {
// 큐(Queue) 선언
Queue<Integer> queueInt = new LinkedList<>(); //int형
Queue<String> queueString = new LinkedList<>(); //string형
Queue<Boolean> queueBoolean = new LinkedList<>(); // boolean형
// enqueue
queueInt.add(1); // 1 삽입 - 실패 시 Exception
queueInt.add(2); // 2 삽입
queueInt.offer(3); // 3 삽입 - 실패 시 false 반환
queueInt.offer(4); // 4 삽입
System.out.println(queueInt); // 출력 : [1, 2, 3, 4]
// peek
queueInt.element(); // 공백 큐일 시 - Exception
System.out.println(queueInt.element()); // 출력 : 1
queueInt.peek(); // 공백 큐일 시 - null 반환
System.out.println(queueInt.peek()); // 출력 : 1
// dequeue
queueInt.remove(); // 1 삭제 - 실패 시 Exception
System.out.println(queueInt.remove()); // 2 삭제, 출력 : 2
queueInt.poll(); // 3 삭제 - 실패 시 null 반환
System.out.println(queueInt.poll()); // 4 삭제, 출력 : 4
// isEmpty
System.out.println(queueString.isEmpty()); // 출력 : true
queueString.add("a"); // "a" 삽입
System.out.println(queueString.isEmpty()); // 출력 : false
}
}
public class ArrayQueue {
int size;
int front;
int rear;
Object[] queue;
public ArrayQueue(int size){
this.size = size;
front = -1;
rear = -1;
queue = new Object[size];
}
// isEmpty
public boolean isEmpty() {
return front == rear;
}
// isFull
public boolean isFull() {
if (rear == this.size - 1) {
return true;
}
else {
return false;
}
}
// enqueue
public void enqueue(Object element) {
if (isFull()) {
System.out.println("큐 포화 에러");
return;
}
else {
queue[++rear] = element;
}
}
// dequeue
public Object dequeue() {
if (isEmpty()) {
System.out.println("큐 공백 에러");
return null;
}
else {
return queue[++front];
}
}
public static void main(String[] args) {
ArrayQueue arrQueue = new ArrayQueue(5);
arrQueue.enqueue(1); // 1 삽입
arrQueue.enqueue(2); // 2 삽입
arrQueue.enqueue(3); // 3 삽입
System.out.println(arrQueue.dequeue()); // 출력 : 1
System.out.println(arrQueue.dequeue()); // 출력 : 2
System.out.println(arrQueue.dequeue()); // 출력 : 3
}
}