Java 3. 스택, 큐 구현

Stack의 특징

• 맨 마지막 위치(top)에서만 자료를 추가,삭제, 꺼내올 수 있음 ( 중간의 자료를 꺼낼 수 없음)
• 데이터를 - 제거해서 꺼내는것 : pop /// 넣는것 : push /// 제거하지않고 꺼내보기만 하는것 : pick
• Last In First Out ( 후입선출 ) 구조
• 택배 상자가 쌓여있는 모양
• 가장 최근의 자료를 찾아오거나 게임에서 히스토리를 유지하고 이를 무를때 사용할 수 있음
• 함수의 메모리는 호출 순서에 따른 stack 구조
• jdk 클래스 : Stack

 

배열 활용하여 Stack 구현하기~

import ch02.MyArray;

public class MyArrayStack {

	//멤버변수는 이렇게만 써놔도 자동으로 초기화가 됨
	int top; // int = 0, 객체인경우 = null, boolean = false로 초기화됨
	MyArray arrayStack; 
	
	public MyArrayStack()
	{
		top = 0;
		arrayStack = new MyArray();
	}
	
	//사이즈가 들어올경우
	public MyArrayStack(int size)
	{	//사이즈만큼 initialize
		top = 0;
		arrayStack = new MyArray(size);
	}
	
	//집어넣을때 - 배열이므로 꽉 찼는제 체크하기 -> 꽉찼으면 넣을수없음
	public void push(int data)
	{
		if(isFull()){ //꽉찼으면 에러메세지 
			System.out.println("stack is full");
			return;
		}
		arrayStack.addElement(data);
		top++; //배열의 맨뒤로 쭉쭉 들어가는것
	}
	
	public int pop()
	{
		if (top == 0){ //없다는것
			System.out.println("stack is empty");
			return MyArray.ERROR_NUM;
		}
		return arrayStack.removeElement(--top); //먼저 감소시키고 operation 진행
		
	}
	
	public boolean isFull()
	{
		if(top == arrayStack.ARRAY_SIZE){
			return true; // 꽉찼으면 return true(꽉찼다는 의미)
		}
		else return false;
	}
	
	public boolean isEmpty()
	{
		if (top == 0){
			System.out.println("stack is empty");
			return true;
		}
		else return false;
	}
	
	//어느데이터가 있는지 보는 것
	public int peek()
	{
		if (top == 0){
			System.out.println("stack is empty");
			return MyArray.ERROR_NUM;
		}
		return arrayStack.getElement(top-1);
	}
	
	public int getSize()
	{
		return top;
	}
	
	
	public void printAll()
	{
		arrayStack.printAll();
	}
}

public class MyArrayStackTest {

	public static void main(String[] args) {

		MyArrayStack stack = new MyArrayStack(3); //3개로 안만들고 디폴트로하면 10개 만들어짐
		
		stack.push(10);
		stack.push(20);
		stack.push(30);
		stack.push(40);
		
		stack.printAll();
		
		System.out.println("top element is " + stack.pop());
		stack.printAll();
		System.out.println("stack size is " + stack.getSize());
		
		System.out.println("stack.pop()");
		System.out.println("stack.push()");
		System.out.println("stack.peek()");
	}
}

 

Queue 구현하기

• 맨 앞(front) 에서 자료를 꺼내거나 삭제하고, 맨 뒤(rear)에서 자료를 추가 함
• Fist In First Out (선입선출) 구조
• 일상 생활에서 일렬로 줄 서 있는 모양
• 순차적으로 입력된 자료를 순서대로 처리하는데 많이 사용 되는 자료구조
• 콜센터에 들어온 문의 전화, 메세지 큐 등에 활용됨
• jdk 클래스 : ArrayList

LinkedList로 Queue구현하기

import ch03.MyLinkedList;
import ch03.MyListNode;

interface Queue{
	public void enQueue(String data);
	public String deQueue();
	public void printQueue();
}	

public class MyLinkedQueue extends MyLinkedList implements Queue {

	MyListNode front;
	MyListNode rear;
	
	//MyLinkedList의 addElement() 사용해서 string 타입으로 enQueue 
	@Override
	public void enQueue(String data) {
		MyListNode newNode;
		if( isEmpty()) { 
			//비어있는 큐에 맨 처음으로 들어가는 경우
			newNode = addElement(data);
			front = newNode;
			rear = newNode;
		}
		else {
			//큐의 맨 뒤에 들어가는 경우
			newNode = addElement(data);
			rear = newNode;
		}
		System.out.println(newNode.getData() + "added");
	}

	//제거 : remove는 0위치에서 하면 됨
	//MyLinkedList의 removeElement(int position) 사용해서 position을 0으로 하면 젤앞에서 deQueue
	@Override
	public String deQueue() {
		if(isEmpty()) {
			//큐가 비어있으면 deQueue작업 하지 못하므로 에러(null)발생
			return null;
		}
		String data = front.getData();
		front = front.next;
		
		if(front == null) {
			//마지막 항목 이라는 뜻
			rear= null;
		}
		return data;
	}

	@Override
	public void printQueue() {
		printAll();
	}

}

public class MyListQueueTest {

	public static void main(String[] args) {
		
		MyLinkedQueue listQueue = new MyLinkedQueue();
		listQueue.enQueue("A");
		listQueue.enQueue("B");
		listQueue.enQueue("C");

		listQueue.printAll();
		
		//deQueue의 반환값은 String이므로 System.out으로 출력
		System.out.println(listQueue.deQueue());
		System.out.println(listQueue.deQueue());
		
	}

}

 

출력

 

Aadded
Badded
Cadded
A->B->C
A
B