'쌓다' 라는 의미를 가진 스택은 데이터를 차곡 차곡 쌓아 올리는 자료구조를 말한다. 프링글스 통처럼 입구가 하나로, 가장 나중에 넣은 자료가 가장 먼저 삭제된다. (First In Last Out, 후입선출)

스택의 핵심 연산

• push(data) : data를 스택에 쌓아 올린다.
• pop() : 가장 위에 있는 데이터를 빼낸다.
• top() : 스택에서 가장 위에 있는 데이터
• is_empty() : 스택이 비어있으면 1, 아니면 0을 반환
• is_ful() : 스택이 꽉 찼으면 1, 아니면 0을 반환

---

• size() : 스택 안에 있는 데이터의 수

스택 구현 - 1. 배열 (C/C++)

배열로 스택을 구현하기 위해서는, 충분한 공간을 가진 배열과 다음에 원소가 추가될 때 삽입해야 하는 위치를 저장하는 변수가 필요하다.

그래서 배열과 원소 삽입 위치를 저장할 변수를 멤버로 갖는 stack이라는 자료형을 구조체로 새로 만든다.

typedef struct Stack
{
	int arr[100];
	int pos = 0;
};

push 함수

pos는 원소가 추가될 때 삽입해야 하는 위치를 담고 있기 때문에, num이라는 데이터를 담기 위해서는 1. 현재 pos위치에 데이터를 담고 2. pos를 한 칸 위로 옮긴다. 스택이 꽉 차있다면 삽입할 수 없으므로 메세지를 출력하고 프로그램을 종료한다.

void push(Stack* s, int value)
{
	if (is_full(s))
	{
		printf("stack is full\n");
		exit(1);
	}
	s->arr[(s->pos)++] = value;
}

is_full 함수

pos가 배열의 크기와 같거나 넘어설 때 배열에 더 이상 넣을 수 있는 상태가 아니다. (full)

int is_full(Stack* s)
{
	if (s->pos >= 100) return 1; //꽉 참
	return 0; //꽉 안 찼으면 0
}

pop 함수

제일 상단에 위치한 데이터를 삭제하는 함수이다. pos는 다음에 삽입할 때 위치를 저장하고 있기 때문에 1. pos를 한 칸 내린 다음에 2. 해당 위치의 데이터를 return하여 pop기능을 수행한다. stack이 비어있다면 stack에는 pop할 데이터가 없기 때문에 에러 메세지를 출력하고 종료한다.

int pop(Stack* s)
{
	if (is_empty(s))
	{
		printf("stack is empty\n");
		exit(1);
	}
	return s->arr[--(s->pos)];
}

is_empty 함수

pos가 0이하이면 비어있으므로 1, 아니면 데이터가 들어있으므로 0 리턴

int is_empty(Stack* s)
{
	if (s->pos <= 0) return 1; //텅 비어있음
	return 0;
}

top 함수

stack에서 가장 위에 있는 원소의 값을 리턴하는 함수이다. 따라서 pos가 현재 있는 위치에서 1만큼 뺀 위치의 값을 리턴한다. 스택이 비어있다면 출력할 원소가 없으므로 에러 메세지를 보내고 종료한다.

int top(Stack* s)
{
	if (is_empty(s))
	{
		printf("stack is empty\n");
		exit(1);
	}
	return s->arr[(s->pos) - 1];
}

size 함수

스택의 크기는 pos와 같기 때문에 pos의 값을 리턴

int size(Stack* s)
{
	return s->pos;
}

사용 예시

int main(void)
{
	struct Stack mystack; //스택 생성
    
	printf("is_empty: %d\n", is_empty(&mystack)); //비어있으니 1출력
	printf("is_full: %d\n", is_full(&mystack)); //꽉 안 찼으니 0 출력
	printf("현재 배열의 크기: %d\n", size(&mystack)); //0
	push(&mystack, 1);
	push(&mystack, 2);
	push(&mystack, 3); // 10 20 30
	printf("현재 배열의 크기: %d\n", size(&mystack)); //3
	printf("top : %d\n", top(&mystack)); // 30출력
	printf("pop : %d \n", pop(&mystack)); // 30출력 후, 10 20
	printf("top : %d\n", top(&mystack)); // 20출력
	printf("현재 배열의 크기: %d\n", size(&mystack)); //2
	printf("pop : %d \n", pop(&mystack)); // 29출력 후, 10
	printf("top : %d\n", top(&mystack)); // 10출력
	printf("pop : %d \n", pop(&mystack)); // 10출력 후, 없음
	printf("현재 배열의 크기: %d\n", size(&mystack)); //0
	//printf("pop : %d \n", pop(&mystack)); // 에러 나오고 종료
	for (int i = 0; i < 100; i++)
	{
		push(&mystack, 1);
	}
	printf("is_empty: %d\n", is_empty(&mystack)); //비어있지 않으니 0출력
	printf("is_full: %d\n", is_full(&mystack)); //꽉 찼으니 1출력
	printf("현재 배열의 크기: %d\n", size(&mystack)); //100
}

