[자료구조] 스택, 연결리스트로 구현, 스택활용(괄호검사)

스택

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 선형구조의 자료 구조이다.

스택 기본 연산

스택(Stack)는 LIFO(Last In First Out) 를 따른다. 즉, 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다.

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

스택 기본 연산 구현(java) : 연결리스트로 구현

// 연결리스트로 Node 클래스 구현
public class Node {
	String data; // data 필드
	Node link; // link 필드

	public Node(String data, Node link) { // 생성자
		super();
		this.data = data;
		this.link = link;
	}

	public Node(String data) { // 생성자 오버로딩
		super();
		this.data = data;
	}

	@Override
	public String toString() {
		return "data";
	}

}
// 스택 클래스 구현
public class Stack {

	private Node top;

	public void push(String data) {
		// 첫번째 노드(top)으로 삽입
		top = new Node(data, top);

	}
	public String pop() {
		if(isEmpty()) return null;
		// 첫번째 노드(top) 삭제
		Node popNode = top;
		top = popNode.link;
		popNode.link = null;

		return popNode.data;
	}

    public String peek() {
		if(isEmpty()) return null;
        // top node의 데이터만 반환
		return top.data;
	}

	public boolean isEmpty() {
		return top == null;
	}
}

스택활용 - 괄호검사

괄호 검사 조건

• 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.
• 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.
• 괄호 사이에는 포함 관계만 존재해야 한다.

스택활용 - 괄호검사 실행코드(java)

SWEA 1218번 문제

import java.util.Scanner;
import java.util.Stack;

public class Solution {
	static int n;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		for(int test_case = 1; test_case <= 10; test_case++) {
			n = sc.nextInt();
			String[] line = new String[n];

			line = sc.next().split("");

			System.out.println("#"+test_case+" "+test(line));
		}	
	}

	public static int test(String[] line) {
		Stack<String> stack = new Stack<String>();

		for(int i=0; i<n; i++) {

			if(line[i].equals("(") || line[i].equals("[") || line[i].equals("{") || line[i].equals("<")) {
				stack.add(line[i]);
			}

			if(line[i].equals(")") || line[i].equals("]") ||line[i].equals("}") || line[i].equals(">")) {
				if(stack.empty()) {
					return 0;
				}

				if(line[i].equals(")")) {
					if(!stack.pop().equals("(")){
						return 0;
					}
				}
				if(line[i].equals("]")) {

					if(!stack.pop().equals("[")){
						return 0;
					}
				}
				if(line[i].equals("}")) {

					if(!stack.pop().equals("{")){
						return 0;
					}
				}
				if(line[i].equals(">")) {

					if(!stack.pop().equals("<")){
						return 0;
					}
				}
			}
		}
		return 1;
	}
}