Stack(스택)과 Queue(큐)

스택(Stack)이란?

스택은 데이터가 들어온 순서대로 차곡차곡 쌓이는 형태의 기억공간을 말한다.

출력 시 가장 나중에 쌓인 데이터가 제일 먼저 출력을 하게 된다.

그러므로 스택을 선입후출 혹은 LIFO(Last In First Out)이라고도 부른다

스택에서는 TOP, POP, PUSH라는 용어를 사용한다.

TOP이란 스택의 맨 위의 데이터인 즉, 최근에 들어온 데이터를 가리키는 화살표라고 생각하면 된다.

데이터가 입/출력이 되면 이 TOP이란 화살표는 움직이면서 스택안에서 데이터가 최대 몇개가 저장되어있는지 알 수가 있다.

POP이란 스택에 있는 데이터를 이용해 연산을 할 때에 데이터를 삭제하기 위한 것이다.

PUSH란 데이터를 삽입하기 위한 것이다. TOP이 다음 데이터가 돌아올 자리로 이동하면 그 자리에 데이터를 삽입한다.

다음은 Stack을 자바로 구현한 코드이다.

class Stack { int top; int[] stack; int size; public Stack(int size) { top = -1; stack = new int[size]; this.size = size; } public void peek() { System.out.println("PEEK : " + stack[top]); } public void push(int value) { stack[++top] = value; System.out.println(stack[top] + " PUSH !"); } public int pop() { System.out.println(stack[top] + " POP !"); return stack[top--]; } public void printStack() { System.out.println("-- STACK LIST --"); for (int i = top; i >= 0; i--) System.out.println(stack[i]); System.out.println("-- END OF LIST --"); } }

큐(Queue)란?

큐는 데이터가 쌓이다가 가장 먼저 들어온 데이터가 나가는 구조이다.

따라서 선입선출 혹은 FIFO(First In First Out)이라고 한다.

큐에서 삭제되는 위치를 Front라 하고, 삽입되는 위치를 Rear라고 한다.

또한 큐에 데이터를 삽입하는 작업을 Enqueue, 빼는 작업을 Dequeue라고 한다.

삽입과 삭제 작업이 일어날때마다 Front와 Rear는 움직인다.

그런데 큐가 비어있었을 때 삭제 작업을 한다면 Queue Underflow가 발생한다.

마찬가지로 큐가 꽉 차있을 경우 삽입을 하려한다면 Queue Overflow가 발생한다. 

원형 큐는 무엇인가?

선형 큐를 구현하면서 문제는 주기적으로 enqueue 되고 dequeue되면 인덱스를 조정하면서

front가 점차 뒤로 가게되면서 앞쪽 메모리 공간을 효율적으로 사용 할 수 없게 된다. 

그래서 메모리 공간을 다 쓰면 다시 앞으로 돌아와서 메모리공간에 enqueue, dequeue 할 수 있는 원형 큐가

필요하게 된 것이다.

다음은 원형 Queue를 자바로 구현한 코드이다.

public class CirCularQueue {

int size = 0;

int front = 0, rear = 0;

int[] queue;

public CirCularQueue(int size){

this.size = size;

queue = new int[size];

}

public void Enqueue(int data){

if((rear + 1) % ArraySize ==  front % ArraySize){

System.out.println("CircularQueue Full!!");

}

else{

rear = (rear + 1) % ArraySize;

arr[rear] = data;

}

}

public void Dequeue(){

if(front == rear){

System.out.println("CircularQueue Empty!!");

}

else{

front = (front + 1) % ArraySize;

System.out.println(arr[front]);

}

}

public void showArray(){

for(int i = 1;i<ArraySize;i++){

System.out.print(arr[i] + " ");

}

System.out.println();

}

}

※ 출처 : http://dreamstorage.tistory.com/132, http://slenderankle.tistory.com/305