순차적 자료구조 - STACK

1. STACK이란?

• 리스트와 다르게 제한된 접근만 허용. 즉, 삽입, 삭제만 허용하는 선형(linear)자료구조
• LIFO(LAST IN FIRST OUT)의 원칙을 따른다

출처: 위키백과

---

 

2. STACK의 연산

• 삽입: push()
• 삭제: pop() - 가장 위에 있는 항목을 삭제
• peak() - 가장 위에 있는 항목을 리턴, 항목을 삭제하는 pop과는 다름
• isEmpty() - 스택이 비어 있다면, True를 반환

stack class생성

---

java로 구현

 

Node

public class Node {
	//데이터 필드 
	public String data;
	//링크 필드
	//참조변수에 저장되는 객체 타입으로 타입을 선언
	public Node link;
	
	public Node(String data) {
		super();
		this.data = data;
	}
	
	public Node(String data, Node link) {
		//super();
		//this.data = data;
		this(data);
		this.link = link;
	}
	@Override
	public String toString() {
		return "Node [data=" + data + ", link=" + link + "]";
	}
}

 

Stack

 

public class Stack {
	
	private Node top;
	
	public void push(String data) {
		Node newNode = new Node(data, top);
		top = newNode;
	}
	
	public boolean isEmpty() {
		return top == null;
	}
	
	public String pop() {
		if(isEmpty()) {
			System.out.println("스택이 비어있어 pop이 불가능~");
			return null;
		}
		Node popNode = top;
		//top자리를 물려준다 
		top = popNode.link;
		popNode.link = null;
		return popNode.data;
	}
	
	//pop에서 삭제만 할 필요 없당~
	public String peek() {
		if(isEmpty()) {
			System.out.println("스택이 비어있어yo");
			return null;
		}
		Node peekNode = top;
		return peekNode.data;
	}
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("S ( ");
		for(Node currNode = top; currNode!=null; currNode = currNode.link) {
			sb.append(currNode.data).append(",");
		}
		if(!isEmpty())sb.setLength(sb.length()-1);
		
		sb.append(" ) ");
		return sb.toString();
	}
	
	
}

---

3. STACK의 활용 - 괄호 맞추기

-(2+5)*7-((3-1)/2+7) 과 같은 식의 괄호 맞추기

- 왼쪽과 오른쪽이 개수와 쌍이 모두 맞아야 한다. 

- 문제: - 입력: 왼, 오 괄호의 문자영

          - 출력: 괄호쌍이 맞으면 True, 아니면 False

- 관찰:  ------------(-------------)----------------