스택은 LIFO (Last In First Out), 즉 후입선출 방식의 자료구조이다
스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 입출력할 수 없다
이러한 특징 때문에 자료의 출력 순서가 입력 순서의 역순으로 이루어져야 할 때 사용된다
먼저 스택의 ADT 부터 알아보자
// 최대 크기가 N인 공백 스택 생성
create(N)
// 스택이 가득 차 있는지 확인
is_full(s)
{
if (스택의 원소 수 == N) return TRUE;
else return FALSE;
}
// 스택이 비었는지 확인
is_empty(s)
{
if (스택의 원소 수 == 0) return TRUE;
else return FALSE;
}
// 스택에 데이터 삽입
push(s, data)
{
if (is_full(s)) return ERROR;
else 스택의 top에 data 추가
}
// 스택에서 데이터 추출
pop(s)
{
if (is_empty(s)) return ERROR;
else 스택의 맨 위 원소를 제거하고 반환
}
스택은 배열이나 리스트로 구현 가능한데, 상기한 스택 ADT를 토대로 먼저 배열로 구현한 스택을 알아보자
배열 스택
배열 스택은 크기가 정해진 배열을 top 변수를 이용해 가장 최근에 저장된 데이터를 가리켜 배열이 비었는지, 가득 차 있는지 확인하며 삽입, 삭제를 하는 자료구조이다
#define MAX_STACK_SIZE 10
int S[MAX_STACK_SIZE];
int top = -1;원하는 자료형의 1차원 배열을 생성한 뒤, 스택에서 가장 최근에 입력된 자료를 가리키는 top 변수도 생성한다
생성한 top 변수를 -1로 초기화하면 배열 스택 생성이 완료된 것이다
스택의 top을 반드시 -1로 초기화해야 하는 것은 아니고, 0으로 초기화하면 push나 pop 연산에서 증감연산자의 위치와 is_empty(), is_full() 함수의 조건만 바뀔 뿐이므로 자신이 원할 대로 초기화하면 된다
삽입
스택에선 삽입 기능을 push라고 이름 짓는다
이 글에서는 따로 is_full()이나 is_empty()를 따로 정의하지 않을 예정인데, 그 이유는 따로 정의하지 않아도 top 값을 배열의 크기와 비교하여 구현할 수 있기 때문이다
push()를 구현하면 다음과 같다
void push(int *S, int *top, int data)
{
if (is_full) return; // is_full = (*top) >= MAX_STACK_SIZE -1
S[++(*top)] = data;
}3번 라인에서 스택이 가득 차 있는지 확인 후, 만약 비었다면 top값을 먼저 증가시킨 뒤, 스택의 가장 위 자리에 데이터를 삽입한다
만약 top 변수를 0으로 초기화 했다면 4번 라인의 증감연산자를 (*top)++로 바꾸고 is_full의 조건을 (*top) >= MAX_STACK_SIZE로 바꾸면 된다
삭제
스택에서 삭제 기능을 pop이라고 이름 짓는다
int pop(int *S, int *top)
{
if (is_empty) return exit(-1); // is_empty = (*top) <= MAX_STACK_SIZE - 1
return S[(*top)--];
}3번 라인에서 스택이 완전 비었는지 확인 후, 완전 비었다면 함수를 종료하고, pop할 데이터가 있다면 가장 위에 있는 데이터를 return 한뒤 top 값을 감소시킨다
pop()도 마찬가지로 top 변수를 0으로 초기화 했다면 4번 라인의 증감연산자를 --(*top)로 바꿔고 is_empty의 조건을 (*top) <= 0으로 바꾸면 된다
SLL 스택
배열 스택은 배열로 구현되다 보니 크기가 정해져 있다는 단점이 있다
하지만 C에서는 malloc() 함수를 이용해 동적으로 삽입 삭제가 가능한 단순 연결 리스트 스택을 사용할 수 있다
정의
typedef int Data;
typedef struct
{
Data data;
struct Node *Next;
} Node;
생성
Node *S = NULL;
S = (Node *)malloc(sizeof(Node));
S -> data = 10;
S -> Next = NULL;
위와 같이 단순 연결 리스트 스택을 정의하고 생성한다
생성을 마치면 아래 그림과 같은 모양을 띈다
그림만 보면 그냥 단순 연결 리스트와 뭐가 다른가 싶지만,
스택의 특성을 생각해보자
맨 위에 삽입하고 맨 위의 데이터만 삭제한다
이러한 특성 덕분에 앞서 배열처럼 top 변수를 따로 만들지 않아도 헤드 포인터만 가지고 삽입, 삭제가 가능하다
삽입
void push(Data value)
{
Node *p = (Node *)malloc(sizeof(Node)); // ①
p -> data = value; // ②
p -> next = S; // ③
S = p; // ④
}
삭제
Node* pop()
{
if (S = NULL) return NULL;
Node *p = S; // ①
S = S -> Next; // ②
return p; // ③
}
마지막으로 배열 스택과 리스트 스택의 특징을 정리해보면 아래와 같다
| 배열 스택 | 리스트 스택 |
| 구현이 쉽다 크기가 정적이다 |
배열보단 구현이 쉽다 크기가 동적이다 일반 리스트보다 삽입, 삭제가 용이하다 |