[자료구조] 스택

스택이란?

스택(Stack)은 컴퓨터에서 굉장히 많이 사용되는 자료구조이다. 식당에 쌓여있는 접시 더미, 책상에 쌓여있는 책 등이 스택의 전형적인 예이다.

 

책상에 쌓여있는 책들을 이용하여 스택을 설명해보자. 책상에 새로운 책을 쌓을 때는, 책 더미의 맨 윗부분에 놓는다. 

책이 필요하게 되면, 맨 위에 있는 책을 꺼낸다. 중간이나 맨 밑의 책부터 뽑아 사용한다면, 책 더미는 무너져버릴 것이다. 그렇기 때문에, 가장 최근에 들어온 책이 제일 위에 있고, 먼저 나간다. 이러한 입출력 형태를 LIFO(Last In First Out, 후입 선출)라고 한다.

 

스택에서의 입출력은 맨 위에서만 일어나고, 스택의 중간에서는 데이터를 삭제할 수 없다.

스택의 입출력이 일어나는 부분을 스택 상단(Stack Top)이라고 하고, 반대쪽인 바닥부분을 스택 하단(Stack Bottom)이라고 한다. 스택에 저장되는 것을 요소(Element)라고 한다. 스택에 요소가 하나도 없는 상태를 공백 스택(Empty Stack)이라고 한다.

 

http://www.incodom.kr/%EC%8A%A4%ED%83%9D

스택은 특히, 자료의 출력 순서가 입력의 역순으로 이루어져야할 때, 매우 요긴하게 사용할 수 있다. 예를 들어, {A,B,C,D,E}의 데이터를 {E,D,C,B,A}처럼 역순으로 하고싶다면, 데이터를 스택에 넣었다가 다시 꺼내면 된다. 또한, 워드나 여러 에디터들에 있는 되돌리기(undo) 기능을 구현할 때, 스택을 사용할 수 있다.

 

---

추상 자료형 스택

스택을 추상 자료형으로 정의해보자. 추상 자료형으로서의 스택은 0개 이상의 요소를 가지는 선형 리스트의 일종으로 정의되며, 스택에 요소를 추가하거나 삭제하는 연산과 현재 스택 상태를 검사하는 연산들로 구성된다.

 

• create(size) :  최대 크기가 size인 공백 스택을 생성한다.\
• is_full(s)
• is_empty(s)
• push(s, item) : 스택의 맨 위에 item을 추가
• pop(s) : 스택의 맨 위의 원소를 제거해서 반환
• peek(s) : 스택의 맨 위의 원소를 삭제하지 않고 반환

스택에는 두가지 기본 연산이 있다.

1 . 삽입 연산 , push 연산

2 . 삭제 연산, pop 연산

 

초기 상태에서, push(A)를 수행하면, 비어있는 스택에 A가 삽입된다. 다음에 push(B)를 수행하면, A위에 B가 쌓인다.

다음에 pop()이 실행되면, 맨위에 있던 B가 삭제된다.

 

push 연산 중, 스택이 가득차서 더이상 입력이 불가능 하거나, pop 연산에서 더이상 꺼낼 요소들이 없는 경우 오류가 발생한다.

---

스택의 구현

스택을 구현하는 방법은 배열을 이용하는 방법과 연결 리스트를 이용하는 방법이 있다.

배열은 구현하는 방법이 간단하고 성능이 우수한 장점이 있지만, 스택의 크기가 고정되는 단점이 있다.

연결리스트를 이용한 방법은 구현이 조금 복잡하지만, 스택의 크기를 필요에 따라 가변적으로 할 수 있다.

 

1. 배열을 이용한 스택 구현

public class Stack {
    int top;
    int[] stack;
    int size;
    
    public Stack(int size) {
    	this.size = size;
        stack = new int[size];
        top = -1; // 가장 최근에 입력된 자료를 가리킴
    }
    
    private void push(int item) {
    	stack[++top] = item;
    }
    
    private int peek() {
    	return stack[top];
    }
    
    private int pop() {
    	return stack[top--];
    }
    
    private int search(int item) {
    	for (int i = 0; i <= top; i++) {
        	if(stack[i] == item) return (top - i) + 1;
         }
        return -1;
     }   
     
     private boolean empty() {
     	return size == 0;
     }
  }   

 

2. 연결리스트를 이용한 스택의 구현

public class Node {
	
	private int data;
	private Node nextNode;
	
	public Node(int data) {
		this.data = data;
		this.nextNode = nextNode;
	}
	
	protected void linkNode(Node node) {
		this.nextNode = node;
	}
	
	protected int getData() {
		return this.data;
	}
	
	protected Node getNextNode() {
		return this.nextNode;
	}
	
}

 public class LinkedListStack {
	Node top;
	
	public LinkedListStack() {
		this.top = null;
	}
	
	private void push(int data) {
		Node node = new Node(data);
		node.linkNode(top);
		top = node;
	}
	
	public int peek() {
		return top.getData();
	}
	
	private void pop() {
		if(empty()) {
			throw new ArrayIndexOutOfBoundsException();
		}
		else {
			top = top.getNextNode(); // top 노드 아래에 있는 노드로 top을 재선언
		}
	}
	
	private int search(int item) {
		Node searchNode = top;
		int index = 1;
		while(true) {
			if(searchNode.getData() == item) {
				return index;
			} else {
				searchNode = searchNode.getNextNode();
				index++;
				if (searchNode == null)
					break;
			}
		}
		return -1;
	}
	 private boolean empty() {
	        return top == null;
	    }
}

 

---

◎ 참고 자료

- C언어로 쉽게 풀어쓴 자료구조. Chapter 4 스택

- velog.io/@lshjh4848/Java-%EC%8A%A4%ED%83%9DStack-%ED%81%B4%EB%9E%98%EC%8A%A4-%EC%A0%95%EB%A6%AC