[자료구조] 스택

스택

자료의 입력과 출력이 LIFO(Last In First Out : 후입선출)의 형태를 띄는 자료 구조이다. 마지막으로 입력된 자료가 먼저 나오게 된다는 말이다.

스택에서는 맨 윗부분(top)에서만 입출력이 가능하고, 중간에서는 불가능하다. 책을 상자에 넣을 때 차곡차곡 쌓다가, 중간에 있는 책을 꺼낼 때는 위에서 부터 꺼낸다고 생각하면 된다. 아래는 스택의 연산들이다.

init() : 스택을 초기화한다.
is_empty() : 스택이 비어있는지 확인한다.
is_full() : 스택이 가득 차 있는지 확인한다.
size() : 스택에 저장된 요소들의 수를 반환한다.
push(x) : x를 스택의 맨 윗부분에 추가한다.
pop() : 스택의 맨 윗부분에 있는 요소를 삭제하고 반환한다.
peek() : 스택의 맨 윗부분에 있는 요소를 반환한다.

스택의 구현

배열을 이용한 스택

정수를 저장할 배열을 stack[MAX_SIZE] 라고 하자. MAX_SIZE는 스택에 저장할 수 있는 최대 개수이다. 스택은 항상 top에서만 연산이 일어나므로, top 변수도 선언하자.

const int MAX_SIZE = 256; // 스택에 저장될 요소의 최대 개수
int stack[MAX_SIZE];
int top; // 스택의 맨 윗부분을 가리킬 변수

init()

초기화는 스택의 top이 -1로 초기화하면 된다. 0은 스택의 가장 아랫부분에 있는 요소를 뜻하므로 0이 아니라 -1임을 알아두자.

void init() { top = -1; }

is_empty(), is_full(), size()

top이 -1이면 공백이고, MAX_SIZE - 1과 같다면 가득 찬 상태이다. size()는 현재 top의 값에 1을 더해주면 된다.

bool is_empty() { return top == -1; } // top이 -1이면 true 아니면 false
bool is_full() { return top == MAX_SIZE - 1; } // top이 MAX_SIZE - 1이면 true 아니면 false
int size() { return top + 1; }

push(x)

top의 값을 하나 증가시키고, stack[top]에 저장하면 된다. 이때, 스택이 가득찬 상태인지를 확인해 예외 처리를 해주자.

void push(int element) {
    if (is_full()) {
        cout << "스택 포화";
        exit(1);
    }
    else {
        stack[++top] = element; // top++;
                                // stack[top] = element; 와 동일
    }
}

pop(), peek()

stack[top]의 값을 반환하고 top의 값을 하나 줄여주면 된다. peek()의 경우에는 stack[top]의 값을 반환시키면 끝이다. 스택이 비었을 경우에 대한 예외처리도 해주자.

int pop() {
    if (is_empty()) {
        cout << "스택 공백";
        exit(1);
    }
    else {
        return stack[top--]; // stack[top]의 값을 반환하고 top이 감소
    }
}

int peek() {
    if (is_empty()) {
        cout << "스택 공백";
        exit(1);
    }
    else {
        return stack[top];
	}
}

여기서 마지막으로 현재 스택을 출력해주는 함수를 만들어주자.

void print() {
    cout << "현재 스택 : ";
	for (int i = 0; i <= top; i++) {
		cout << stack[i] << " ";
	}
    cout << endl;
}

전체 코드는 다음과 같다.

#include <iostream>
#include <cstdlib>

using namespace std;

class Array_Stack {    
    static const int MAX_SIZE = 256; //스택에 저장될 요소의 최대 개수.
    /*const int MAX_SIZE = 256; 클래스가 선언되었지만 객체가 생성되지 않아 배열 선언에서
                                MAX_SIZE의 값을 알 수 없게 되어버린다. static을 사용해
                                상수를 정적으로 선언해 오류 해결. */
    int stack[MAX_SIZE];
    int top; // 스택의 맨 윗부분을 가리킬 변수
    
public:
    Array_Stack() { top = -1; }
    ~Array_Stack() { }
    void init() { top = -1; } // 스택 초기화
    bool is_empty() { return top == -1; } // top이 -1이면 true 아니면 false
    bool is_full() { return top == MAX_SIZE - 1; } // top이 MAX_SIZE - 1이면 true 아니면 false
    int size() { return top + 1; } // 현재 크기
    
    // 요소 삽입
    void push(int element) {
        if (is_full()) {
            cout << "스택 포화";
            exit(1);
        }
        else {
            stack[++top] = element;
        }
    }
    
