추상 자료형 스택에 대해서 알아보자:)

개요

---

스택은 많이 사용되는 추상자료형의 하나이다.

스택하면 메모리의 스택 공간을 흔히 생각할 수 있는데 구분하기 위해서 컴퓨터 내부의 스택은 시스템 스택, 우리가 만들어 사용할 스택을 사용자 스택이라고 한다.

그렇다면 이제 스택을 한번 구현해 보겠다.

---

스택

---

영단어 stack의 의미는 쌓아올린 더미들을 말한다.

스택과 같은 예시를 실생활에서 찾아보면 급식 먹을 때 쌓아올린 식판을 들 수 있다.

누군가가 식판을 놓으면 차곡차곡 그 위로 식판을 올려놓게 된다. 그리고 설거지를 할 때는 맨 처음 식판을 꺼내서 하는 것이 아니라 맨 마지막의 식판을 먼저 씻는다.

이런 개념을 이해하는데에는 어렵지가 않다. 이런 개념을 추상화 한 것이 추상자료형 스택이다. 추상자료형 리스트와 같이 스택의 주요 작업은 삽입, 삭제, 검색이다.

그러나 내가 원하는 위치에 삽입, 삭제가 가능한 리스트와는 달리 스택의 모든 작업은 항상 가장 마지막 위치에서만 작업이 가능하다.

스택의 가장 위를 스택 탑(stack top)이라고 한다. 스택에 어떤 데이터를 삽입하는 작업을 푸시(push)라고 하며 빼는 작업은 팝(pop)이라고 한다.

스택 구조를 후입선출 구조라고 본다. 가장 나중에 들어온 데이터가 나갈 때는 가장 먼저 빠져나가기 때문이다.

영어로는 LIFO(Last In First Out), LCFS(Last Come First Served)라고 하며 스택에서의 삽입, 삭제는 한 쪽 끝에서만 일어난다.

---

배열에 의한 스택

---

스택의 헤더파일과 소스코드는 리스트와 거의 유사하다.

작업 대상이 되는 스택을 함수에 전달하려면 스택 구조체를 가리키는 포인터를 넘기면 된다.

푸시, 팝은 배열의 가장 오른쪽 끝에서 이루어진다.

빈 스택을 초기화할 때 탑 인덱스를 0으로 잡았으면 그 위치가 첫번째 아이템이 들어올 위치가 된다.

즉, 탑 인덱스가 다음 삽입할 데이터의 위치를 나타내므로 푸시 명령이 들어오면 곧바로 탑 인덱스 위치에 삽이되어야한다.

그리고 탑 인덱스는 다음 푸시를 위해서 그 즉시 1만큼 증가한다. 따라서 이 경우, 스택의 가장 위에있는 아이템은 항상 현재의 탑 인덱스 바로 아래 있는 아이템이 된다.

팝 작업시에 미리 인덱스를 감소시키는 것은 이러한 이유 때문이다.

따라서 탑 인덱스를 -1로 초기화 하기도 한다. 이 방법에서는 미리 탑 인덱스를 증가시킨 후에 푸시가 가해져야한다.

이렇게 하면 스택 탑은 항상 현재 스택의 가장 위에 있는 데이터를 가리키게 된다.

그렇기 때문에 팝을 할 때도 아이템을 삭제하고 인덱스를 줄이면 된다.

---

연결 리스트에 의한 스택

---

#ifndef _STACK_
#define _STACK_

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct LinkedStackType
{
    int currentElementCount;    // 현재 원소의 개수
    StackNode* pTopElement;        // Top 노드의 포인터
} LinkedStack;
LinkedStack* createLinkedStack();
int pushLS(LinkedStack* pStack, StackNode element);
StackNode* popLS(LinkedStack* pStack);
StackNode* peekLS(LinkedStack* pStack);
void deleteLinkedStack(LinkedStack* pStack);
int isLinkedStackFull(LinkedStack* pStack);
int isLinkedStackEmpty(LinkedStack* pStack);
#endif

#ifndef _COMMON_LIST_DEF_
#define _COMMON_LIST_DEF_

#define TRUE        1
#define FALSE        0

#endif

연결 리스트로 구현한 스택에서 탑은 항상 첫번째 노드이다.

따라서 헤더노드가 새로 만든 노드를 가리키게 하면 된다.

이렇게 구현 했을 때 연결리스트와 상당히 유사하다. 따라서 스택은 리스트의 특수한 경우로 취급할 수 있다.

연결 리스트로 스택을 구현할 때 스택 탑 노드를 가장 처음에 두는 이유는 시간적 효율성을 위한 것이다.