[JAVA/자료구조] 큐(Queue)와
스택(Stack) 구현하기
Java로 큐와 스택을 구현을 해봅시다
우선 큐와 스택을 알아야겠죠?
큐(Queue)란 선입선출 구조입니다.
먼저들어온게 먼저나간다는 소리입니다.
예를 들면 영화 티켓구매하기 위해서는 줄을 서야하겠죠?
맨 앞사람이 가장 빨리 왔으니 가장빨리 예매를 하겠죠?
그림으로 보자면
반대로 스택(Stack)은 후입선출 구조입니다.
나중에 들어온게 먼저 나간다는 소리입니다.
예를 들자면 뷔폐에 있는 접시를 생각하면 되겠습니다.
맨 위에 접시가 올려지고
맨 위 접시가 가장 빨리 나갑니다.
그림으로 보자면
그럼 이제 큐와 스택을 이해했으니
실제로 구현을 해봅시다
먼저 큐(Queue) 입니다.
public class Queue {
private int front;
private int rear;
private int maxSize;
private Object[] queue;
// 처음 큐 생성
public Queue(int maxSize) {
this.maxSize = maxSize;
this.front = 0;
this.rear = -1;
this.queue = new Object[maxSize];
}
// 꽉차있는지 확인
public boolean full() {
return (rear == maxSize-1);
}
// 비어있는지 확인
public boolean empty() {
return (front == rear+1);
}
// 큐에 객체 넣기
public void insert(Object item) {
if(full()) throw new ArrayIndexOutOfBoundsException();
queue[++rear] = item;
}
// 큐 객체 가져오기
public Object peek() {
if(empty()) throw new ArrayIndexOutOfBoundsException();
return queue[front];
}
// 큐 객체 삭제하기
public Object remove() {
Object item = peek();
front++;
return item;
}
public static void main(String[] args) {
Queue queue = new Queue(10);
queue.insert(1);
queue.insert(2);
queue.insert(3);
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
}
}
다음은 스택(Stack) 입니다.
public class Stack {
private int top;
private int maxSize;
private Object[] stack;
//배열 생성, 스택 생성
public Stack(int maxSize) {
this.maxSize = maxSize;
this.stack = new Object[maxSize];
this.top = -1;
}
public boolean emtpy() {
return (top == -1);
}
public boolean full() {
return (top == maxSize-1);
}
// 스택 객체 넣기
public void push(Object item) {
if(full()) {
throw new ArrayIndexOutOfBoundsException();
}
stack[++top] = item;
}
// 스택 객체 선택
public Object peek() {
if(emtpy()) {
throw new ArrayIndexOutOfBoundsException();
}
return stack[top];
}
// 스택 객체 빼기
public Object pop() {
Object item = peek();
top--;
return item;
}
public static void main(String[] args) {
Stack stack = new Stack(10);
stack.push(1);
stack.push(2);
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
}
}
여기까지가 큐와 스택 규현 입니다.
이만 큐(Queue)와 스택(Stack) 구현하기 포스팅을 마치겠습니다.
