2-2. [C++] 배열로 구현한 스택

스택을 구현하는 방법은 크게 2가지가 있다.

1. 배열을 이용하는 방법
   
   • 간단하게 구현할 수 있다.
   • 크기 제한이 있는 배열의 특성에 따라 스택의 크기가 고정되는 단점이 있다.
2. 연결 리스트를 이용하는 방법
   • 배열을 이용하는 방법보다는 구현이 까다롭다.
   • 크기 제한이 없는 연결 리스트의 특성에 따라 스택의 크기도 제한이 없다.(isFull() 연산이 필요가 없게 된다.)

아직 연결 리스트를 다루지 않았기 때문에 지금은 배열로 스택을 구현하고

, 후에 연결 리스트를 다룬 뒤에 다시 연결 리스트로 스택을 구현해보자.

---

배열을 이용한 스택 구현

배열을 이용해 정수(int)를 저장하는 스택을 구현해보자.

일단 정수를 저장할 1차원 배열이 필요하다. 이를 int data[MAX_STACK_SIZE] 라고 하자. (MAX_STACK_SIZE는 스택에 저장할 수 있는 최대 요소 개수를 나타낸다.)

또, 스택에서는 삽입/삭제 연산을 위한 스택 상단을 가리키는 변수 top이 필요하다.

스택을 처음 생성하면 top변수는 -1로 초기화 한다. (배열의 인덱스는 0부터 시작하기 때문)

즉, top변수의 값이 -1이면 스택은 공백 상태인 것이다.

 

isEmpty(), isFull() 연산의 유사 코드

isEmpty()연산과 isFull() 연산의 유사 코드를 알아보자.

isEmpty()

if top = -1
	then return TRUE
    else return FALSE

isFull()

if top = MAX_STACK_SIZE - 1
	then return TRUE
    else return FALSE

push(x) 연산의 유사 코드

push(x) 연산의 유사 코드를 알아보자.

push(x)

if isFull()
	then error "overflow"
    else top ← top + 1
    	 data[top] ← x

배열을 이용한 스택은 크기 제한이 있기 때문에 항상 push()하기 전에 isFull() 연산을 해봐야 한다.

스택이 꽉 차지 않았다면 top변수를 하나 증가시킨 후, top이 가리키는 위치에 x를 삽입한다.

pop() 연산의 유사 코드

pop() 연산의 유사 코드를 알아보자.

pop()

if isEmpty()
	then error "underflow"
    else remove ← data[top]
    	 top ← top - 1
         return remove

스택이 비어있다면 삭제/반환할 요소 자체가 없기 때문에 항상 pop()하기 전에 isEmpty() 연산을 해봐야 한다.

스택이 비어있지 않다면 현재 top변수가 가리키는 값을 저장하고, top변수를 하나 감소시킨 후 저장해둔 값을 반환한다.

top변수를 감소시키는 것 자체가 삭제를 한 것과 마찬가지이다.

 

peek() 연산은 pop() 연산의 유사 코드에서 top ← top - 1 부분만 생략하면 된다.

---

본격적으로 스택을 구현하기 전에 스택의 ADT를 바탕으로 UML 다이어그램을 설계해보자.

UML 다이어그램을 바탕으로 C++ 클래스로 스택을 구현해보자.

#include <iostream>
#include <cstdlib>
using namespace std;
#define MAX_STACK_SIZE 20

inline void errorPrint(const char *message) { cout << message << endl; exit(1); }

class ArrayStack {
    int top; // 스택 요소의 개수
    int data[MAX_STACK_SIZE];

public:
    ArrayStack() { top = -1; } // 스택 생성 시 top을 -1로 초기화
    ~ArrayStack() {}

    bool isEmpty() { return top == -1; }
    bool isFull() { return top == (MAX_STACK_SIZE - 1); }

    void push(int x) {
        if (isFull()) errorPrint("Stack overflow");

        data[++top] = x;
    }

    int pop() {
        if (isEmpty()) errorPrint("Stack underflow");

        return data[top--];
    }
    int peek() {
        if (isEmpty()) errorPrint("Stack underflow");

        return data[top];
    }

    void display() {
        cout << "[스택의 항목 수] : " << top + 1 << endl;
        for (int i = 0; i <= top; i++)
            cout << '<' << data[i] << "> ";
        cout << endl << endl;
    }
};

int main() {
    ArrayStack stack;

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

    return 0;
}

/*
실행 결과 : 
[스택의 항목 수] : 9
<1> <2> <3> <4> <5> <6> <7> <8> <9>

[스택의 항목 수] : 6
<1> <2> <3> <4> <5> <6>
*/

위 코드는 아래 이미지를 클릭해 깃허브에서도 확인할 수 있다.