스택 구현 - 2. 연결리스트(C)

head가 방금 push한 노드(=stack의 top)를 가리키도록 구현

1. 구조체로 노드 정의

typedef struct stack //스택 정의
{
	struct node * head = NULL;
}Stack;

typedef struct node // 연결리스트를 구성할 노드 정의
{
	int data;
    struct node* next;
}Node;

2. push 함수

void push(Stack *s, int data)
{
	newnode = (struct node*)malloc(sizeof(struct node)); 
    newnode -> data = data; //그림 0 노드 생성
    newnode -> next = s->head; //그림 1
    s -> head = newnode; //그림2
}

3. empty 함수

head는 스택의 top을 가리키는데 가리키는 것이 없다면 (NULL) stack이 비어있기 때문에 1 리턴.

int empty(Stack *s)
{
	return (s->head == NULL); //비었으면 1, 아니면 0 리턴
}

4. pop 함수

head가 가리키는 노드가 최상단 노드이므로 스택이 비어있는지 먼저 확인하고, 비어있지 않은 경우 head가 가리키는 노드를 pop한다.

int pop(Stack *s)
{
	if (empty(s)) return -1; //비었으면 실행 안함
    struct node* popNode = s -> head;
    int value = popNode -> data;
    s -> head = s -> head -> next;
    free(popNode);
    return vaule;
}

5. top 함수

스택이 비었는지 확인하고 비어있지 않으면 head가 가리키는 노드의 데이터를 리턴

int top(Stack *s)
{
	if (empty(s)) return -1;
    return s->head->data;
}

예시

Stack stack; //스택 생성
printf("%d\n", empty(&stack)); // 비어있으니 1출력
push(&stack, 1);
push(&stack, 2);
push(&stack, 3); //스택에 1, 2, 3 순서로 쌓임
printf("%d\n" pop(&stack)); // 3이 pop
printf("%d\n", top(&stack)); // 2가 출력
printf("%d\n", empty(&stack)); // 스택에 데이터가 있으니 0 출력

stack STL (C++)

스택 헤더 파일

stack STL을 사용하기 위해서는 #include <stack> 헤더파일을 포함해야 한다. int형을 담을 수 있는 s라는 스택을 만들려면 stack s; 로 stack을 선언한다.

#include <stack>
stack<int> s; //stack<데이터타입> 이름; 으로 스택 생성

스택에 데이터 추가하기

s.push(데이터); 

스택에 맨 위 데이터 제거하기

s.pop(); 

스택에 맨 위 데이터 출력하기

printf("%d", s.top()); 

스택이 비어있는지 확인하기

printf("%d", s.empty()); //비었으면 1, 아니면 0 리턴 

스택에 들어있는 데이터 개수 확인하기

printf("%d", s.size());

예시

int main(void)
{
	s.push(1);
	s.push(2);
	s.push(3); // 1 2 3
	printf("%d\n", s.empty()); //비어있지 않으니 0 출력
	printf("%d\n", s.size()); //스택의 크기 출력 3
	s.pop(); // 1 2
	printf("%d\n", s.top()); // 2출력
	s.pop(); // 1
	s.pop(); // 없음
	printf("%d", s.empty()); //비어있으니 1 출력
}

스택 구현 - 3. 리스트 (python)

python에서 스택을 사용하려면 리스트를 사용하면 된다.

stack = [] #비어있는 스택
stack.append(1) #1 push
stack.append(2) #2 push
stack.append(3) #3 push
stack.pop() #3을 pop
stack.pop() #2를 pop
print(stack[-1]) #top
print(len(stack)) #stack의 사이즈