2. 스택(Stack)

• 먼저 들어간 데이터가 가장 마지막에 나오는 구조(Last In, First Out : LIFO)

• 삽입과 삭제가 한쪽 끝에서만 자료를 넣고 뺄 수 있다.

• 예: 함수 호출 스택, 되돌리기, 괄호 검사, 후위 표기식 계산

불변식은 0 <= size <= capacity와 “다음에 꺼낼 값이 맨 위에 있다”는 것이다. push(10), push(20), pop() 순서라면 반환값은 20이고 스택에는 10이 남는다. 입력 순서를 뒤집어 처리해야 할 때 스택이 적합하다. 먼저 들어온 값을 먼저 처리하는 작업에는 큐가 맞다.

스택(Stack)의 주요 기능

스택의 초기화

아래의 size 방식은 stack[0..size-1]에 값이 있고 stack[size]가 다음 삽입 위치라는 의미다. top 인덱스 방식을 쓰는 뒤의 Java·C 구현에서는 빈 상태를 top=-1로 표현한다. 두 방식의 인덱스를 혼용하면 빈 스택에서 잘못된 칸을 읽는다.

int[] stack = new int[100];
int size = 0;

삽입(Push)

• 스택 위에 새로운 노드를 쌓는 작업

void push(int data) {
    if (size == stack.length) throw new IllegalStateException("스택이 가득 찼습니다");
    stack[size++] = data;
}

삽입 전에 용량을 검사한다. size가 3이면 기존 값은 인덱스 0,1,2에 있고 새 값은 3에 쓴 뒤 size가 4가 된다. 고정 크기 배열의 push는 O(1)이다.

<데이터 80 삽입>

                                                               <데이터 80 삽입>

삭제(Pop)

• 스택에서 최상위 노드를 걷어내는 작업

int pop() {
    if (size == 0) throw new IllegalStateException("스택이 비었습니다");
    return stack[--size];
}

마지막 값은 stack[size-1]이므로 먼저 size를 줄이고 그 인덱스를 읽는다. 원래 코드의 size < 0은 빈 상태인 0을 걸러내지 못했고, stack[size]는 다음 삽입 칸이었다. 빈 스택에서 0을 돌려주면 실제 데이터 0과 실패를 구분할 수도 없다.

<데이터 80 제거>

                                                                    <데이터 80 제거>

Peek

• Top이 가리키는 위치의 데이터를 가져오는 작업

int peek() {
    if (size == 0) throw new IllegalStateException("스택이 비었습니다");
    return stack[size - 1];
}

peek는 값을 꺼내지 않으므로 size가 바뀌지 않는다. push, pop, peek, isEmpty, size 모두 상수 시간이다.

< Top이 가리키는 위치의 데이터 70을 가져온다 >

                                          < Top이 가리키는 위치의 데이터 70을 가져온다 >

empty

• 스택이 비어있는지 비어있지 않은지 알아보는 작업

boolean isEmpty() {
    return size == 0;
}

size

• 스택에 저장되어 있는 자료의 개수를 알아보는 작업

int size() {
    return size;
}

배열로 구현하는 스택

• 고정 크기 배열은 용량을 초과하면 삽입할 수 없다. 배열을 새로 만들어 복사하면 자동 확장이 가능하지만 그 순간에는 O(n)이 든다.

• 구현이 간단하다.

Java version

ArrayStack.java

public class ArrayStack<T> implements Stack<T> {
	private static final int DEFAULT_SIZE = 10;
	private int top;
	private final int capacity;
	private final Object[] stack;

	public ArrayStack() {
		this(DEFAULT_SIZE);
	}
	public ArrayStack(int capacity) {
		if (capacity < 1) throw new IllegalArgumentException("capacity must be positive");
		top = -1;
		this.capacity = capacity;
		stack = new Object[capacity];
	}
	@Override
	public void push(T data) {
		if (isFull()) {
			throw new IllegalStateException("stack overflow");
		}
		stack[++top] = data;
	}
	@Override
	public T pop() {
		if (isEmpty()) {
			throw new IllegalStateException("stack is empty");
		}
		@SuppressWarnings("unchecked") T value = (T) stack[top];
		stack[top--] = null; // 꺼낸 객체 참조를 해제한다
		return value;
	}
	@Override
	public T peek() {
		if (isEmpty()) throw new IllegalStateException("stack is empty");
		@SuppressWarnings("unchecked") T value = (T) stack[top];
		return value;
	}
	@Override
	public boolean isFull() {
		if (top == capacity-1) {
			return true;
		}
		return false;
	}
	@Override
	public boolean isEmpty() {
		if (top == -1) {
			return true;
		}
		return false;
	}

}