    // 요소 제거, 반환
    int pop() {
        if (is_empty()) {
            cout << "스택 공백";
            exit(1);
        }
        else {
            return stack[top--];
        }
    }
	
    // 요소 출력
    int peek() {
        if (is_empty()) {
            cout << "스택 공백";
            exit(1);
        }
        else {
            return stack[top];
	    }
    }
    
    // 스택 출력
    void print() {
        cout << "현재 스택 : ";
	    for (int i = 0; i <= top; i++) {
		    cout << stack[i] << " ";
	    }
        cout << endl;
    }
};

// 스택 테스트
int main() {
    Array_Stack as;
    
    for (int i = 0; i < 4; i++) {
        as.push(i);
    }
    as.print();
    cout << "pop \t: " << as.pop() << endl;
    cout << "peek \t: " << as.peek() << endl;
    cout << "size \t: " << as.size() << endl;
    
    as.push(9);
    as.print();
    
    return 0;
}

출력

현재 스택 : 0 1 2 3
pop     : 3
peek    : 2
size    : 3
현재 스택 : 0 1 2 9

연결 리스트를 이용한 스택

연결 리스트란 자료들을 서로 연결하여 하나로 이어주는 방법을 뜻한다. 배열과 비교하자면 0번은 'A', 1번은 'B', 4번은 'E' 로 자료들을 표현한다면, 연결 리스트는 'A' 다음에 'B', 'B' 다음에 'C', ... , 'D' 다음에 'E' 처럼 표현한다. 연결 리스트도 여러 종류가 있는데, 이번에는 단순 연결 리스트(연결된 방향이 하나인 연결 리스트)를 이용해 만들어보겠다.

연결리스트에서는 is_full() 연산이 없다는 것만 알아두자. 동적으로 메모리를 할당시키기 때문에 is_full() 연산이 의미가 없다.

노드를 표현할 구조체를 Node라고 하자. Node에는 정수값을 저장할 data를 선언하고, 다음 노드를 가리키는 link 포인터를 선언하자.

struct Node {
    int data;
    Node* link;
};

스택의 맨 윗부분을 뜻하는 top은 어떻게 될까? 마지막에 들어간 Node를 가리키는 포인터가 되면 된다.

Node* top;

init()

초기화 연산은 마찬가지로 간단하다. top에 NULL을 복사하면 끝이다.

void init() { top = NULL; }

is_empty(), size()

공백 상태인지 확인하려면 당연히 top이 NULL포인터인지 확인하면 된다. size()연산은 마지막 노드의 link가 NULL을 가리킬 때 까지, top에서 노드를 하나하나 찾아가면서 개수를 헤아리면 된다.

bool is_empty() { return top == NULL; } // top이 Null포인터면 true, 아니면 false

int size() {
    int count = 0;
    
    for (Node* n = top; n != NULL; n = n->link) {
        count++;
    }
    return count;
}

push(x)

삽입 연산은 어떻게 해야할까? 다음과 같은 과정을 거쳐야한다.

새로운 노드를 하나 만들어서 요소를 저장한다.
새로운 노드의 link가 마지막 노드를 가리킨다.
top이 새로운 노드를 가리킨다.

이를 구현해보자.

void push(int element) {
    Node* node = new Node; // 동적할당
    node->data = element; // 새로운 노드를 하나 만들어서 요소를 저장한다.
    node->link = top; // 새로운 노드의 link가 마지막 노드를 가리킨다.
    top = node; // top이 새로운 노드를 가리킨다.
}

pop()

삭제 연산은 top에 있는 노드의 요소를 반환하면 된다.

삭제할 노드를 가리킬 포인터 node와 item 변수를 선언한다.
node가 마지막 노드를 가리킨다.
top이 그 아래 노드를 가리킨다.
node를 할당 해제해주고 item을 반환한다.

int pop() {
    Node* node;
    int item;   // 변수 선언
    
    if (is_empty()) {
        cout << "스택 공백" << endl;
        exit(1);
    }
    else {
        node = top; // node가 마지막 노드를 가리킨다.
        top = node->link; // top이 그 아래 노드를 가리킨다.
        
        item = node->data;
        delete node;
        return item; // node를 할당 해제해주고 item을 반환한다.
    }
}

스택이 공백일 때의 예외 처리도 잊지 말자.

peek()

마지막 노드의 data를 반환해주면 된다. 즉, top->data를 반환하라는 소리가 된다. 마찬가지로 예외 처리를 잊지 말자.

int peek() {
    if (is_empty()) {
        cout << "스택 공백" << endl;
        exit(1);
    }
    else {
        return top->data;
    }
}

