[ENG][자료구조]Stack 이론과 예제

Overview

한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조
즉, 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다.

  - pop(): 스택에서 가장 위에 있는 항목을 제거한다.
  - push(item): item 하나를 스택의 가장 윗부분에 추가한다.
  - peek(): 스택의 가장 위에 있는 항목을 반환한다.
  - isEmpty(): 스택이 비어 있을 때에 true를 반환한다.

배열과 달리 스택은 i번째 항목에 접근할 수 없다.

 

Usecase

  - 웹 브라우저 방문기록 (뒤로 가기)
  - 실행 취소 (undo)
  - 역순 문자열 만들기
  - 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사, 후위 표기법 계산)

 

Structure

https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

 

Code Example

package com.data.structure;

class MyStack {

	public final int MAX_N = 1000;

	public int top;
	public int stack[] = new int[MAX_N];

	public void stackInit() {
		top = 0;
	}

	public boolean stackIsEmpty() {
		return (top == 0);
	}

	public boolean stackIsFull() {
		return (top == MAX_N);
	}

	public boolean push(int value) {
		if (stackIsFull()) {
			System.out.println("stack overflow!");
			return false;
		}
		stack[top] = value;
		top++;

		return true;
	}

	public Integer pop() {
		if (top == 0) {
			System.out.println("stack is empty!");
			return null;
		}

		top--;
		Integer value = new Integer(stack[top]);

		return value;
	}

	public static void main(String arg[]) throws Exception {
		MyStack myStack = new MyStack();
		
		int N = 10;

		myStack.stackInit();
		
		for (int i = 0; i < N; i++) {
			int value = i;
			myStack.push(value);
		}

		while ( ! myStack.stackIsEmpty()) {
			Integer value = myStack.pop();
			if (value != null) {
				System.out.print(value.intValue() + " ");
			}
		}
	}
}

 

Console Result

9 8 7 6 5 4 3 2 1 0

 

Conclusion

N/A