태그 보관물: 배열

미분류

자료구조 – c언어 배열을 사용한 스택(stack) 구현

댓글 남기기

 스택(Stack)은 후입선출(Last In, First Out) 구조를 가지는 대표적인 자료구조 중 하나입니다. 이 글에서는 C언어로 배열을 사용하여 스택을 구현하는 방법에 대해 자세히 알아보겠습니다.

1. 스택의 기본 이해

 스택은 데이터를 한쪽 끝에서만 넣고 빼는 구조입니다. 이를 후입선출(LIFO: Last In, First Out) 구조라고 합니다.

1-1. 스택의 주요 연산

  • push: 스택에 데이터를 삽입하는 연산입니다.
  • pop: 스택에서 데이터를 제거하는 연산입니다.
  • peek: 스택의 최상단 요소를 확인하는 연산입니다.
  • isEmpty: 스택이 비어있는지 확인하는 연산입니다.
  • isFull: 스택이 가득 찼는지 확인하는 연산입니다.

2. 배열을 사용한 스택 구현

 우리는 배열을 사용하여 스택을 구현할 수 있습니다. 다음 예제 코드에서는 int형 스택을 구현합니다.

#include <stdio.h>
#define MAX 5

int stack[MAX];
int top = -1;

void push(int value) {
    if (top == MAX - 1) {
        printf("스택 오버플로우\n");
        return;
    }
    stack[++top] = value;
}

int pop() {
    if (top == -1) {
        printf("스택 언더플로우\n");
        return -1;
    }
    return stack[top--];
}

int peek() {
    if (top == -1) {
        printf("스택이 비어 있습니다\n");
        return -1;
    }
    return stack[top];
}

int isEmpty() {
    return top == -1;
}

int isFull() {
    return top == MAX - 1;
}

int main() {
    push(10);
    push(20);
    push(30);
    printf("Top 요소: %d\n", peek());
    printf("Pop 요소: %d\n", pop());
    printf("Top 요소: %d\n", peek());
    return 0;
}

3. 메모리 레이아웃 이해

 스택의 메모리 레이아웃은 다음과 같이 생길 수 있습니다.

 메모리 주소   데이터
--------------
 0x7fffd4 | [    ] (빈 자리)
 0x7fffd3 | [    ]
 0x7fffd2 | [ 30 ] < top
 0x7fffd1 | [ 20 ]
 0x7fffd0 | [ 10 ]
--------------

3-1. push 연산 후 메모리 상태

메모리 주소   데이터
--------------
 0x7fffd4 | [    ]
 0x7fffd3 | [ 40 ] < top
 0x7fffd2 | [ 30 ]
 0x7fffd1 | [ 20 ]
 0x7fffd0 | [ 10 ]
--------------

3-2. pop 연산 후 메모리 상태

메모리 주소   데이터
--------------
0x7fffd4 | [    ] 
0x7fffd3 | [    ]
0x7fffd2 | [ 30 ] < top
0x7fffd1 | [ 20 ]
0x7fffd0 | [ 10 ]
--------------

4. 스택의 활용 사례

 스택은 일상에서도 다양한 방식으로 사용됩니다.

4-1. 함수 호출 스택

 프로그래밍 언어에서는 함수 호출을 관리하기 위해 스택을 사용합니다. 함수를 호출할 때마다 스택에 복귀 주소와 매개변수 등이 저장됩니다.

4-2. 브라우저 뒤로 가기 기능

 웹 브라우저에서는 방문한 웹 페이지를 스택에 저장해두고, 뒤로 가기 버튼을 누르면 가장 마지막에 저장된 페이지로 돌아갑니다.

5. 스택과 배열의 차이점

 배열은 정적이지만 스택은 동적으로 요소를 추가하거나 제거할 수 있다는 점에서 차이가 있습니다.

5-1. 배열의 특성

  • 미리 할당된 크기만큼 저장할 수 있습니다.
  • 임의 접근이 가능합니다.

5-2. 스택의 특성

  • 동적으로 요소를 추가하거나 제거할 수 있습니다.
  • 특정 순서(LIFO)를 따릅니다.
구분 배열 스택
접근 방식 임의 접근 LIFO
크기 미리 정해짐 동적 조정 가능