[Java] ArrayList로 스택(stack)과 큐(Queue) 구현하기

프로그램을 개발할 때 가장 많이 사용하는 자료 구조인 스택과 큐에 대해 살펴보자.

스택은 맨나중에 추가된 데이터를 먼저 꺼내는(List in First Out : LIFO) 방식이다.

큐는 일상 생활에서 많이 사용하는 선착순을 생각하면 된다.

줄을 선 대기열처럼 먼저 추가된 데이터부터 꺼내서 사용하는 (First In First Out : FIFO) 방식이다.

 

스택은 가장 최근에 추가된 자료부터 반환해 준다. 가장 최근에 검색한 단어를 찾거나 장기, 체스 같은 게임에서 수를 무를 때도 응용 가능하다. 스택에 자료를 추가하는 것을 push() , 자료를 꺼내는 것을 pop()이라고 한다. 예제를 확인해보자

class MyStack{
	
	private ArrayList<String> arrayStack = new ArrayList<String>();
	
	public void push(String data) { //엘리먼트 받아서 넣기
		arrayStack.add(data);  // 스택의 맨 뒤에 요소를 추가
	}
	
	public String pop() { //pop은 꺼내면서 삭제
		
		int len = arrayStack.size();
		if(len==0) { //len에 스택사이즈 대입해서 len이 비어있으면 아래를 출력
			System.out.println("스택이 비었습니다.");
			return null;
		}
		//데이터가 0이아니면 내려와서 size-1번째 꺼내서 삭제
		return arrayStack.remove(len-1);
		
	}
	
	public String peek() { //peek은 집어들어 확인하고 내려놓음
		int len = arrayStack.size();
		if(len==0) {
			System.out.println("스택이 비었습니다.");
			return null;
		}
		// get은 꺼내보기 remove는 확인후 삭제
		return arrayStack.get(len-1);
	}
}

public class StackTest {

	public static void main(String[] args) {

		MyStack stack = new MyStack();
		
		stack.push("a");
		stack.push("b");
		stack.push("c");
		
		System.out.println(stack.peek());
		System.out.println(stack.peek());
		System.out.println(stack.pop());
		
		System.out.println(stack.pop());
		System.out.println(stack.pop());
		System.out.println(stack.pop());
			
	}

}

출력결과

C

B

A

 

큐를 구현한 예제를 확인해보자

import java.util.ArrayList;

class MyQueue {
	
	private ArrayList<String> arrayQueue = new ArrayList<String>();
	
	public void enQueue(String data) { 
		arrayQueue.add(data);  // 큐의 맨 뒤에 추가
	}
	
	public String deQueue() {
		int len = arrayQueue.size();
		
		if(len==0) {
			System.out.println("큐가 비었습니다.");
			return null;
		}
		return arrayQueue.remove(0); // 맨 앞의 자료를 반환하고 배열에서 제거
	}
}

public class QueueTest {

	public static void main(String[] args) {
		
		MyQueue queue = new MyQueue();
		
		queue.enQueue("A");
		queue.enQueue("B");
		queue.enQueue("C");
		
		System.out.println(queue.deQueue());
		System.out.println(queue.deQueue());
		System.out.println(queue.deQueue());
	}

}

출력결과

A

B

C

간단힌 스택 큐 프로그램을 만들어보자

public  abstract class Memory {

	protected int []data; 
	protected int sum;
	protected int pos;
	
	public Memory() {
		data = new int[5]; // 배열사이즈는 작게 5로선언
		pos=0;
		sum = 0;
	}
	public void push(int num) {
		data[pos++] = num;  // push를 호출하면 data배열의 pos번째에 num대입후 pos는 1증가
	}
	public abstract int pop(); // 상속받은 클래스에 구현책임을 부여
	
	}

public class MyStack extends Memory{

	@Override
	public int pop() {
		
		return data[--pos]; // 스택에서 pop호출시 마지막 번호 바로전 값을 반환
	}
	}

public class MyQueue extends Memory{

	@Override
	public int pop() {
		
		int temp = data[sum++]; //배열의 첫번째를 빼와야함 Memory클래스에 sum=0; 이라고 선언해둠(배열의 첫번째)
		                        //Queue의 pop이 호출되면 0번째부터 한칸씩 증가(sum++)
		 if(sum == pos) {  // pos는  push()호출때 마다 1씩 증가했음
			 pos = -1;     // pop 호출시 sum은 첫번째 부터 증가하여 pos와sum이 같아 질때 종료 
			 sum = -1;
			 System.out.println("데이터가 없습니다.");
		 }
		return temp;
	}

import java.util.Scanner;

public class MyTest  {

	public static void main(String[] args) {

		
		Memory mem = null;
		MyStack ms = new MyStack();
		MyQueue mq = new MyQueue();
		
		Scanner sc = new Scanner(System.in);
		
		while(true) {
			System.out.println("1.stack  2.queue  3.End");
			int num  = sc.nextInt();
			
			if(num==1) mem = ms; // 1번 선택시 메모리에 MyStack을 대입
			else if (num==2) mem = mq; 2번 선택시 메모리에 MyQueue를 대입
			else System.exit(-1); // 다른숫자 입력시 종료
			
			while(true) {
				System.out.println("1.push  2.pop  3.back");
				int num2 = sc.nextInt();
				
				if(num2 ==1) {
					System.out.print("숫자 입력>>");
					mem.push(+sc.nextInt());
				}
				else if (num2==2) System.out.println(mem.pop()); // 선택에 따라 다른 pop호출
				else break;
			}
		}
	}
}