[자료구조] 스택

[자료구조 알고리즘] Stack 구현하기 in Java - YouTube

 

[ 스택의 활용 예 : 출처 자바의 정석 ] 수식 계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로

 

★ 문제 : 10828번: 스택 (acmicpc.net)

10828번: 스택

★ 스택 단계 (acmicpc.net)

스택 단계

 

■ 스택을 생성해보는 예제 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class _00_스택 {
	public static void main(String[] args) throws Exception{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer token;
		
		//스택 인스턴스 생성
		Stack stack = new Stack();
		
		//첫번째줄 입력값(명령의 수) 
		int N = Integer.parseInt(reader.readLine()); 
		
		//명령 문자열 한 줄
		String input;
		//명령어
		String order;
		
		while (N > 0) {
			input = reader.readLine();
			token = new StringTokenizer(input);
			order = token.nextToken();
			
			//명령어에 따라 스택 메소드 실행
			if (order.equals("push")) {
				int item = Integer.parseInt(token.nextToken());
				stack.push(item);
			} else if (order.equals("pop")) {
				stack.pop();
			} else if (order.equals("size")) {
				stack.size();
			} else if (order.equals("empty")) {
				stack.empty();
			} else if (order.equals("top")) {
				stack.top();
			}
			
			N--;
		}
	}
}

class Stack {
	//노드 내부 클래스 정의
	class Node {
		private int data;
		private Node next;
	}
	
	//가장 위에 있는 노드
	private Node top;
	
	//push메소드 : 노드 삽입
	public void push(int item) {
		Node t = new Node();
		t.data = item;
		t.next = top;
		top = t;
	
	//pop메소드 : 노드 빼기 (뺄 때, 데이터값 읽기)
	public void pop() {
	    if (top == null) {
	    	System.out.println("-1");
	    }else {
	    	Node tmp = top;
	    	top = top.next;
	    	System.out.println(tmp.data);
	    }
	}//pop()
	
	//size메소드 : 노드의 갯수 반환
	public void size() {
		int count = 1;
		Node tmp = top;
		
		if (top == null) {
			System.out.println(0);
		} else {
			while(tmp.next != null) {
				tmp = tmp.next;
				count++;
			}
			System.out.println(count);
		}
	}//size()
	
	//empty메소드(isEmpty) : 노드가 있는지 여부 확인
	public void empty() {
		if (top == null) {
			System.out.println(1);
		} else {
			System.out.println(0);
		}
	}//empty()
	
	//top메소드(peek) : top노드 데이터 읽기
	public void top() {
		if (top == null) {
			System.out.println("-1");
		} else {
			System.out.println(top.data);
		}
	}//top()
	
}