자료구조 - 스택

스택(Stack) : LIFO(Last-In First-Out) 구조

 

스택의 용도ex) 함수호출, Undo 기능, 괄호검사, 계산기, 미로탐색 etc,,

스택의 구현) 배열 or linkedlist 사용

 

C++로 구현한 배열버전 Stack

# ArrayStack.cpp

#include "ArrayStack.h"

int main()
{
	ArrayStack stack;
    for(int i = 1; i<10; i++)
    	stack.push(i);
    stack.display();
    stack.pop();
    stack.pop();
    stack.pop();
    stack.display();
 }

# ArrayStack.h

#include <cstdio>

const int MAX_STACK_SIZE = 20;

inline void error(char *message){
	printf("%s\n",message);
    exit(1);
}

class ArrayStack
{
	int top; // 요소의 개수
    int data[MAX_STACK_SIZE];
public:
	ArrayStack() { top = -1; }
    ~ArrayStack() {}
    bool isEmpty() { return top == -1; }
    bool isFull() { retrun top == MAX_STACK_SIZE-1; }
    
    void push (int e) { // 요소삽입
    	if( isFull() ) error("스택 포화 에러");
        data[++top] = e;
    }
    int pop() {
    	if( isEmpty() ) error("스택 공백 에러");
        return data[top--];
    }
    int peek() {
    	if( isEmpty() ) error("스택 공백 에러");
        return data[top];
    }
    void display() {
    	printf("[스택 항목의 수 = %2d] ==> ", top+1);
        for(int i = 0; i <= top; i++){
        	printf("<%2d>",data[i])'}
        printf("\n");
    }
};

<이를 활용한 괄호검사 알고리즘 만들기>

# BracketChecker.h

#include "ArrayStack.h"
#include <cstdio>

bool CheckMatching( char* filename ){
	FILE *fp = fopen(filename, "r");
    if( fp == NULL ) error("Error : 파일 존재하지 않습니다.\n");
    
    int nLine = 1, nChar = 0;
    ArrayStack stack;
    char ch;
    
    while((ch = getc(fp)) ! = EOF) { // getc는 단일문자 읽기 EOF는 파일끝
    	if( ch == '\n') {nLine++;}
        nChar++;
        if( ch == '[' || ch == '(' || ch == '{' ){
        	stack.push(ch);}
        else if( ch == ']' || ch == ')' || ch == '}' ){
        	int prev = stack.pop();
            if( (ch == ']' && prev != '[' ) ||
                (ch == ')' && prev != '(' ) ||
                (ch == '}' && prev != '{' )){ break;}
        }
    }
    fclose(fp);
    printf("[%s] 파일 검사결과:\n", filename);
    if( !stack.isEmpty()){
    	printf("Error! (라인수 = %d, 문자수= %d) \n\n", nLine,nChar);}
    else{
    	printf(" OK: (라인수 = %d, 문자수= %d) \n\n", nLine,nChar);}
    return stack.isEmpty();
 };
 
 # BracketChecker.cpp
 
 #include "BracketChecker.h"
 
 int main(){
 	CheckMatching("ArrayStack.h")
    return 0;
}