[JAVA] 스택(Stack)

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다.

---

스택

스택은 데이터를 일시적으로 저장하기 위한 자료구조로, 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.

데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out)이다. 스택에 데이터를 넣는 작업을 푸시라 하고, 스택에서 데이터를 꺼내는 작업을 팝이라고 한다.

이렇게 푸시와 팝을 하는 위치를 꼭대기(top)라 하고, 스택의 가장 아랫부분을 바닥(bottom)이라고 한다.

 

int 배열을 이용한 IntStack 클래스

public class IntStack {
	private int max;
	private int ptr;
	private int []stk;
	
	public IntStack(int capacity) //생성자
	{
		max = capacity;
		ptr = 0;
		stk = new int[max];
	}
	
	private boolean isFull() {return ptr >= max;} //스택이 용량이 남아있는지 리턴
	
	private boolean isEmpty() {return ptr <= 0;} //스택 비어있는지 리턴
	
	public void push(int value)
	{
		if(!isFull()) stk[ptr++] = value;
		else System.out.println("스택의 남은 용량이 없습니다.");
		
	}
	
	public void pop()
	{
		if(!isEmpty()) --ptr;
		else System.out.println("이미 스택이 비어있습니다.");
	}
	
	public void peek() //스택의 꼭대기 값을 출력
	{
		if(!isEmpty()) System.out.println(stk[ptr-1]);
		else System.out.println("스택이 비어있습니다.");
	}
	
	public void indexOf(int value) //스택에서 원하는 값을 검색
	{
		for(int i = ptr -1; i >= 0; --i) 
			{
				if(stk[i] == value)
				{
					System.out.println("찾는 값이 있습니다. 인덱스 : " + i);
					return;
				}
			}
		System.out.println("찾는 값이 없습니다.");
	}
	
	public void clear() {ptr = 0;} //ptr을 0으로 바꿔줌으로서 스택에 쌓인 데이터가 0으로 인식
	
	public int capacity() {return max;} //스택의 최대용량 리턴
	
	public int size() {return ptr;} //데이터 수를 확인 하는 메소드
	
	public void dump() //스택 안에 있는 모든 데이터를 표시하는 메소드
	{
		if(isEmpty())
		{
			System.out.println("스택이 비어있습니다.");
			return;
		}
		
		for (int i = 0; i < ptr; ++i)
		{
			System.out.println("[" + i + "]" + "=" + stk[i]);
		}
	}
	
}

 

실행 예제

import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("스택 용량 입력 : ");
		int command = sc.nextInt();
		IntStack stk = new IntStack(command);
		while(true)
		{
			System.out.println("현재 데이터 수 : " + stk.size() + "/" + stk.capacity());
			System.out.println("(1) push (2)pop (3)search (4)peek (5)dump (6)exit");
			System.out.print("cmd : ");
			command = sc.nextInt();
			if(command == 1)
			{
				System.out.print("value : ");
				command = sc.nextInt();
				stk.push(command);
			}
			else if(command == 2) stk.pop();
			else if(command == 3)
			{
				System.out.print("Data for Search: ");
				command = sc.nextInt();
				stk.indexOf(command);
			}
			else if(command == 4) stk.peek();
			else if(command == 5) stk.dump();
			else if(command == 6) System.exit(0);
			else continue;
		}
	}
}

 

 

 

 

양쪽 스택

배열을 공유하여 2개의 스택을 구현하는 int형 스택 클래스를 작성

(스택에 저장하는 데이터는 int형 값으로 아래 그림처럼 배열의 처음과 끝을 사용)

 

IntStackX 클래스

public class IntStackX{
	private int max;
	private int Aptr;
	private int Bptr;
	private int []stk;
	
	public enum AB{A, B}; //열거 타입
	
	public IntStackX(int capacity) //생성자
	{
		max = capacity;
		stk = new int[max];
		Aptr = 0;
		Bptr = stk.length -1;
	}
	
	private boolean isFull() {return Aptr >= Bptr +1;}
		
	
	private boolean isEmpty(AB ab) {
		switch (ab)
		{
		case A:
			return Aptr <= 0;
		case B:
			return Bptr >= max-1;
		}
		return true;
	}
	
	public void push(int value, AB ab)
	{
		if(!isFull())
		{
			switch(ab)
			{
			case A:
				stk[Aptr++] = value;
				break;
			case B:
				stk[Bptr--] = value;
				break;
			}
		}
		else
		{
			System.out.println("스택이 모두 사용중입니다.");
			return;
		}
	}
	
	public void pop(AB ab)
	{
		if(!isEmpty(ab))
		{
			switch(ab)
			{
			case A:
				stk[--Aptr] = 0;
				return;
			case B:
				stk[++Bptr] = 0;
				return;
			}
		}
		else
		{
			System.out.println("스택이 이미 비어있습니다.");
			return;
		}
	}
	