이 구현은 top=-1을 빈 상태로 둔다. push에서 ++top한 위치에 값을 넣고, pop에서는 현재 top 값을 읽은 뒤 top-- 한다. capacity와 top을 인스턴스별로 보관해야 스택 두 개를 만들어도 서로의 크기를 건드리지 않는다. 기존 생성자는 전달받은 용량을 무시했고 top과 capacity를 static으로 두어 여러 인스턴스가 상태를 공유했다. pop이 꺼낸 배열 칸을 null로 비우는 이유는 스택에서 제거된 객체를 배열이 계속 참조하지 않게 하기 위해서다. 비어 있을 때 peek도 실패해야 한다.

연산	고정 배열 스택	머리에 삽입하는 연결 스택
push / pop / peek	O(1)	O(1)
공간	미리 잡은 용량만큼	값마다 노드 한 개
용량 초과	예외 또는 배열 확장	메모리가 허용하는 동안 생성

연결 스택에서 삽입·삭제가 상수 시간이 되려면 리스트 머리가 스택의 top이어야 한다. 꼬리에 붙이고 끝에서 제거하려면 단일 연결 리스트에서는 이전 노드를 찾느라 O(n)이 걸린다.

Stack.java

public interface Stack<T> {
	public void push(T data);
	public T pop();
	public T peek();
	public boolean isFull();
	public boolean isEmpty();
}

c language

ArrayList.h

//
// Created by Paik Seung Cheol on 2020. 3. 19..
//

#ifndef ARRAYSTACK_H
#define ARRAYSTACK_H


#include <stdio.h>
#include <stdlib.h>


#define TRUE 1
#define FALSE 0

typedef struct _Node {
    int data;
}Node;

typedef struct _Stack {
    int top;
    int capacity;
    Node* nodes;
}Stack;

void createStack(Stack** stack, int capacity);
int isFull(Stack* stack);
int isEmpty(Stack* stack);
void push(Stack* stack, int data);
int popup(Stack* stack);
int peek(Stack* stack);
#endif //ARRAYSTACK_H

ArrayList.c

//
// Created by Paik Seung Cheol on 2020. 3. 19..
//
#include "ArrayStack.h"

void createStack(Stack** stack, int capacity) {
    (*stack) = (Stack*)malloc(sizeof(Stack));
    (*stack)->capacity = capacity;
    (*stack)->top = -1;
    (*stack)->nodes = (Node*) malloc(sizeof(Node)* capacity);
}

int isFull(Stack* stack) {
    if ((stack)->top == (stack)->capacity-1) {
        return TRUE;
    }
    return FALSE;
}
int isEmpty(Stack* stack) {
    if ((stack)->top == -1) {
        return TRUE;
    }
    return FALSE;
}
void push(Stack* stack, int data) {
    if (isFull(stack)) {
        printf("stack overflow\n");
        exit(1);
    }
    stack->nodes[++stack->top].data = data;
}
int popup(Stack* stack) {
    if (isEmpty(stack)) {
        printf("is empty\n");
        exit(1);
    }
    return stack->nodes[stack->top--].data;
}

int peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("is empty\n");
        exit(1);
    }
    return stack->nodes[stack->top].data;
}

연결리스트로 구현하는 스택

• 스택의 용량을 미리 정하지 않는다. 메모리 부족까지 무한하다는 뜻은 아니다.

push(10) 뒤 push(20)을 하면 연결이 top → 20 → 10 → null이 된다. pop()은 20을 돌려주며 top을 다음 노드 10으로 옮긴다. 다른 노드를 순회하지 않아도 된다. 빈 상태에서 top == null이고 length == 0이어야 한다는 불변식도 유지한다.

//
// Created by Paik Seung Cheol on 2020. 3. 19..
//
public class LinkedListStack<T> implements Stack<T> {

