2. 스택(stack)

스택이란?

스택은 가장 간단한 자료구조 중 하나로 주방에 쌓여있는 접시를 상상하면 쉽게 이해할 수 있다.

 

접시를 닦는 사람은 방금 닦은 접시를 항상 접시더미의 맨 위에 올려놓는다

 

접시를 쓰는 사람은 항상 맨 위의 접시를 꺼내 쓴다.

 

이러한 입출력 형태를 후입선출(LIFO : Last-In-First_Out) 이라고 한다.

 

스택의 연산들

• push(x) : 주어진 요소 x를 스택의 맨 위에 추가한다.
• pop() : 스택이 비어있지 않으면 맨 위에 있는 요소를 삭제하고 반환한다.
• isEmpty() : 스택이 비어있으면 true를 아니면 false를 반환한다.
• peek() : 스택이 비어있지 않으면 맨 위에 있는 요소를 삭제하지 않고 반환한다.
• isFull() : 스택이 가득 차 있으면 true를 아니면 false를 반환한다.
• size() : 스택 내의 모든 요소들의 개수를 반환한다.
• display() : 스택 내의 모든 요소들을 출력한다.

 

스택의 활용 예

스택은 특히 자료의 출력순사가 입력순서의 역순으로 이루어져야 할 경우에 매우 요긴하게 사용된다.

• 문서나 그림, 수식 등의 editor에서 되돌리기(undo) 기능을 구현할 때 스택이 사용된다.
• 함수 호출에서 복귀 주소를 기억하는데 스택을 사용한다.
• 소스코드나 문서에서 괄호 닫기가 정상적으로 되었는지 검사하는 프로그램에서도 스택을 사용한다.
• 계산기 프로그램에서 입력된 수식을 계산하는 과정
• 미로에서 출구 찾기

 

일반 Array 를 이용한 stack 구현

package com.stack.array;

public class Stack_Array {

	private static int MAX_STACK_SIZE = 10;

	private int top; // stack 의 top 위치 처음에는 -1로 초기화
	private int[] data = new int[MAX_STACK_SIZE];

	public Stack_Array() {
		top = -1;
	}

	public Stack_Array(int mAX_STACK_SIZE) {
		super();
		MAX_STACK_SIZE = mAX_STACK_SIZE;
		top = -1;
	}

	public boolean isEmpty() {
		return top == -1;
	}

	public boolean isFull() {
		return top == MAX_STACK_SIZE - 1;
	}

	// 맨 위에 항목 삽입
	public void push(int element) {
		if (isFull()) {
			System.out.println("stack 이 가득 차있습니다.");
		} else {

			++top;
			data[top] = element;
		}
	}

	// 맨 위의 요소를 삭제하고 반환
	public int pop() {
		int element;

		if (isEmpty()) {
			System.out.println("stack 이 이미 비어있습니다.");
			return -1; // error return -1
		} else {
			element = data[top];
			--top;
			return element;
		}
	}

	// 삭제하지 않고 반환
	public int peek() {
		if (isEmpty()) {
			System.out.println("stack이 이미 비어있습니다.");
			return -1;
		} else {
			return data[top];
		}
	}

	// 스택 내용을 화면에 출력
	public void display() {
		if (isEmpty()) {
			System.out.println("stack이 이미 비어있습니다.");
		} else {
			System.out.println("[stack의 항목 수 = " + (top + 1) + "] ==> ");

			for (int i = top; i >= 0; i--) {
				System.out.println(data[i]);
			}
		}
	}
}

 

기본 배열을 이용해 stack 자료구조를 구현해 보았습니다. 

 

main() 에서 간단하게 이 Stack_Array 클래스를 이용해 보겠습니다.

package com.stack.array;

public class MTest {

	public static void main(String[] args) {
		// 생성자에서 stack의 크기를 10으로 초기화!
		Stack_Array st = new Stack_Array(10);

		for (int i = 1; i < 8; i++) {
			st.push(i);
		}
		
		System.out.println("stack 에 값을 push 한 후 : \n");
		st.display();
		
		// top 의 요소를 반환하고 삭제하지 않음
		System.out.println("top = " + st.peek());
		
		// top 의 요소를 반환하고 삭제
		System.out.println("top = " + st.pop());
		System.out.println("top = " + st.pop());
		System.out.println("top = " + st.pop());
		
		System.out.println("\nstack 에서 값을 삭제한 후 \n" );
		st.display();
		
		
	}
}

 

 

Array Stack을 이용한 괄호 검사

위의 Array_Stack 클래스에서 int type 만 char type 으로 바꾸어 수정하였습니다. 후에는 JAVA의 Generic을 이용해 일반 배열을 사용한 stack을 구현해 보겠습니다.

package com.checkMatching;

public class StackCheckMatching {

	private static int MAX_STACK_SIZE = 10;

	private int top; // stack 의 top 위치 처음에는 -1로 초기화
	private char[] data = new char[MAX_STACK_SIZE];

	public StackCheckMatching() {
		top = -1;
	}

	public StackCheckMatching(int mAX_STACK_SIZE) {
		super();
		MAX_STACK_SIZE = mAX_STACK_SIZE;
		top = -1;
	}

	public boolean isEmpty() {
		return top == -1;
	}

	public boolean isFull() {
		return top == MAX_STACK_SIZE - 1;
	}

	// 맨 위에 항목 삽입
	public void push(char element) {
		if (isFull()) {
			System.out.println("stack 이 가득 차있습니다.");
		} else {

			++top;
			data[top] = element;
		}
	}

	// 맨 위의 요소를 삭제하고 반환
	public char pop() {
		char element;

		if (isEmpty()) {
			System.out.println("stack 이 이미 비어있습니다.");
			return ' '; // error return -1
		} else {
			element = data[top];
			--top;
			return element;
		}
	}

	// 삭제하지 않고 반환
	public char peek() {
		if (isEmpty()) {
			System.out.println("stack이 이미 비어있습니다.");
			return ' ';
		} else {
			return data[top];
		}
	}

	// 스택 내용을 화면에 출력
	public void display() {
		if (isEmpty()) {
			System.out.println("stack이 이미 비어있습니다.");
		} else {
			System.out.println("[stack의 항목 수 = " + (top + 1) + "] ==> ");

			for (int i = top; i >= 0; i--) {
				System.out.println(data[i]);
			}
		}
	}
}

package com.checkMatching;

import java.util.Scanner;

public class MTest {

	private static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		StackCheckMatching scm = new StackCheckMatching(10);

		System.out.println("괄호 검사 할 문자열 입력 : ");
		String str = sc.nextLine();

		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) == '(' || str.charAt(i) == '{' || str.charAt(i) == '[' || str.charAt(i) == '<') {
				scm.push(str.charAt(i));
			} else if (str.charAt(i) == ')' || str.charAt(i) == '}' || str.charAt(i) == ']' || str.charAt(i) == '>') {
				if (scm.isEmpty()) {
					System.out.println("오류!!");
					scm.display();
					return;
				} else {
					char now = scm.pop();

					if ((str.charAt(i) == ')' && now != '(') || (str.charAt(i) == '}' && now != '{')
							|| (str.charAt(i) == ']' && now != '[') || (str.charAt(i) == '>' && now != '<')) {
						break;
					}
				}
			}
		}

		if (scm.isEmpty()) {
			System.out.println("오류 없는 괄호 매칭 입니다!");
		} else {
			System.out.println("오류!!!!");
			scm.display();
		}
	}
}

 

문자열은 아무 코드나 복사해서 붙여넣었습니다. 잘돌아가네요 ㅎㅎ,,,