[JAVA 자료구조] 스택(Stack)

   스택이란?

스택은 물건을 쌓아올리는 자료를 쌓아 올린 형태의 자료구조이다.
가장 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조를 가지고 있다.
스택의 마지막에 삽입한 자료가 가장 먼저 꺼내어지므로 후입선출(LIFO:Last-In First-OUT)이며, 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형구조이다.

※참고※ 선형구조와 비선형구조
- 선형구조: 자료간의 관계가 1대 1의 관계를 가짐
- 비선형구조: 자료간의 관계가 1대 N의 관계를 가짐(ex.트리 자료구조)

 

   스택의 구조

 

- 스택 상단(top): 스택에서 입출력이 이루어지는 부분
- 스택 하단(bottom): 바닥 부분
- 요소(element): 스택에 저장되는 것
- 공백(empty)상태: 요소가 하나도 없는 경우
- 포화(full)상태: 꽉 차서 더 이상 요소를 넣을 수 없는 상태

 

   스택의 연산

- init(): 스택을 초기화한다.
- is_empty(): 스택이 비어있으면 TRUE를 아니면 FALSE를 반환한다.
- is_full(): 스택이 가득 차 있으면 TRUE를 아니면 FALSE를 반환한다.
- size(): 스택 내의 모든 요소들의 개수를 반환한다.
- push(x): 스택 맨 위에 있는 요소를 삭제하고 반환한다.
- pop(): 스택 맨 위에 있는 요소를 삭제하고 반환한다.
- peek(): 스택 맨 위에 있는 요소를 삭제하지 않고 반환한다.

 

   스택의 구현

구현1 배열을 이용한 스택

스택을 가장 간단하게 구현할 수 있는 방법이지만 크기를 변경할 수 없다는 단점이 있다.

import java.util.Scanner;

public class Stack {
	private int top; // 가장 최근에 입력된 항목의 위치를 가리키기 위한 변수
	private int maxSize; // 스택에 저장할 수 있는 최대 요소의 개수
	private Object[] stackArray;// 정수 항목들을 저장할 배열

	// 배열 스택 생성
	public Stack(int maxSize) {
		this.maxSize = maxSize;
		this.top = -1;
		this.stackArray = new Object[maxSize];
	}

	// 스택이 비어있는지 체크
	public boolean isEmpty() {
		return (top == -1); // 값이 -1이면 항목이 하나도 없는 상태
	}

	// 스택이 꽉 찼는지 체크
	public boolean isFull() {
		return (top == maxSize - 1);
	}

	// 스택에 요소 삽입
	public boolean push(Object item) {
		if (isFull()) { // 스택이 포화상태이면
			for(int i=0; i<maxSize; i++) {
				System.out.println("| stack is full |");
				System.out.println("-------");
			}		
			return false;
		}
		stackArray[++top] = item;
		return true;
	}

	// 스택의 가장 위의 데이터 반환
	public Object peek() {
		if (isEmpty()) { //비어있다면
			System.out.println("| stack is empty |");
			return null;
		} else {
			Object item = stackArray[top];
			return item;
		}
	}

	// 스택의 가장 위의 데이터 제거
	public Object pop() {
		Object item = peek();
		top--;
		return item;
	}

	// 스택 출력
	public void printStack(Stack stack) {
		if (top != -1) {// 비어있지 않다면
			for (int i = top; i >= 0; i--) {
				System.out.println("| " + stack.stackArray[i] + " |");
				System.out.println("-------");
			}
		} else {
			System.out.println("| stack is empty |");
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("스택 size 입력: ");
		int size = sc.nextInt();

		Stack arrayStack = new Stack(size);

		boolean flag = true;

		// 스택 실행 메뉴
		while (flag) {
			menu();
			String s = sc.next();

			switch (s) {
			// push()
			case "1":
				System.out.println("push:");
				String data = sc.next();
				arrayStack.push(data);
				break;

			// pop()
			case "2":
				System.out.println("pop: " + arrayStack.pop());
				break;

			// peek()
			case "3":
				System.out.println("가장 위의 데이터는: " + arrayStack.peek());
				break;

			// 스택 데이터 출력
			case "4":
				arrayStack.printStack(arrayStack);
				break;

			case "q":
			case "Q":
				System.out.println("종료");
				flag = false;
				break;
			}
		}
	}

	public static void menu() {
		System.out.println("1. push");
		System.out.println("2. pop");
		System.out.println("4. stack");
		System.out.println("3. peek");
		System.out.println("q. 종료");
	}
}

배열의 인덱스가 0에서 부터 데이터가 채워질것이기 때문에 데이터가 하나도 없는 공백상태일 경우 top=-1이 되도록 하고,
데이터가 채워지면서 top=maxSize-1일 경우 포화상태가 된다.
데이터를 삽입할경우에는 배열이 포화상태가 아닌지 검사 후 top을 하나 증가시킨 후에 넣어주고, 가장 위의 데이터를 꺼낼 때는 배열이 비어있는지 확인 후에 데이터를 꺼낸 후에 top을 하나 감소시킨다.
peek()은 맨 위의 데이터를 반환하기만 할 뿐 현재 위치는 변하지 않는다.

<실행 화면>

1. push()

2. peek()

3. pop()

 

구현2 연결리스트를 이용한 스택

연결리스트는 공부중이므로 추후 업데이트 예정...

 

구현3 자바 Collections 클래스 사용

Java에서는 List 컬렉션 클래스의 Vector클래스를 상속받아 전형적인 스택 메모리 구조의 클래스를 제공하고 있다.
Java의 Stack클래스에서는 push(), push(), peek(), empty() 및 search()메서드를 제공한다.

1) Stack의 선언

import java.util.Stack;

Stack<Integer> stack = new Stack<Integer>

2) Stack의 메소드

public void push(Element data); 해당 스택의 제일 상단에 요소를 삽입함
public Element pop(); //가장 상단에 있는 요소 꺼내고 반환
public Element peek(); //가장 상단의 요소 반환
public boolean empty(); //스택이 비어있는지 판별
public int search(Element data); //data을 보관한 순번 반환(0이 아닌 1번부터 시작)

3) 예제 코드

import java.util.Stack;

public class StackClass {
	public static void main(String[] args) {
		Stack<Integer> stack = new Stack<Integer>(); // 스택의 생성

		// push()
		stack.push(3);
		stack.push(2);
		stack.push(1);
		System.out.println(stack);

		// pop()
		System.out.println(stack.pop());
		System.out.println(stack);

		// peek()
		System.out.println(stack.peek());
		System.out.println(stack);

		// search()
		System.out.println(stack.search(2));
		System.out.println(stack.search(3));
	}
}

※참고※ Stack클래스에 대한 자세한 설명
http://tcpschool.com/java/java_collectionFramework_stackQueue