	private Node top;
	private int length;

    public class Node {
        private T data;
		private Node next;

        public Node() {
            this.data = null;
			this.next = null;
        }

        public Node(T data) {
            this.data = data;
			this.next = null;
        }
    }

    public LinkedListStack() {
		top = null;
		length = 0;
    }

    @Override
    public void push(T data) {
        Node newNode = new Node(data);
		newNode.next = top;
		top = newNode;
        length++;
    }

    @Override
    public T pop() {
        if (isEmpty()) {
			throw new IllegalStateException("Stack is empty");
		}
		T value = top.data;
		top = top.next;
		length--;
		return value;
    }

    @Override
    public T peek() {
        if (isEmpty()) {
			throw new IllegalStateException("stack is empty");
        }
        return top.data;
    }

    @Override
    public boolean isFull() {
		// 연결 구조에서는 사전에 정한 용량이 없다.
        return false;
    }

    @Override
    public boolean isEmpty() {
		return length == 0;
    }

    @Override
    public String toString() {
		Node temp = top;
        if (temp == null) {
            return "[ ]";
        } else {
            // StringBuilder 클래스를 이용하여 데이터를 출력
            StringBuilder sb = new StringBuilder("[");
            sb.append(temp.data);
			temp = temp.next;
            while (temp != null) {
                sb.append(", ");
                sb.append(temp.data);
				temp = temp.next;
            }
            sb.append("]");
            return sb.toString();
        }
    }
}

Ex) 후위표기 사칙연산 계산

후위 표기식은 연산자가 두 피연산자 뒤에 오는 표기다. "32-"는 3 - 2이므로 문자열을 왼쪽부터 읽어 숫자를 스택에 쌓다가 -를 만나면 오른쪽 값 2를 먼저, 왼쪽 값 3을 다음에 꺼낸다. 뺄셈·나눗셈은 순서를 바꾸면 답이 달라지므로 원래 코드의 op1=pop(); op2=pop(); op1-op2는 잘못되었다. 아래 코드는 한 자리 숫자만 허용하는 학습용 예제다. 토큰이 여러 자리 수라면 문자열을 토큰으로 분리해야 한다.

//
// Created by Paik Seung Cheol on 2020. 3. 19..
//
public class Calculator {
	public static void main(String[] args) {
		double result = postFixCalc("132**");
		System.out.println(result);
	}

	public static double postFixCalc(String data) {
		Stack<Double> stack = new ArrayStack<>();

		for (int i = 0; i < data.length(); i++) {
			switch (data.charAt(i)) {
			case '*':
			case '-':
			case '+':
			case '/':
				double right = stack.pop();
				double left = stack.pop();
				double result = calculate(data.charAt(i), left, right);
				stack.push(result);
				break;
			default:
				int num = Character.digit(data.charAt(i), 10);
				if (num < 0) throw new IllegalArgumentException("숫자 또는 연산자만 허용합니다");
				stack.push((double) num);
			}
		}
		double result = stack.pop();
		if (!stack.isEmpty()) throw new IllegalArgumentException("피연산자가 남았습니다");
		return result;
	}

	private static double calculate(char postfixExp, double op1, double op2) {
		switch (postfixExp) {
		case '*':
			return op1 * op2;
		case '-':
			return op1 - op2;
		case '+':
			return op1 + op2;
		case '/':
			if (op2 == 0) throw new ArithmeticException("0으로 나눌 수 없습니다");
			return op1 / op2;
		default:
			throw new IllegalArgumentException("지원하지 않는 연산자");
		}
	}
}

"132**"는 3×2=6을 먼저 계산하고 1×6=6을 계산한다. 연산자를 만났을 때 스택에 값이 두 개보다 적으면 잘못된 식이므로 pop()에서 예외가 난다. 전체 처리 후 값이 하나보다 많이 남아도 잘못된 식이다. 정수나 금전 계산에는 double의 반올림 특성을 고려해 별도 수 타입을 골라야 한다. Java의 실제 애플리케이션에서는 레거시 Stack 클래스보다 Deque 구현인 ArrayDeque를 스택으로 사용하는 방법도 있다. Oracle Deque 문서는 push, pop, peek의 대응 관계를 명시한다.

소스코드

github 이동 (Click)