👋 대표적인 선형 자료구조 "스택"에 대해 알아보자!
✏️ 스택 Stack
스택(stack)은 "쌓다, 무더기"라는 뜻을 가진 영단어이다.
사전적 의미에서도 알 수 있듯, 스택은 말 그대로 데이터를 차곡차곡 쌓아올리는 형태의 자료구조이다.
흔히 스택을 프링글스에 비유하는데, 빈통에 차곡차곡 프링글스를 넣은 후 우리는 제일 마지막에 넣은 것 먼저 꺼내 먹게 된다. 또 우리는 오직 한 입구를 통해서만 과자를 꺼낼 수 있다! 프링글스의 이러한 특징을 스택에 적용해보자.
✔️ 스택의 특징
-
LIFO (Last In First Out), 후입선출
Last In First Out 해석 그대로 "가장 마지막에 들어온 데이터가 가장 먼저 나간다"는 의미이다. -
Top 에서만 데이터에 접근이 가능
입구가 하나 뿐인 프링글스처럼, 스택도 이와 유사하게 데이터의 삽입, 삭제 등이 일어날 수 있는 곳은 단 한 곳 뿐이다. 이 부분을 "Top"이라고 부르며 가장 최근에 삽입된 데이터가 존재하는 곳이다.
✔️ 스택의 대표적인 연산
- push 데이터의 삽입
- pop 가장 최근에 삽입된 데이터 삭제
- top 가장 최근에 삽입된 데이터 반환
- size 스택의 크기 반환
- empty 스택이 비어있는지 확인
✏️ 스택 구현하기 (동적 배열, 링크드 리스트, C++ STL)
백준 10828번
백준 10828번에서 주어진 메소드들을 가지고 있는 스택을 여러 방법으로 구현해보았다.
❗ 동적배열을 사용한 구현 (C)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//동적배열을 사용한 stack 구현
typedef struct _stack {
int* st;
int size;
int top;
}Stack;
void create_stack(Stack* stack) {
stack->top = -1;
stack->size = 1;
stack->st = (int*)malloc(sizeof(int)*1);
} //동적배열 생성, 초기 size = 1
void destroy_stack(Stack* stack) {
free(stack->st);
} //동적할당된 배열의 메모리 해제
void push(Stack* stack, int n) {
if (stack->size == (stack->top)+1) {
stack->size *= 2; //동적배열이 꽉 찼을 때 2배로 realloc
stack->st = (int*)realloc(stack->st, sizeof(int) * (stack->size));
}
stack->top += 1;
stack->st[stack->top] = n;
}
void pop(Stack* stack) {
if (stack->top == -1) {
printf("%d\n",-1);
return;
}
printf("%d\n", stack->st[stack->top--]);
//stack->st[stack->top] 출력 후 따로 stack->top -= 1 해주는 대신, 후위 연산자 사용!
}
void size(Stack* stack) {
printf("%d\n", (stack->top)+1);
}
void empty(Stack* stack) {
if (stack->top == -1) printf("%d\n", 1);
else printf("%d\n", 0);
}
void top(Stack* stack) {
if (stack->top == -1) printf("%d\n", -1);
else printf("%d\n", stack->st[stack->top]);
}
int main() {
Stack stack;
create_stack(&stack); //구조체 생성
int tc,num;
char str[6]; //입력값 받을 문자열
scanf("%d", &tc);
for (int i = 0; i < tc; i++) {
scanf("%s", str);
if (!strcmp(str, "push")) {
scanf("%d", &num);
push(&stack, num);
} //push
else if (!strcmp(str, "pop")) { pop(&stack); } // pop
else if (!strcmp(str, "empty")) { empty(&stack); } // empty
else if (!strcmp(str, "size")) { size(&stack); } // size
else if (!strcmp(str, "top")) { top(&stack); } // top
else { printf("%s", "!Wrong Input!\n"); } // 예외처리
}
destroy_stack(&stack);
return 0;
}
❗ 링크드 리스트를 사용한 구현 (C)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//링크드리스트를 사용한 stack 구현
typedef struct _node {
int data;
struct _node* link;
}Node;
typedef struct _head {
Node* top_node;
int len;
}Head;
Head* create_stack(void) {
Head* head = (Head*)malloc(sizeof(Head));
head->len = 0;
head->top_node = NULL;
return head;
} //head 구조체 생성 및 변수 초기화, head 구조체 포인터 리턴
void* push(Head* head, int dataIn) {
Node* newnode = (Node*)malloc(sizeof(Node));
newnode->data = dataIn;
newnode->link = NULL;
if (head->top_node == NULL) head->top_node = newnode;
else {
Node* temp = head->top_node;
head->top_node = newnode;
newnode->link = temp;
}
head->len += 1;
} //head 구조체의 top_node 포인터를 새로 추가하는 node를 가리키도록 설정
void pop(Head* head) {
if (head->len == 0) printf("%d\n", -1);
else {
printf("%d\n", head->top_node->data);
Node* temp = head->top_node->link;
free(head->top_node);
head->top_node = temp;
head->len -= 1;
}
} //기존의 head->top_node 삭제 후 top_node 포인터 값 수정
void size(Head* head) {
printf("%d\n", head->len);
}
void empty(Head* head) {
if (head->len == 0) printf("%d\n", 1);
else printf("%d\n", 0);
}
void top(Head* head) {
if (head->len == 0) printf("%d\n", -1);
else printf("%d\n", head->top_node->data);
}
void destroy_stack(Head* head) {
Node* temp;
while (head->top_node != NULL) {
temp = head->top_node->link;
free(head->top_node);
head->top_node = temp;
} //Node 구조체 모두 메모리 해제
free(head); //Head 구조체 메모리 해제
}
int main() {
Head* stack_head = create_stack(); //linked list의 head 생성
int tc,num;
char str[6]; //입력값 받을 문자열
scanf("%d", &tc);
for (int i = 0; i < tc; i++) {
scanf("%s", str);
if (!strcmp(str, "push")) {
scanf("%d", &num);
push(stack_head, num);
} //push
else if (!strcmp(str, "pop")) { pop(stack_head); } // pop
else if (!strcmp(str, "empty")) { empty(stack_head); } // empty
else if (!strcmp(str, "size")) { size(stack_head); } // size
else if (!strcmp(str, "top")) { top(stack_head); } // top
else { printf("%s", "!Wrong Input!\n"); } // 예외처리
}
destroy_stack(stack_head); //동적할당 메모리 해제
return 0;
}✔️ C++ STL stack
C++에서는 다양한 자료구조를 직접 구현하지 않고도 사용할 수 있도록 STL (Standard Template Library)를 제공해준다. 스택 역시 STL을 사용하여 간단하게 사용할 수 있다!
- stack.push( ) 데이터의 삽입
- stack.pop( ) 데이터의 삭제
- stack.top( ) 가장 최근의 데이터 반환
- stack.size( ) 스택의 크기 반환
- stack.empty( ) 스택이 비어있는지 확인
❗ STL 사용 (C++)
#include <iostream>
#include <stack>
using namespace std;
int main() {
int tc;
string command;
stack<int> st;
cin >> tc;
for (int i = 0; i < tc; i++) {
cin >> command;
if (command == "push") {
int n;
cin >> n;
st.push(n);
}
else if (command == "pop") {
if (st.size() == 0) cout << -1 << "\n";
else {
cout << st.top() << "\n";
st.pop();
}
}
else if (command == "size") cout << st.size() << "\n";
else if (command == "empty") {
if (st.size() == 0) cout << 1 << "\n";
else cout << 0 << "\n";
}
else if (command == "top") {
if (st.size() == 0) cout << -1 << "\n";
else cout << st.top() << "\n";
}
else cout << "Wrong Input!" << "\n";
}
return 0;
}오늘은 C와 C++을 이용하여 스택을 다양한 방법으로 구현해보았다!
배열과 링크드 리스트를 통해 직접 스택을 구현하다보니 C++의 STL이 새삼 얼마나 편리한지 다시 한 번 느낄 수 있었다 👻 잠시 잊고 살았던 구조체나 포인터, 동적할당도 오랜 만에 연습하니 꽤나 다양한 오류를 만나서 힘들었다...ㅎ 스택을 아주 씹고 뜯고 맛보고 즐긴 흔적...
다음엔 void 포인터를 사용해서도 구현해보면 좋을 것 같다 👍
[이미지 출처] https://www.programiz.com/dsa/stack
Keep At It