자료 구조 - 스택

3 minute read

‘c++로 쉽게 풀어쓴 자료구조 1판 - 천인국, 최영규’ 책을 참고하여 작성한 포스트입니다.

스택

스택이란 자료의 입출력이 후입선출(LIFO:Last-In First-Out)의 형태로 일어나는 자료구조를 말한다.

스택 상단(stack top): 스택에서 입출력이 이루어지는 부분
스택 하단(stack bottom): top의 반대 부분
요소(element): 스택에 저장되는 것, 항목
공백(empty)상태: 스택에 요소가 하나도 없는 상태
포화(full)상태: 스택에 더 이상 요소를 넣을 수 없는 상태

스택의 추상 자료형

데이터: 후입선출의 접근 방법을 유지하는 요소들의 모음
연산
 - push(x): 주어진 요소x를 스택의 맨 위에 추가
 - pop(): 스택이 비어있지 않으면 맨 위에 있는 요소를 삭제하고 반환
 - isEmpty(): 스택이 비어있으면 true, 그렇지 않으면 false 반환
 - peek(): 스택이 비어있지 않으면 맨 위에 있는 요소를 삭제하지 않고 반환
 - isFull(): 스택이 가득 차 있으면 true, 그렇지 않으면 false 반환
 - size(): 스택 내의 모든 요소들의 개수를 반환
 - display(): 스택 내의 모든 요소들을 출력함

스택의 구현

스택의 구현 방법으로 배열 혹은 연결 리스트를 사용할 수 있다.
여기선 배열로 구현하고 연결 리스트는 나중에!

배열을 이용한 스택의 표현

배열은 순차적인 메모리 공간에 할당된다고 해서 순차적 표현(sequential representation)이라고도 한다. 배열은 같은 자료형의 변수를 여러 개 만드는 경우에 특히 유용하고, 항목을 저장할 수 있는 여러 개의 공간을 제공한다. 각 공간은 정확히 하나의 항목만을 담으며 각 항목들은 인덱스 번호를 통해 직접 접근이 가능하다. 인덱스 번호는 0부터 시작한다.

직접 구현해서 책과 내용이 다를 수 있습니다

구현 전!

// 스택의 상단을 나타내는 인덱스
int top = -1;
// 스택을 구현할 배열의 사이즈
int MAX_STACK_SIZE = 10;
// 스택을 구현할 배열
int stack[10];
// 에러 처리를 메세지 출력으로 대신함
void printErrorMSG(string s) {
    printf("%s", s);
}

push(x) 연산

void push(x) {
    if (top == MAX_STACK_SIZE - 1) {
        printErrorMSG("overflow");
    } else {
        //비어 있는 배열의 자리로 top 인덱스를 옮기고
        //그 위치에 x를 대입
        stack[++top] = x;
    } 
}

pop() 연산

int pop() {
    if(top == -1) { // 스택이 비어 있는 경우
        printErrorMSG("Stack is empty!");
    } else {
        //스택의 상단을 가리키는 원소 반환 후
        //top 인덱스를 1만큼 감소
        return stack[top--]; 
    }
}

isEmpty() 연산

bool isEmpty() {
    // 비어 있을 때(초기화한 경우도 마찬가지)
    // 스택 상단의 인덱스는 -1로 정의했다
    if (top == -1) {
        return true;
    } else {
        return false;
    }
}

peek() 연산

int peek() {
    if(top == -1) { // 스택이 비어 있는 경우
        printErrorMSG("Stack is empty!");
    } else {
        // 스택 상단의 원소 반환
        return stack[top];
    }
}

isFull() 연산

bool isFull() {
    if(top == MAX_STACK_SIZE - 1) {
        return true;
    } else {
        return false;
    }
}

size() 연산

int size() {
    // 배열의 인덱스는 0에서 시작하므로
    return top+1;
}

display() 연산

void display() {
    for(int i = 0; i <= top; i++) {
        printf("stack의 %d번째 요소는 %d입니다.\n", i, stack[i]);
    }
}

수식의 계산

후위 표기법을 이용해 사칙연산을 구현한다. 후기 표기법은 스택과 잘 맞는 표기법이고, 괄호나 사칙연산의 우선순위를 고려하지 않아도 되는 장점이 있다.
사칙 연산 기호들은 char형이지만 int, double 등으로 자동 형변환 된다.

ArrayStack은 위에서 구현한 Stack .

중위 표기법을 후기 표기법으로 변환

void convert(char* ch, int len, char* ch2) {
	ArrayStack arrayStack;
	int idx = 0;
	for(int i=0; i<len; ++i) {
		if(ch[i] == '+' || ch[i] == '-' || ch[i] == '*' 
		   || ch[i] == '/' || ch[i] == '(' || ch[i] == ')') {
			switch (ch[i]) {
				case '+' : case '-' : case '*' : case '/' :
					if(arrayStack.peek() == '*' || arrayStack.peek() == '/') {
						ch2[idx++] = arrayStack.pop();
					}
					arrayStack.push(ch[i]);
					break;
				case '(' :
					arrayStack.push(ch[i]);
					break;
				case ')' :
					while(!arrayStack.isEmpty()) {
						double d = arrayStack.pop();
						if(d != '(') ch2[idx++] = d;
						else break;
					}
					break;
			}
		} else {
			ch2[idx++] = ch[i];
		}
	}
	while(!arrayStack.isEmpty()) {
		ch2[idx++] = arrayStack.pop();
	}
}

후위 표기법 계산

double calculate(char* ch, int len) {
	ArrayStack arrayStack;
	for(int i=0; i<len; ++i) {
		char c = *(ch + i);
		if (c == '+' || c == '-' || c == '*' || c == '/') {
			double right = arrayStack.pop();
			double left = arrayStack.pop();
			switch(c) {
				case '+' :
					arrayStack.push(left + right);
					break;
				case '-' :
					arrayStack.push(left - right);
					break;
				case '*' :
					arrayStack.push(left * right);
					break;
				case '/' :
					arrayStack.push(left / right);
					break;
			}
		} else {
			arrayStack.push(c - '0');
		}
	}
	return arrayStack.pop();
}

확인

int main()
{
	char ch[10] = "82/3-32*+";
	cout << calculate(ch, strlen(ch))<< endl;
	char ch2[12] = "8*2-3*(3+2)";
	char ch3[12];
	convert(ch2, strlen(ch2), ch3);
	for(int i=0; i< strlen(ch3); ++i) {
		cout << ch3[i] << " ";
	}
	cout << endl;
	cout << calculate(ch3, strlen(ch3)) << endl;
	return 0;
}

/* print
7
stack is empty
stack is empty
8 2 * 3 3 2 + * - 
1
*/

Chocobubble