[データ構造](Data Structure)スタック、接続リスト、およびスタックの使用(かっこチェック)

スタック
これは,一端からしか資料を入れて取り出すことができないLIFO(Last In First Out)形式の線形構造の資料構造である.
スタック基本演算
スタックはLIFOに従う.つまり、最近スタックに追加されたアイテムは、最初に削除されたアイテムです.
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;
	}
}