마지막으로 현재 스택을 출력해주는 함수이다. size()와 비슷하게 구현하면 된다.

void print() {
    cout << "현재 스택 : ";
    for (Node* n = top; n != NULL; n = n->link) {
        cout << n->data << " ";
    }
    cout << endl;
}

전체코드

#include <iostream>
#include <cstdlib>

using namespace std;

class Linked_Stack {
    struct Node {
        int data;
        Node* link;
    };
    Node* top;
    
public:
    Linked_Stack() { top = NULL; }
    ~Linked_Stack() { }
    void init() { top = NULL; }
    bool is_empty() { return top == NULL; }
    
    // 스택의 크기
    int size() {
        int count = 0;
    
        for (Node* n = top; n != NULL; n = n->link) {
            count++;
        }
        return count;
    }
    
    // 삽입
    void push(int element) {
        Node* node = new Node; // 동적할당
        node->data = element; // 새로운 노드를 하나 만들어서 요소를 저장한다.
        node->link = top; // 새로운 노드의 link가 마지막 노드를 가리킨다.
        top = node; // top이 새로운 노드를 가리킨다.
    }
    
    // 삭제, 반환
    int pop() {
        Node* node;
        int item;   // 변수 선언
    
        if (is_empty()) {
            cout << "스택 공백" << endl;
            exit(1);
        }
        else {
            node = top; // node가 마지막 노드를 가리킨다.
            top = node->link; // top이 그 아래 노드를 가리킨다.
        
            item = node->data;
            delete node;
            return item; // node를 할당 해제해주고 item을 반환한다.
        }
    }
    
    // 반환
    int peek() {
        if (is_empty()) {
            cout << "스택 공백" << endl;
            exit(1);
        }
        else {
            return top->data;
        }
    }
    
    // 현재 스택 출력
    void print() {
        cout << "현재 스택 : ";
        for (Node* n = top; n != NULL; n = n->link) {
            cout << n->data << " ";
        }
        cout << endl;
    }
};

// 스택 테스트
int main() {
    Linked_Stack ls;
    
    for (int i = 0; i < 10; i++) {
        ls.push(i);
    }
    
    ls.print();
    cout << "pop : " << ls.pop() << endl;
    cout << "peek : " << ls.peek() << endl;
    ls.push(11);
    ls.print();
    cout << "현재 스택 크기 : " << ls.size() << endl;

	return 0;
}

출력

현재 스택 : 9 8 7 6 5 4 3 2 1 0
pop : 9
peek : 8
현재 스택 : 11 8 7 6 5 4 3 2 1 0
현재 스택 크기 : 10

스택의 활용

스택은 어디에서 사용될까? 방금까지 만들던 함수에 사용된다. 정확히는, 함수의 호출에 스택이 사용된다. 아래 코드를 예로 들자면,

int main() {               int a() {               int b() {
    a();                       b();                    return 0;
    return 0;                  return 0;           }
}                          }

main() 함수가 먼저 호출되면, main(), a(), b() 함수 순으로 스택에 쌓이게 된다.

함수 외에도 편집기에서 되돌리기 기능, 계산기에서 수식이 계산되는 과정 등에도 사용된다.

[Reference]

http://www.kyobobook.co.kr/product/detailViewKor.laf?ejkGb=KOR&mallGb=KOR&barcode=9788970509419&orderClick=LAG&Kc=

자료구조 - 교보문고

컴퓨터로 어떤 문제를 해결하기 위해 필요한 자료들을 효율적으로 관리하고 구조화시키기 위한 학문 '자료구조'. 이 책은 자료구조를 보다 명확하게 배울 수 있도록 구성되어 있다. 각 장에서는

www.kyobobook.co.kr

728x90

저작자표시 비영리 변경금지

'알고리즘(Algorithm) > Data Structure' 카테고리의 다른 글

[자료구조] 그래프 (0)	2022.04.04
[자료구조] 우선순위 큐와 힙 (0)	2022.03.15
[자료구조] 트리 (0)	2022.03.14
[자료구조] 큐 (0)	2022.03.04

꼼지락 IT 공부방

[자료구조] 스택

스택

스택의 구현

스택의 활용

'알고리즘(Algorithm) > Data Structure' 카테고리의 다른 글

티스토리툴바

[자료구조] 스택

스택

스택의 구현

스택의 활용

'알고리즘(Algorithm) > Data Structure' 카테고리의 다른 글

'알고리즘(Algorithm)/Data Structure' Related Articles

티스토리툴바