2022. 4. 7. 17:56ㆍC
스택이란?
스택은 위 그림과 같이 Data1->2->3->4 순서대로 삽입을 하지만 출력은 4->3->2->1 순으로
한마디로 출력순서가 입력순서의 역순으로 이루어져야 할 경우에 자주 사용되는 자료 구조이다.
이러한 입출력 형태를 후입선출(LIFO : Last-in-First-Out)이라고 한다.
스택에서의 입출력은 스택 상단에서만 일어나며 스택의 중간에서는 데이터를 삭제할 수 없다.
그리고 스택의 바닥부분을 스택 하단이라고 하며 스택 안에 저장되는 것들은 요소라고 한다.
스택에 요소가 하나도 없는 상태를 공백 스택이라고 한다.
이제 몇가지 예제를 통해 자세히 알아보도록 하자.
컴퓨터가 동작할때 수많은 함수의 호출이 이루어지는데, 이 함수들은 실행이 끝나면 자신을 호출한 함수로 되돌아가야 한다. 이럴때 스택이 사용이 되며 이는 곧 복귀할 주소를 기억하는데 스택이 사용된다는 점을 알아야 한다.
그림으로 이를 쉽게 이해할 수 있다.
void fun2() {
return;
}
void fun1() {
fun2();
}
int main(void) {
fun1();
return 0;
}위 코드는 아래 그림과 같이 처리된다.
함수호출에서의 스택 사용은 위와 같은 순서로 활성 레코드가 만들어졌다가 호출이 끝나면 사라지게 된다.
스택의 연산은 어떤것들이 있을까?
두가지가 있는데 먼저 push 연산이다.
push(n)를 통해 비어있는 스택에 n을 삽입한다. 그후 push(a)를 하면 n위에 a가 쌓이게 되는 방식이다.
두번째는 pop연산이다. 파이썬에서 보아 익숙한데 이 pop연산은 가장 위에 쌓여있는 값을 삭제하는 함수이다.
이 두연산의 중요한 점은 스택이 가득찼을때 push 함수를 이용하게 되면 오류가 발생하고
마찬가지로 스택안에 아무것도 없을때 pop 함수를 이용하면 오류가 발생한다는 것이다.
is_empty와 is_full 연산은 스택이 공백인지, 포화상태인지를 검사하는 함수이다.
creat는 스택을 생성, peek은 스택에서 연산의 요소를 삭제하지 않고 보기만 하는 용도로 사용한다.
peek과 pop의 차이점은 peek은 스택 값에 영향을 미치지 않고 단순히 확인용이고 pop은 가장 최근의 요소를 삭제하면서 가져온다는 것이 핵심이다.
배열을 이용해 스택을 구현해보자.
(1)데이터를 스택에 넣는 작업
void push(StackType* s, int value) {
if (is_full(s)) {
printf("Stack is full");
exit(1);
}
s->arr[++(s->top)] = value;
}
(2)데이터를 스택에서 빼는 작업
int pop(StackType* s) {
if (is_empty(s)) {
printf("Stack is empty");
exit(1);
}
return s->arr[(s->top)--];
}
(3)스택이 꽉 차있는지 판단하는 작업
int is_full(StackType* s) {
if (s->top == SIZE - 1)
return 1;
return 0;
}
(4)스택이 비어 있는지 판단하는 작업
int is_empty(StackType *s){
if (s->top == -1)
return 1;
return 0;
}이러한 함수들을 토대로 만들어 보았다.
#include <stdio.h>
#include <stdlib.h>
#define SIZE 100
//StackType이라는 구조체는 int형 100크기의 배열과 top라는 정수형 변수를 가진 구조체
typedef struct StackType {
int arr[SIZE];
int top;
}StackType;
//스택을 만들때마다 초기화를 해주는 함수
void init(StackType* s) {
s->top = -1; //배열은 index의 0부터 시작
//데이터가 하나 있으면 스택배열[0] 두개면 [1] ... 이런 형식
}
//empty : return 1
//!empty : return 0
//스택이 비어있는지 확인한다.
int is_empty(StackType* s) {
if (s->top == -1) //스택이 가리키는 top이 -1일 경우 (비어있을때)
return 1;
return 0;
}
//full : return 1
//!full : return 0
int is_full(StackType* s) {
if (s->top == SIZE - 1) //배열 0부터 시작이니 0~99이므로 SIZE -1
return 1;
return 0;
}
void push(StackType* s, int value) {
if (is_full(s)) { //스택이 꽉 차있으면 안되니 is_full함수로 확인해주고 full일시 종료
printf("Stack is full");
exit(1);
}
printf("\npush : %d\n", value);
s->arr[++(s->top)] = value; //s가 가리키는 arr에[s->top를 먼저 하나 증가시켜놓고] 밸류값을 넣는다.
}
int pop(StackType* s) {
if (is_empty(s)) { //스택이 비어있으면 데이터를 뽑아낼 수 없으니 비어있는지 확인
printf("Stack is empty");
exit(1);
}
return s->arr[(s->top)--]; //s가 가리키는 arr에[s->top을 리턴시켜준 후에] --됨
}
int peek(StackType* s) { //맨 위에 있는 데이터가 어떤 것인지 확인만 하는 함수
if (is_empty(s)) {
printf("Stack is empty");
exit(1);
}
return s->arr[(s->top)];
}
int main(void) {
StackType s;
init(&s); //stack 초기화
push(&s, 3);
push(&s, 2);
push(&s, 1);
printf("peek : %d\n", peek(&s));
printf("pop : %d\n", pop(&s));
printf("pop : %d\n", pop(&s));
printf("pop : %d\n", pop(&s));
printf("pop : %d\n", pop(&s));
}출력 결과
push : 3
push : 2
push : 1
peek : 1
pop : 1
pop : 2
pop : 3
Stack is empty
책의 예제를 풀어보자
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
typedef int element;
element stack[MAX_STACK_SIZE];
int top = -1;
int is_empty() {
return (top == -1);
}
int is_full() {
return (top == (MAX_STACK_SIZE - 1));
}
void push(element item) {
if (is_full()) { //만약 is_full함수가 즉 top == (MAX_STACK_SIZE -1)이 참이라면 스택이 가득 찼다는 것을 알려주는 조건
fprintf(stderr, "스택이 가득 찼습니다.");
return;
}
else stack[++top] = item; //아니라면 stack[top배열 +1]의 값에 item을 넣는다
}
element pop() {
if (is_empty()) { //top == -1 일 경우에는 스택이 비어있다는 것을 알려줌
fprintf(stderr, "스택이 비어있습니다");
exit(1);
}
else return stack[top--]; //그게 아니라면 stack[top]을 출력하고 stack[top-1]을 리턴함
}
element peek() {
if (is_empty()) { //top == -1 일 경우에는 스택이 비어있다는 것을 알려줌
fprintf(stderr, "스택이 비어있습니다");
exit(1);
}
else return stack[top]; //스택의 값을 건드리는 것이 아닌 가장 위에 있는 top을 보기만 하는 함수이다.
}
int main(void) {
push(1);
push(2);
push(3);
printf("%d\n", pop());
printf("%d\n", pop());
printf("%d\n", pop());
}출력 결과
3
2
1진짜 어이 無 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
if문 조건에 is_empty()에서 ()이거 안넣어서 자꾸 이상한 결과 값뜨길래 뭐지? 하고 책 뒤지다가 모르겠어서 형한테 물어보니까
ㅋㅋㅋㅋㅋㅋㅋㅋ아 짜증나 아무튼 책의 예제는 잘못된 것이 없었다.
스택의 요소를 구조체로 하는 방법도 있다
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
#define MAX_STRING 100
typedef struct { //여러가지 변수를 가지고 있는 element 구조체를 선언함
int student_no;
char name[MAX_STACK_SIZE];
char address[MAX_STRING];
}element;
element stack[MAX_STACK_SIZE]; //그 구조체의 배열은 100
int top = -1;
int is_empty() {
return (top == -1);
}
int is_full() {
return (top == MAX_STACK_SIZE - 1);
}
void push(element item) {
if (is_full()) {
fprintf(stderr, "스택이 가득 찼습니다.");
return;
}
else stack[++top] = item;
}
element pop() {
if (is_empty()) {
fprintf(stderr, "스택이 비어 있습니다.");
exit(1);
}
else return stack[top--];
}
int main(void) {
element ie = { //ie라는 구조체의 값들을 입력
20190001,
"Hong",
"Ulsan"
};
element oe; //새로운 oe라는 구조체 선언
push(ie); //ie 구조체의 값을 스택에 넣어주고
oe = pop(); //pop함수로 꺼낸 값을 oe에 넣어준다
printf("%d %s %s", oe.student_no, oe.name, oe.address); //oe의 값들이 잘 들어갔는지 출력을 통해서 확인
return 0;
}출력 결과
20190001 Hong Ulsan예제 풀면 풀수록 점점 이해하고 있는 내 모습이 보여서 뿌듯하다.
하지만 위 두 예제들의 문제점은 전역변수로 stack배열과 top값을 선언하기 때문에 하나의 프로그램에서 여러가지 스택을 동시에 사용하기엔 무리가 있다. 그래서 가장 처음에 그 값들을 하나의 구조체로 묶어 이 구조체의 포인터를 함수로 전달해서 이 포인터를 각 함수의 매개변수로 사용하는 방법이 가장 효율적인것 같다. 포인터 존나 싫어
기본적으로 C언어에서의 함수 매개변수 전달 방식이 call by value이라는 점.
즉 구조체의 복사본이 함수에 전달되기 때문에 원본값에 영향을 줄 순 없다.
원본에 대한 포인터를 전달하여 값을 직접적으로 바꿔주는 call by reference 방식을 이용함으로써 여러가지의 스택을 동시에 만들 수 있다는 장점이 있다.
이를 이용해 문제를 하나 풀어보자
스택을 2개 생성해보자. 첫번째 스택에 1,2,3을 추가하였다가 삭제하여 그대로 두번째 스택에 넣는다.
두번째 스택에서 삭제하여 출력해본다. 데이터의 순서는 어떻게 되는가?#include <stdio.h>
#include <string.h>
#define MAX_STACK_SIZE 100
typedef int element;
typedef struct {
element data[MAX_STACK_SIZE];
int top;
}StackType;
void init_stack(StackType* s) { //스택 초기화
s->top = -1;
}
int is_empty(StackType* s) {
return (s->top == -1);
}
int is_full(StackType* s) {
return (s->top == MAX_STACK_SIZE - 1);
}
void push(StackType* s, element items) {
if (is_full(s)) {
fprintf(stderr, "스택 포화\n");
return;
}
else s->data[++(s->top)] = items;
}
element pop(StackType* s) {
if (is_empty(s)) {
fprintf(stderr, "스택이 비어있음");
exit(1);
}
else return s->data[(s->top)--];
}
element peek(StackType* s) {
if (is_empty(s)) {
fprintf(stderr, "스택이 비어있음");
exit(1);
}
else return s->data[s->top];
}
int main(void) {
StackType fir;
StackType sec;
//구조체 초기화
init_stack(&fir);
init_stack(&sec);
//fir에 1,2,3 순서대로 값 넣기
push(&fir, 1);
push(&fir, 2);
push(&fir, 3);
//sec에 fir에서 3,2,1 순서대로 꺼낸것을 다시 넣어서
push(&sec, pop(&fir));
push(&sec, pop(&fir));
push(&sec, pop(&fir));
//위에서 차례대로 꺼내면 123
printf("%d", pop(&sec));
printf("%d", pop(&sec));
printf("%d", pop(&sec));
return 0;
}출력 결과
123
백준 - 10828번 스택
#include <stdio.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define MINUS -1
#define MAX_SIZE 10000
typedef struct {
int arr[MAX_SIZE];
int top;
}Stack;
void Init(Stack* s) {
s->top = -1;
}
int Empty(Stack* s) {
if (s->top == -1) return TRUE;
return FALSE;
}
int Size(Stack* s) {
return s->top + 1;
}
int Full(Stack* s) {
if (s->top + 1 >= MAX_SIZE) return TRUE;
return FALSE;
}
void push(Stack* s, int data) {
if (Full(s) == TRUE) return;
s->arr[++(s->top)] = data;
}
int pop(Stack* s) {
if (Empty(s) == TRUE) return MINUS;
return s->arr[(s->top)--];
}
int peek(Stack* s) {
if (Empty(s) == TRUE) return MINUS;
return s->arr[s->top];
}
int main(void) {
int i, n, num;
char str[6];
Stack stack;
scanf("%d\n", &n);
Init(&stack);
for (i = 0; i < n; i++) {
scanf("%s", str);
if (strcmp(str, "push")==0) {
scanf("%d", &num);
push(&stack, num);
}
else if (strcmp(str, "pop")==0) {
printf("%d\n", pop(&stack));
}
else if (strcmp(str, "empty")==0) {
printf("%d\n", Empty(&stack));
}
else if (strcmp(str, "size")==0) {
printf("%d\n", Size(&stack));
}
else if (strcmp(str,"top")==0) {
printf("%d\n", peek(&stack));
}
}
return 0;
}string.h 파일에 strcmp함수를 이용하면 간단히 해결될 문제였지만, 그걸 몰랐던 나는 else if(str == "size")로 계속 고민하고 있었다.
strcmp(str,"empty")==0은 str과 "empty"문자열을 서로 비교해 참일 경우 0을 반환한다.
그래서 문자열이 일치할 경우(반환값0) 해당 구문이 실행된다고 정리할 수 있다.
백준 - 10773번 제로
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100000
typedef int element;
typedef struct {
element stack[MAX_STACK_SIZE];
int top;
int size;
}Stack;
void init_stack(Stack* s) {
s->top = -1;
s->size = 0;
}
void push(Stack* s, element item) {
s->stack[++(s->top)] = item;
s->size++;
}
element pop(Stack* s) {
if (s->size == 0) return 0;
s->size--;
return s->stack[(s->top)--];
}
element peek(Stack* s) {
return s->stack[s->top];
}
int main(void) {
int K, num;
int n = 0;
Stack a;
init_stack(&a);
scanf("%d", &K);
for (int i = 0; i < K; i++) {
scanf("%d", &num);
if (num == 0) {
pop(&a);
}
else {
push(&a, num);
}
}
int sum = 0;
for (int j = 0; j < (a.size); j++) {
sum += a.stack[j];
}
printf("%d", sum);
return 0;
}첫번째 for문에서 숫자를 입력받아 0일 경우는 pop을 그 외의 경우는 스택에 그 수를 넣어주며
두번째 for문에서 차례대로 그 수를 더해 최종 결과값을 출력하면 끝날 문제였지만,
두번째 for문에서 많이 헷갈렸다
왜냐하면 나는
int sum = 0;
for (int j = 0; j <= (a.size); j++) {
sum = sum + pop(&a);
}
printf("%d", sum);이렇게 pop을 이용해 꺼낸 값을 더하고 그 외에 반복문도 되게 복잡하게 생각하였는데, 문제는 최종적으로 적어낸 수의 총 합만 출력하면 됐기에 배열(스택)에 저장되어 있는 정수들을 차례대로 더해주기만 하면 될 문제였다.
그 외에는 크게 고민한 부분도 없었고, 전체적인 코드의 틀을 생각하고 짜는 실력이 조금은 늘어난 기분이 들었다.
백준 - 9012번 괄호
코드를 짜기전 미리 틀을 짜보았는데,
스택 a, b를 생성하여
a에는 (를
b에는 )를 담는 스택으로 생각해보자.
반복{
문자열을 입력받는다
해당 문자열의 길이를 담는 변수 len 생성
반복 {
해당 문자열의 길이만큼 반복을 하며
(일 경우 스택 a에 저장
)일 경우 스택 b에 저장
}
반복 {
위의 경우로 스택에 문자열을 저장할 경우 전체길이/2만큼의 높이가 각 스택에 쌓여있을것
고로 peek함수를 통해 a와 b에 각각 (,)이 존재할경우
ab를 pop해준다
}
만약 a나 b의 사이즈가 다를 경우(즉 vps가 아닐 경우){
No 출력
}
그 외의 경우 {
Yes 출력
}
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100000
typedef int element;
typedef struct {
element stack[MAX_STACK_SIZE];
int top;
int size;
}Stack;
void init_stack(Stack* s) {
s->top = -1;
s->size = 0;
}
void push(Stack* s, element item) {
s->stack[++(s->top)] = item;
s->size++;
}
element pop(Stack* s) {
if (s->size == 0) return 0;
s->size--;
return s->stack[(s->top)--];
}
element peek(Stack* s) {
return s->stack[s->top];
}
int main(void) {
int K,n;
char vps[50];
Stack a;
Stack b;
init_stack(&a);
init_stack(&b);
scanf("%d", &K);
for (int i = 0; i < K; i++) {
scanf("%s", vps);
int len = strlen(vps);
for (int z = 0; z < len; z++) {
if (vps[z]== '(') {
push(&a, vps[z]);
}
else if (vps[z]==')') {
push(&b, vps[z]);
}
}
for (int j=0;j<len/2;j++){
if ((peek(&a)=='(') && (peek(&b)== ')')){
pop(&a);
pop(&b);
}
}
if (a.size != 0 || b.size != 0) {
printf("NO\n");
}
else printf("YES\n");
}
return 0;
}힘들었던 점은
위의 코드에서 내가 전혀 고려하지 않았던 반례가 있었다.
바로 ))((같은 경우도 vps로 인식하고 yes를 출력하는 것이었다.
왜냐하면 입력 순서에 상관없이 '('는 a에 ')'는 b에 저장되어 꺼내기 때문에 순서를 인식하지 못한다.
반례를 생각하지 않은 설계였기에 실컷 코드를 다 짜놓고도 빠꾸를 먹는 내 자신을 오늘 되돌아보게 됐다.
또한 이 문제의 경우 '('나 ')'같은 *문자*를 확인하는 것이기에 strcmp를 사용할 필요도 없고 strcmp는 문자열만 지원하기에 잘못된 방법이다.
위에 힘들었던 점을 참고하여 다시 문제를 설계해보자
스택에 '('를 담는다
')'를 만날 경우 pop을 해준다
위의 방법으로 문자열의 입력이 끝났을 때
만약 스택에 '('가 남아있다면
No를 출력하면 될 간단한 문제이다.'C' 카테고리의 다른 글
| C - 자료구조 덱 (0) | 2022.05.18 |
|---|---|
| C - 자료구조 큐 (0) | 2022.05.03 |
| C - 자료구조 3장 연습문제 풀이 (0) | 2022.04.07 |
| C - call by value / call by reference (0) | 2022.04.05 |
| C - 자료구조 배열/구조체/포인터/동적 메모리 할당 (0) | 2022.04.05 |