[c언어로 쉽게 풀어쓴 자료구조] 4장 스택

1. Stack?

• 스택은 컴퓨터 과학에서 사용되는 중요한 자료 구조 중 하나.
• 스택은 데이터를 저장하고 검색하는데 사용되며, 주로 "Last In First Out" (LIFO) 원칙을 따름
• → 가장 최근에 추가된 항목이 가장 먼저 제거

 

2. Stack 구성 요소

• 데이터 요소: 스택에 저장되는 각 항목 또는 데이터 요소
• 맥위(TOP): 스택의 맨 위에 위치한 데이터 요소를 가리키는 포인터

 

3. Stack 기본 동작

• Push : 스택에 데이터를 추가하는 작업. 새로운 항목은 스택의 맨 위에 쌓이게 됨
• Pop : 스택에서 가장 위에 있는 데이터를 제거하는 작업. 스택의 맨 위 항목이 제거 됨
• Peek ( or Top) : 스택의 맨위에 있는 데이터를 확인하지만 제거는 하지 않음
• isEmpty : 스택이 비어있는지 여부를 확인하는 작업

4. Stack 구현을 위한 기본 함수

스택은 1차원 배열을 이용하여 간단한 방법으로 구현이 가능함. 단 1차월 배열을 이용하면 스택의 크기가 고정된다는 단점이 있다.

( 스택의 크기를 가변적으로 구현하려면 연결 리스트를 이용해야함)

is_empty 함수

스택이 비어있는지 검사하는 함수. 스택이 비어있으면, (=top의 값이 -1이면) TRUE(1), 아니면 FALSE(0)을 반환

int is_empty()
	if(top == -1) return 1;
    else return 0;

is_full 함수

스택이 꽉 차있는지 검사하는 함수. 스택이 꽉차있으면, (=top의 값이 MAX-1이면) TRUE(1), 아니면 FALSE(0)을 반환

int is_full()
	if(top == MAX-1) return 1;
    else return 0;

push 함수

스택에 데이터를 삽입. 우선 is_full 함수를 이용하여 먼저 스택이 현재 꽉차있는 상태인지 점검한 후 스택에 데이터를 삽입

스택에서 데이터의 삽입은 항상 맨 위에서마 일어나므로, top 변수를 1 증가 시켜준 후 데이터를 삽입

void push(k)
	if(is_full() == 1)
    	cout << "Overflow";
    else
    	top++;
        stack[top] =k;

 

pop 함수

스택에서 데이터를 삭제. is_enpty 함수를 이용하여 먼저 스택이 현재 비어있는 상태인지 점검한 후 스택의 맨 위에 있는 데이터를 삭제함. 스택에서 데이터의 삭제는 맨위에서만 일어나므로, 현재 top이 가리키는 위치를 데이터를 리턴 후 삭제, Top을 1 감소 시킴

int pop()
	if(is_empty() ==1)
    	cout << "Empty";
    else
    	x=stack[top];
        top--;
        return x;

 

peek 함수

스택의 요소를 리턴하는 함수. pop 연산과 비슷하지만, pop은 맨 위 데이터를 리턴 후 삭제까지 하고, peek은 삭제 없이 데이터를 조회만 한다는 차이점이 있음

int peek()
	if(is_empty() ==1)
    	cout << "Empty!";
    else
    	return stack[top];

 

Stack 구현

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

# define MAX 100
int stack[MAX];
int top = -1;

// stack이 비었는 지 확인
int is_Empty(){
    if (top == -1)
        return 1;
    else
        return 0;
}
// Stack이 꽉 차있는지 검사
int is_full(){
    if (top == (MAX-1)) // 배열이므로 최대 크기는 (지정한 크기 -1)
        return 1;
    else
        return 0;
}
// stack에 데이터 삽입
void push(int k){
    if (is_full() == 1){
        cout << "OverFlow";
    exit(1); // 리턴 없이 함수를 강제 종료
    }
    else{
        top++;
        stack[top] = k;
    }
}

// stack의 맨 위 데이터 변환 후 삭제
int pop(){
    if (is_Empty() == 1){
        cout << "Empty!";
        exit(1); // 리턴값 없이 함수를 강제 종료
    }
    else{
        int x = stack[top];
        top--;
        return x;
    }
}
// stack의 맨위 데이터 출력
int peek(){
    if(is_Empty() == 1){
        cout << "Empty!";
        exit(1); // 리턴값 없이 함수를 강제 종료
    }
    else
        return stack[top];
}
int main() {
	cout << "Is Empty? (Yes: 1 / No : 0) => " << is_Empty() << "\n";
	push(1);	// 1 삽입
	push(2);	// 2 삽입
	push(3);	// 3 삽입
	cout << pop() << "\n";	// 3 반환 후 삭제
	cout << peek() << "\n";	// 2 반환
	cout << pop() << "\n";	// 2 삭제
	cout << "Is Empty? (Yes: 1 / No : 0) => " << is_Empty() << "\n";
	return 0;
}