7장 스택

스택은 접시처럼 시간순서에 따라 자료가 쌓이고, 삭제할 때는 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO, Last In First Out)의 구조를 갖는다. (삽입은 푸시, 삭제는 팝 이라 부른다.)

스택 구현 방법

1. 순차 자료구조방식을 이용한 스택의 구현

2. 연결 자료구조방식을 이요한 스택의 구현

순차 자료구조를 이용한 스택은 배열을 사용하여 구현하기는 쉽지만, 물리적으로 크기가 고정된 배열을 사용하기 때문에 스택의 크기를 변경하기가 어렵고, 메모리의 낭비가 생기는데 이는 연결 자료구조 방식을 이용해 해결가능하다.

프로그램 간의 호출과 복귀에 따른 수행 순서는 가장 나중에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 LIFO 구조가 된다. 이를 응용하여 시스템 스택을 사용한다. 함수나 서브프로그램이 호출되면 스택 프레임을 작성하여 시스템 스택에 삽입하고, 함수의 실행이 끝나면 시스템 스택의 top 원소를 삭제하면서 프레임에 저장되어있던 복귀 주소를 확인하고 복귀한다. 함수 호출과 복귀에 따라 이 과정을 반복하여 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택이 된다.

 

연산자의 위치에 따라 3가지 표기법이 있는데 그걸 먼저 살펴보겠다.

1) 전위 표기법 (Prefix Notation)

연산자를 앞에 표기하고 그 다음에 피연산자를 표기하는 방법

ex) +AB

 

2) 중위 표기법 (Infix Notation)

연산자를 피연산자의 가운데에 표기하는 방법

ex) A+B

 

3) 후위 표기법 (Postfix Notation)

연산자를 피연산자 뒤에 표기하는 방법

ex) AB+

 

중위 표기법 -> 전위 표기법

1) 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.

2) 각 연산자를 그에 대응하는 왼쪽 괄호의 앞으로 이동시킨다.

3) 괄호를 제거한다.

((A*B)-(C/D))    ≫   -(*(AB)/(CD)  ≫   -*AB/CD

 

중위 표기법 -> 후위 표기법

1)수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.

2) 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다.

3) 괄호를 제거한다.

 

((A*B)-(C/D))    ≫    ((AB)*(CD)/)-  ≫  AB*CD/-

 

스택을 이용해 수식의 후위 표기법으로 변환하는 방법

사람이 일반적으로 사용하는 표기법은 중위 표기법이나, 컴퓨터 내부에서 수식을 처리하는데 가장 효율적인 방법은 후위 표기법이다.

ex) ( ( A * B ) - ( C / D ) ) 을 후위 표기법으로 변환

 

1) 왼쪽 괄호를 만나면 무시하고 다음 문자를 읽는다.

2) 피연산자를 만나면 출력한다.

3) 연산자를 만나면 스택에 삽입한다.

4) 오른쪽 괄호를 만나면 스택을 팝하여 출력한다.

5) 수식이 끝나면 스택이 공백이 될 때까지 팝하여 출력한다.

최종 출력상태  》  AB*CD/-

 

package stack;

public class Stack {
	private int top;
	private int maxSize;
	private Object[] stackArray;
	//스택 생성, 스택의 최대 크기로 생성
	public Stack(int maxSize) {
		this.maxSize = maxSize;
		this.stackArray = new Object[maxSize];
		this.top = -1; // top은 -1로 초기화
	}
	
	//스택이 비었는지 체크
	public boolean empty() {
		return (top == -1);
	}
	//스택이 꽉찼는지 체크
	public boolean full() {
		return (top == maxSize-1);
	}
	//스택에 item 입력
	public boolean push(Object item) {
		if(full()) {
			System.out.println("꽉 찼습니다.");
			return false;
		}
		stackArray[++top] = item;
		return true;
	}
	//스택의 가장 위의 데이터 제거
	public Object pop() {
		if(empty()) {
			System.out.println("비었습니다.");
			return false;
		} else {
			Object item = stackArray[top];
			stackArray[top] = null;
			top--;
			return item;
		}
	}
	//스택 출력
	public void printStack(Stack stack) {
		if(top != -1) {
			for(int i=top; i<=top; i--) {
				if(i == -1) {
					break;
				}
					System.out.println(" | " + stackArray[i] + " | ");
					System.out.println("----------");
			}
		} else {
			System.out.println("비어있음");
		}		
	}	
}

package stack;

import java.util.Scanner;

public class Main {

	public static void menu() {
		System.out.println("1. push");
		System.out.println("2. pop");
		System.out.println("3. stack");
		System.out.println("Q. 종료");
		
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		Stack stack = new Stack(T);
		boolean flag = true;
		
		while (flag) {
			menu();
			String s = sc.next();
			
			switch (s) {
				case "1":
					System.out.print("Push : ");
					String data = sc.next();
					stack.push(data);
					break;
				case "2":
					System.out.print("Pop : " + stack.pop());
					break;
				case "3":
					stack.printStack(stack);
					break;
				case "Q":
				case "q":
					flag = false; break;
			}
		}
	}
}