[Java, C++] 스택(Stack)

 

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다.

 

 

 

 

 

 

 

스택(Stack)

• 한쪽 끝에서만 항목 삽입 / 삭제하는 자료구조
• 새 항목을 저장하는 연산 : push
• Top 항목을 삭제하는 연산 : pop
• 후입 선출(Last-In First-Out, LIFO)

 

 

 

• 배열로 구현한 스택

• 마지막 index를 top에 가지고 있다.
• A[++top;] = "망고"
• A[top++;] = "망고"는 틀린 문법! 주의할 것

 

• 단순 연결 리스트로 구현한 스택

정의된 스택대로 사용하는게 제일 효율적이다.

 

 

 

배열로 구현한 ArrayStack class

import java.util.EmptyStackException;
public class ArrayStack<E> {
    private E s[];		// 스택을 위한 배열
    private int top;	// 스택의 top 항목의 배열 원소 인덱스
    public ArrayStack() {	// 스택 생성자
        s = (E[]) new Objact[1];	// 초기에 크기가 1인 배열 생성
        top = -1;
    }
    public int size() { return top+1; }		// 스택에 있는 항목의 수 반환
    public boolean isEmpty { return ( top == -1);}		// 스택이 empty이면 true 반환
    // peek(), push(), pop(), resize() 메서드 선언
}

 

• EmptyStackException : java.util 라이브러리에 선언된 클래스를 이용하여 underflow 발생 시 프로그램 종료

 

 

 

 

Method

 

 

peek()

스택의 top에 있는 항목 반환한다.

public E peek() {		// 스택 top 항목의 내용만을 반환
    if (isEmpty()) throw new EmptyStackException;	// underflow 시 프로그램 정지
    return s[top];
}

 

 

underflow 발생 시 프로그램 종료

 

 

 

push()

 

새 항목을 스택에 삽입한다.

public void push(E newItem) {	// push 연산
	if (size() == s.length)
		resize(2*s.length);		// 스택을 2배의 크기로 확장
	s[++top] = newItem;		// 새 항목을 push
}

 

overflow가 발생하면, resize() 호출하여 배열을 2배로 확장한다.

 

 

 

 

pop()

스택의 top 항목을 삭제한다.

public E pop() {	// pop 연산
        if (isEmpty()) throw new EmptyStackException();		// underflow 발생 시 프로그램 정지
        E item = s[top]
        s[top--] = null;		// null로 초기화
        if (size() > 0 && size()(==s.length/4)
        	resize(s.length/2);		// 스택을 1/2 크기로 축소
	return item;
}

 

 

 

 

 

main class

 

public class main {
	public static void main(String[] args) {
		ArrayStack<String> stack = new ArrayStack<String>();

        stack.push("apple");
        stack.push("orange");
        stack.push("cherry");
        System.out.println(stack.peek());
        stack.push("peer");
        stack.print();
        stack.pop();
        System.out.println(stack.peek());
        stack.push("grape");
        stack.print();
	}
}

 

• 일련의 push와 pop 연산을 수행하고 두 차례 peek 연산 수행

 

 

출력 결과

 

 

 

 

스택의 항목을 위한 Node class

public class Node <e> {
    private E iotem;
    private Node<E> next;
    public Node(E newItem, Node<E> node){	// 생성자
        item = newItem;
        next = node;
	}
    // getter & setter method
    public E getItem() { return item; }
    public Node<E> getNext() { return next; }
    public void setItem(E newItem) { item = newItem; }
    public void setNext(Node<E> newNext) { next = newNext; }
}

 

 

 

ListStack Class

import java.util.EmptyStackException;
public class ListStack <E> {
    private Node<E> top;	// 스택 top 항목을 가진 Node를 가리키기 위해
    private int size;	// 스택의 항목 수
    public ListStack() {	// 스택 생성자
        top = null;
        size = 0;
    }
    public int size() { return size; }	// 스택의 항목의 수를 반환
    public boolean isEmpty() { return size == 0; }	// 스택이 empty이면 true 반환
    // peek(), push(), pop() 메소드 선언
}

 

 

peek()

• 스택의 top 항목만 반환한다.

public E peek() {	// 스택 top 항목만을 반환
	if (isEmpty()) throw new EmptyStackException();		// underflow 시 프로그램 정지
	return top.getItem();
}

 

 

push()

• 스택에 새 항목을 삽입한다.

public void push(E newItem){	// 스택 push 연산
	Node newNode = new Node(newItem, top);	// 리스트 앞부분에 삽입
	top = newNode;		// top이 새 노드 가리킴
	size++;		// 스택 항목 수 1 증가
}

 

 

 

pop()

• top이 가리키는 노드의 item을 반환한다.

public E epop()	// 스택 pop 연산
    if (isEmpty()) throw new EmptyStackException();	// underflow 시 프로그램 정지
    E topItem = top.getPItem();		// 스택 top 항목을 topItem에 저장
    top = top.getNext();	// top이 top 바로 아래 항목을 가리킴
    size--;		// 스택 항목 수를 1 감소
    return topItem;
}

 

 

출력 결과

• 2번 째 라인 pear, 4번 째 라인 grape가 top이 된다.

 

 

스택의 응용

• 컴파일러의 괄호 짝 맞추기
• 회문(Palindrome) 검사
• 후위 표기(Postfix Notation) 수식 계산
• 중위 표기(Infix Notation) 수식의 후위 표기 변환

 

 

 

컴파일러의 괄호 짝 맞추기

 

<<핵심 아이디어>>
왼쪽 괄호는 스택에 push, 오른쪽 괄호를 읽으면 pop 수행

 

 

• pop된 왼쪽 괄호와 바로 읽은 오른쪽 괄호가 다른 종류이면 에러 처리, 같은 종류이면 다음 괄호를 읽음
• 모든 괄호를 읽은 뒤 에러가 없고 스택이 empty이면 정상
• 모든 괄호를 처리한 후, 스택이 empty가 아니면 짝이 맞지 않는 괄호가 스택에 남은 것이므로 에러 처리

 

괄호 짝 맞추기

 

 

 

 

 

 

 

회문 검사

 

<<핵심 아이디어>>
전반부의 문자들을 스택에 push한 후, 후반부의 각 문자를 차례로 pop한 문자와 비교

 

 

• 회문(Palindrome) : 앞으로부터 읽으나 뒤로부터 읽으나 동일한 스트링
• 입력의 앞부분 1/2을 읽어 스택에 push한 후, 문자열의 길이가 짝수이면 뒷부분의 문자 1개를 읽어서 pop한 문자와 비교하는 과정 반복
• 마지막 비교까지 두 문자가 동일하고 스택이 empty이면 입력은 회문
• 입력의 길이가 홀수인 경우 문자는 읽고 버린다.

 

 

 

 

 

스택의 응용 2

• 미로 찾기
• 트리의 순회
• 그래프의 깊이 우선 탐색
• 프로그래밍에서 매우 중요한 함수(메서드) 호출 및 순환 호출도 스택

 

수행 시간

• 배열 스택이 push와 pop 연산 : O(1)
• 배열 크기를 확대 / 축소시키는 경우에 스택의 모든 item들을 새 배열로 복사해야 하므로 O(n)
• 상각 분석 : 각 연산의 평균 수행 시간은 O(1) 시간
• 단순 연결 리스트 스택의 push와 pop 연산 O(1) 시간
• 배열과 단순 연결 리스트로 구현된 스택의 장단점은 리스트를 배열고 단순 연결 리스트로 구현하였을 때의 장단점과 같다.