자료구조)Stack구조-C

Stack 구조란?

Stack은 제한적으로 접근할 수 있는 나열 구조로 접근방법은 언제나  목록의 맨 끝에서만 일어납니다

참조 스택 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

스택 - 위키백과, 우리 모두의 백과사전

 

주요 특징으로는 스택의 마지막에서만 자료를 넣거나 뺄 수 있으며 LIFO(Last In First Out) 구조로 되어있습니다

자료를 넣을 때는 PUSH라 하며 빼낼 때는 POP이라고합니다

 

Stack 구조

정리해보면 Stack 특징은

• LIFO구조
• PUSH, POP을 통해 데이터를 넣고 뺄 수 있다

 

Stack을 구현하려면

• Stack를 표현할 배열
• PUSH, POP함수
• 가장 위에 있는 데이터를 표시할 포인터가 필요합니다
• FULL상태인지 EMPTY상태인지 확일할 함수가 필요합니다(각각 따로 만들 겁니다)

 

이번에는 C로 구현해보겠습니다 전체 코드는

#include<stdio.h>
#include <stdbool.h> //bool 타입을 쓰기위한 라이브러리

#define stack_size 5

int stack[stack_size];
int top_pointer = -1; //index -1

void push(int data);
void pop(void);

bool empty_check();
bool full_check();





int main() {

	push(1);
	push(2);
	push(3);
	push(4);
	push(5);
	push(6); //over flow

	printf("--------stack print--------\n");

	pop();
	pop();
	pop();
	pop();
	pop();
	pop();




	return 0;
}


bool empty_check() {
	if (top_pointer < 0) return true;
	else return false;
}

bool full_check() {
	if (top_pointer >= stack_size - 1) return true;
	else return false;
}

void push(int data) {
	if (full_check() == true) printf("max\n");
	else stack[++top_pointer] = data;
}

void pop() {
	if (empty_check() == true) printf("end of stack \n");
	else printf("%d \n", stack[top_pointer--]);
}

코드를 분석해봅시다

 

#include<stdio.h>
#include <stdbool.h> //bool 타입을 쓰기위한 라이브러리

#define stack_size 5

int stack[stack_size];
int top_pointer = -1; //index -1

위 코드대로 만들게 되면 int형 배열을 위와 같이 생성하고 top_pointer는 -1(임의로 설정)이라 다른 곳을 가리킬 겁니다 

 

 

PUSH 함수

PUSH

함수는 Stack 데이터를 넣을 때 사용합니다

void push(int data) {
	if (full_check() == true) printf("max\n");
	else stack[++top_pointer] = data;
}

push를 하게 되면 Stack 꽉 찼는지 비교하게 되고 아니라면 전위 연산자를 통해 top_pointer를 증가시키고 데이터를 집어넣게 됩니다 만약 꽉 찼으면 max를 표시하고 바로 해당 함수를 탈출합니다

 

POP 함수 

POP 함수는 Stack에서 데이터를 꺼낼 때 사용합니다

void pop() {
	if (empty_check() == true) printf("end of stack \n");
	else printf("%d \n", stack[top_pointer--]);
}

pop을 사용하게 되면 비어있는지 확인하고 안 비어있으면 이번에 값을 빼내고 후위 연산을 통해 pointer를 줄입니다   만약 Stack 내부가 텅 비어있으면 "end of stack"를 출력하고 함수를 탈출하게 됩니다

 

 

empty_check/full_check 함수

 

empty_check:스택이 비어져있는지 확인합니다

full_check :스택이 꽉 차 있는지 확인합니다

 

bool empty_check() {
	if (top_pointer < 0) return true;
	else return false;
}

bool full_check() {
	if (top_pointer >= stack_size - 1) return true;
	else return false;
}

간단합니다 top_pointer를 통해  배열의 범위를 넘어가는지 아닌지를 보고 비어있는지 꽉 찼는지  True / False로 반환합니다