스택 (리스트를 이용한 구현)

리스트를 이용한 구현
앞서 구현한 배열을 리스트로 변경할 경우 연결 리스트의 특징을 그대로 가져오게 된다. 리스트라고 말하면 복잡해 보이지만 "역순으로 삭제가 가능한 리스트이다"라고 생각한다면 그다지 어렵지 않다. 아래의 내용은 비어있는 초기의 리스트 스택 형태이다.

들어가기에 앞서
 1. 리스트 구현과 동일하게 노드가 존재하며 노드는 데이터와 다음 위치를 가리킬 수 있는 노드를 가지고 있다.
 2. 스택은 top이 아닌 head로 변경이 되며 이는 현재 위치를 가리키는 변수이다.

리스트를 이용한 스택의 초기 상태

① 데이터 삽입을 보자. 배열을 이용한 스택과 동일하게 Push()라는 함수 호출로 값을 삽입한다. 
먼저 10을 추가해보자. 10을 추가할 경우 head는 새로운 노드를 가리키게 되며 nextNode는 자기 자신의 이전 노드를 가리키게 한다. 아래의 그림을 보면 이해가 될 것이다.

10과 20이 추가된 그림, head와 nextNode의 이동 방향을 유심히 볼 것

② 데이터의 삭제와 반환을 보자. 배열을 이용한 스택과 동일하게 Pop()이라는 함수 호출로 데이터를 삭제와 반환을 한다. 아래의 그림을 보자.
 1) 삭제할 데이터와 주소를 임시 변수에 저장한다.
 2) head를 nextNode를 가리키게 한다.
 3) 노드를 삭제를 한다. 

리스트 스택의 삭제 방법

중요한 사항은 다 알아보았다. 코드로 구현해보고 이해가 안 된다면 디버깅을 하거나 그림을 그리도록 하자.

#include <iostream>
 
using namespace std;
 
#define MAX_LENGTH 5
 
// 노드 구조체
typedef struct node
{
    // 생성자
    node() : data(0), nextNode(nullptr) {}
 
    // 데이터
    int data;
 
    // 다음 노드를 가리키는 포인터
    node* nextNode;
}NODE;
 
// 스택 구조체
typedef struct listStack
{
    // 생성자
    listStack() : head(nullptr) {}
 
    // 노드
    NODE* head;
}LISTSTACK;
 
void Push(LISTSTACK* stack, int data)
{
    // 새로운 노드를 생성
    NODE* newNode = new NODE;
    newNode->data = data;
    newNode->nextNode = stack->head;
 
    // head가 새로운 노드를 가리키게 설정
    stack->head = newNode;
}
 
bool IsEmpty(LISTSTACK* stack)
{
    // 비어있을 경우 true를 반환
    if (stack->head == nullptr)
        return true;
 
    return false;
}
 
int Pop(LISTSTACK* stack)
{
    if (IsEmpty(stack))
    {
        cout << "스택이 비어있습니다." << endl;
        return 0;
    }
 
    // 삭제하기 전 데이터와 노드를 임시 변수에 저장
    int data = stack->head->data;
    NODE* node = stack->head;
 
    // head의 다음 위치를 head로 가리키게 설정한 후 노드 삭제
    stack->head = stack->head->nextNode;
    delete node;
    
    return data;
}
 
int Peek(LISTSTACK* stack)
{
    if (IsEmpty(stack))
    {
        cout << "스택이 비어있습니다." << endl;
        return 0;
    }
 
    // head가 저장된 데이터 반환
    return stack->head->data;
}
 
int main()
{
    // 스택 생성
    LISTSTACK stack;
 
    // 데이터 삽입
    for (int i = 0; i < 5; ++i)
    {
        Push(&stack, i);
    }
 
    // 데이터 검색
    cout << Peek(&stack) << endl;
 
    // 데이터가 존재하지 않을 때까지 루프문 순회
    while (IsEmpty(&stack) == false)
    {
        // 데이터 출력
        cout << Pop(&stack) << endl;
    }
}