	public void peek(AB ab) //스택의 꼭대기 값을 출력
	{
		if(!isEmpty(ab))
		{
			switch(ab)
			{
			case A:
				System.out.println("Top Data : " + stk[Aptr -1]);
				return;
			case B:
				System.out.println("Top Data : " + stk[Bptr +1]);
				return;
			}
		}
		else
		{
			System.out.println("스택이 이미 비어있습니다.");
			return;
		}
	}
	
	public void indexOf(int value, AB ab) //스택에서 원하는 값을 검색
	{
		switch(ab)
		{
		case A:
			for(int i = Aptr -1; i >= 0; --i)
			{
				if(stk[i] == value) System.out.println("찾는 값이 있습니다. 인덱스 : " + i);
			}
			return;
		case B:
			for(int i = Bptr +1; i < max; ++i)
			{
				if(stk[i] == value) System.out.println("찾는 값이 있습니다. 인덱스 : " + i);
			}
			return;
		}
		System.out.println("찾는 값이 없습니다.");
	}
	
	public void clear(AB ab)
	{
		switch(ab)
		{
		case A:
			Aptr = 0;
			System.out.println("A스택이 초기화 되었습니다.");
			break;
		case B:
			Bptr = max -1;
			System.out.println("B스택이 초기화 되었습니다.");
			break;
		}
	}
	
	public int capacity() {return max;} //스택의 최대용량 리턴
	
	public int size(AB ab)
	{
		switch(ab)
		{
		case A: return Aptr;
		case B: return max - Bptr -1;
		}
	return 0;
	}
	
	public void dump(AB ab) //스택 안에 있는 모든 데이터를 표시하는 메소드
	{
		if(isEmpty(ab))
		{
			System.out.println("스택이 비어있습니다.");
			return;
		}
		else
		{
			switch(ab)
			{
			case A:
				for (int i = 0; i < Aptr; ++i) System.out.println("[" + i + "]" + "=" + stk[i]);
				return;
			case B:
				for (int i = max -1; i > Bptr; --i) System.out.println("[" + i + "]" + "=" + stk[i]);
				return;
			}
		}
	}
	
}

 

실행 예제

import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("스택 용량 입력 : ");
		int command = sc.nextInt();
		IntStackX stk = new IntStackX(command);
		IntStackX.AB AB = IntStackX.AB.A;
		while(true)
		{
			if(AB == IntStackX.AB.A) {System.out.println("Stack A, 현재 데이터 수 : " + stk.size(AB) + "/" + (stk.capacity() - stk.size(IntStackX.AB.B)));}
			else {System.out.println("Stack B, 현재 데이터 수 : " + stk.size(AB) + "/" + (stk.capacity() - stk.size(IntStackX.AB.A)));}
			System.out.println("(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)exit");
			System.out.print("cmd : ");
			command = sc.nextInt();
			if(command == 0) AB = IntStackX.AB.B;
			else if(command == 1)
			{
				System.out.print("value : ");
				command = sc.nextInt();
				stk.push(command, AB);
			}
			else if(command == 2) stk.pop(AB);
			else if(command == 3)
			{
				System.out.print("Data for Search: ");
				command = sc.nextInt();
				stk.indexOf(command,AB);
			}
			else if(command == 4) stk.peek(AB);
			else if(command == 5) stk.dump(AB);
			else if(command == 6) stk.clear(AB);
			else if(command == 7) System.exit(0);
			else continue;
		}
	}
}
/*
 스택 용량 입력 : 10
Stack A, 현재 데이터 수 : 0/10
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 1
Stack A, 현재 데이터 수 : 1/10
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 2
Stack A, 현재 데이터 수 : 2/10
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 3
Stack A, 현재 데이터 수 : 3/10
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 4
Stack A, 현재 데이터 수 : 4/10
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 5
Stack A, 현재 데이터 수 : 5/10
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 0
Stack B, 현재 데이터 수 : 0/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 1
Stack B, 현재 데이터 수 : 1/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 2
Stack B, 현재 데이터 수 : 2/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 3
Stack B, 현재 데이터 수 : 3/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 4
Stack B, 현재 데이터 수 : 4/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 5
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 5
[9]=1
[8]=2
[7]=3
[6]=4
[5]=5
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 6
스택이 모두 사용중입니다.
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 0
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 6
스택이 모두 사용중입니다.
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 5
[9]=1
[8]=2
[7]=3
[6]=4
[5]=5
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 3
Data for Search: 5
찾는 값이 있습니다. 인덱스 : 5
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 2
Stack B, 현재 데이터 수 : 4/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 2
Stack B, 현재 데이터 수 : 3/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 5
[9]=1
[8]=2
[7]=3
Stack B, 현재 데이터 수 : 3/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 
 */