데이터를 일시적으로 저장하기 위한 자료구조로, 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.
(후입선출 - Last In First Out)
public class IntArrayStack {
private int max; // 스택용량
private int top; // 스택 포인터 top (스택에 쌓여있는 데이터 수)
private int[] stk; // 스택 본체
public IntArrayStack(int capacity) {
top = 0;
max = capacity;
stk = new int[max];
}
/** 스택에 데이터를 push */
public void push(int x) {
if (isFull())
throw new OverflowStackException();
stk[top++] = x;
}
/** 스택의 꼭대기(top)에서 데이터를 pop */
public int pop() {
if (isEmpty())
throw new EmptyStackException();
return stk[--top];
}
/** 스택 꼭대기(top)에 있는 데이터 조회 */
public int peek() {
if (isEmpty())
throw new EmptyStackException();
return stk[top - 1];
}
/** 스택이 비어 있는지 여부 */
public boolean isEmpty() {
return top <= 0;
}
/** 스택이 가득 찼는지 여부 */
public boolean isFull() {
return top >= max;
}
}
public class Node {
private int data;
private Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
// getter, setter
}
public class IntLinkedListStack {
private Node top;
private int size;
/** 스택에 데이터를 push */
public void push(int x) {
Node node = new Node(x);
node.setNext(top);
top = node;
size++;
}
/** 스택의 꼭대기(top)에서 데이터를 pop */
public int pop() {
if (isEmpty())
throw new EmptyStackException();
int result = top.getData();
top = top.getNext();
size--;
return result;
}
/** 스택 꼭대기(top)에 있는 데이터 조회 */
public int peek() {
if (isEmpty())
throw new EmptyStackException();
return top.getData();
}
/** 스택이 비어 있는지 여부 */
public boolean isEmpty() {
return size == 0;
}
}
배열 → 검색 빈번, 등록/수정 적음
연결리스트 → 등록/수정 빈번, 검색 적음
데이터를 일시적으로 저장하기 위한 자료구조로, 가장 먼저 넣은 데이터를 가장 먼저 꺼낸다.
(선입선출 - First In First Out)
public class IntArrayQueue {
private int max; // 큐의 용량
private int front; // 첫 번째 요소 커서
private int rear; // 마지막 요소의 하나 뒤의 인덱스 커서
private int size; // 현재 데이터 수
private int[] que; // 큐 본체
public IntArrayQueue(int capacity) {
size = front = rear = 0;
max = capacity;
que = new int[max];
}
/** 큐에 데이터를 enQueue */
public void enQueue(int x) {
if (isFull())
throw new OverflowQueueException();
que[rear] = x;
rear = (rear + 1) % max; // 원형 큐*
size++;
}
/** 큐의 맨 앞에서 데이터를 deQueue */
public int deQueue() {
if (isEmpty())
throw new EmptyQueueException();
int x = que[front];
front = (front + 1) % max; // 원형 큐
size--;
return x;
}
/** 큐의 맨 앞의 데이터 조회 */
public int peek() {
if (isEmpty())
throw new EmptyQueueException();
return que[front];
}
/** 큐가 비었는지 여부 */
public boolean isEmpty() {
return size <= 0;
}
/** 큐가 가득찼는지 여부 */
public boolean isFull() {
return size >= max;
}
}
public class IntLinkedListQueue {
private Node front;
private Node rear;
private int size;
/** 큐에 데이터를 enQueue */
public void enQueue(int x) {
Node node = new Node(x);
if (rear != null)
rear.setNext(node);
rear = node;
if (front == null)
front = rear;
size++;
}
/** 큐의 맨 앞에서 데이터를 deQueue */
public int deQueue() {
if (isEmpty())
throw new EmptyQueueException();
int result = front.getData();
front = front.getNext();
size--;
return result;
}
/** 큐의 맨 앞의 데이터 조회 */
public int peek() {
if (isEmpty())
throw new EmptyQueueException();
return front.getData();
}
/** 큐가 비었는지 여부 */
public boolean isEmpty() {
return size == 0;
}
}
배열 → 검색 빈번, 등록/수정 적음
연결리스트 → 등록/수정 빈번, 검색 적음