Stack(C언어)

Stack

 Stack은 데이터를 담는 자료구조로, 데이터를 역순으로 저장할 수 있는 자료구조이다. Stack은 나중에 받은 데이터를 제일 처음(Top)에 저장하고, 마지막으로 받은 데이터부터 반환하는 Last In First Out(LIFO) 구조이다.

 

 Stack은 다음과 같은 기본적인 연산을 가진다.

1. push() - Stack에 데이터를 넣는다

2. pop() - Stack의 Top에 있는 데이터를 제거, 반환한다

3. peek() - Stack의 Top에 있는 데이터를 제거하지 않고 반환한다

4. isEmpty() - Stack이 비어있는지 여부를 반환한다

5. size() - Stack의 크기를 반환한다

 

상황에 따라 추가적인 연산을 구현할 수 있다.

 

 

 그림을 통해 Stack을 이해해 보자.

 

 비어 있는 Stack이다.

 

 

push 연산

 Stack에 push를 하면 Stack의 가장 위로 데이터가 들어가고, Top은 그 데이터를 가리키게 된다. 

 

 

 

pop 연산

Stack에 pop을 하면 Stack의 가장 위(Top)에 있는 데이터를 제거하고 반환한다.

 

 

 

peek 연산

 Stack을 peek 하면 Stack의 가장 위(Top)에 있는 데이터를 제거하지 않고 반환한다.

 

 

 

isEmpty 연산

 isEmpty 연산은 Stack이 비어있는지 체크한 후, 비어있으면 true, 비어있지 않으면 false를 반환한다.

 

 

 

size 연산

 size 연산은 Stack의 크기(들어있는 데이터의 개수)를 반환한다.

 

 

 

 

구현

Stack을 LinkedList를 사용해 구현해 보자. 

 

 

Stack 선언

struct Stack {
	LinkedList *top;//Stack의 top를 저장하는 Linked List	
	int size;//Stack의 크기
}typedef Stack;

 Stack은 멤버 변수로 top, size를 가질 수 있다. LinkedList* top은 stack에 저장된 데이터들의 top의 주소를 가진다. 가장 마지막에 추가된 데이터를 가지고 있을 테니 그림으로 보면 다음과 같다.

 

 

push

/*
* Description: Stack에 값을 추가(push)하는 함수
* 
* Parameter:
* stack: Stack 포인터
* data: Stack에 추가할 데이터
* 
* Return: 
* 성공 시 1, 실패 시 0
*/
int push(Stack* stack, int data) {
	//Stack의 top에 새로운 Linked List를 추가해야 함
	//newLinkedList->stack의 top
	LinkedList* newLinkedList = (LinkedList*)malloc(sizeof(LinkedList));
	newLinkedList->data = data;

	//이렇게 하면 newLinkedList->stack의 top이 됨
	newLinkedList->next = stack->top;
	stack->top = newLinkedList;
	(stack->size)++;
	return 1;
}

 매개변수로 받은 데이터를 담는 newLinkedList를 만들고, newLinkedList의 next가 top을 가리키게 한다. 그리고 나서 stack의 top을 newLinkedList로 만들어주면 된다. 

 

 

pop

/*
* Description: Stack에서 값을 반환(pop)하는 함수
* 
* Parameter:
* stack: Stack 포인터
* 
* Return:
* 성공 시 반환할 데이터, 실패 시 0(stack에 top에 -1이 있을 수 있으니 이렇게 하면 안되지만, 이해를 위해 -1 반환)
* */
int pop(Stack* stack) {
	//stack이 비어있는지 체크
	if (stack->top == NULL) {
		return 0;
	}
	//stack의 top에 있는 데이터를 반환
	//free를 위해 stack의 top을 임시로 저장
	LinkedList* temp = stack->top;
	int dataInTop = temp->data;
	//stack의 top에 있는 데이터를 반환하기 전에 stack의 top을 top의 next로 바꿔줌
	stack->top = stack->top->next;
	//temp(stack의 원래 top)는 더 이상 필요 없으므로 free
	free(temp);
	(stack->size)--;
	return dataInTop;
}

 Stack의 top을 top의 next로 바꿔준 후, 기존 top을 free 하고, 기존 top에 있던 데이터를 반환할 것이다. 이를 구현하기 위해서는 다음과 같은 순서를 따라야 한다.

1. Stack의 top을 임시로 저장하는 temp를 만든다.

2. return 할 데이터를 저장할 변수를 만들고 temp->data(top의 데이터)를 넣어준다.

3. Stack의 top을 top의 next로 바꿔준다.

4. temp를 free 시킨다.

5. 2에서 저장한 변수를 return 한다.

 

 temp를 사용해 Stack의 top을 임시 저장하고 return 할 데이터를 저장하는 변수를 만드는 이유는 Stack의 top을 top의 next로 바꿔주면 기존 top의 주소를 잃어버려 free 할 수 없고, 이에 따라 기존 top에 있던 데이터에도 접근할 수 없기 때문이다.

 

 

 

peek

/*
* Description: Stack의 top을 pop 하지 않고 반환하는 함수
* 
* Parameter:
* stack: Stack 포인터
* 
* Return:
* 성공 시 반환할 데이터, 실패 시 -1(stack에 top에 -1이 있을 수 있으니 이렇게 하면 안되지만, 이해를 위해 -1 반환)
*/
int peek(Stack* stack) {
	//stack이 비어있으면 -1 반환
	if (stack->top == NULL) {
		return -1;
	}
	//그게 아니라면 stack의 top에 있는 데이터를 반환
	return stack->top->data;
}

 peek는 정말 쉽다. 그냥 top에 있는 데이터를 반환하기만 하면 된다. 

 

 

 

 

isEmpty

/*
* Description: Stack이 비어있는지 확인하는 함수
*
* Parameter:
* stack: Stack 포인터
*
* Return:
* 비어있으면 1(true), 비어있지 않으면 0(false)
* */
int isEmpty(Stack* stack) {
	//stack의 top이 NULL이면 비어있는 것
	if (stack->top == NULL) {
		return 1;
	}
	return 0;
}

 isEmpty도 마찬가지로 쉽다. Stack의 top이 비어있지 않으면 0, 비어있다면 1을 반환하면 된다.

 

 

 

size

/*
* Description: Stack의 크기를 반환하는 함수
*
* Parameter:
* stack: Stack 포인터
*
* Return:
* Stack의 크기
*/
int size(Stack* stack) {
	return stack->size;
}

 위에서 push, pop을 구현할 때 Stack의 size를 증가, 감소시켰으므로, LinkedList 크기 연산을 할 필요 없이 Stack의 size를 반환하면 된다. 

 

 

 

 

 

 

 

 

 Stack은 함수 호출 및 재귀 함수 호출, 메모리 관리, 웹에서의 뒤로 가기 기능 등 다양한 곳에서 사용된다. 데이터 구조의 기초를 이해하는 데 중요한 요소이며, 프로그래밍과 알고리즘에서 자주 활용된다. Stack에 대한 개념을 잘 이해하고 적절하게 활용한다면, 코드의 효율성, 문제 해결 능력을 향상시킬 수 있다.

 

 

 

 

 

 

 

 

 

 

과제

Stack1.cpp

0.00MB

Stack2.cpp

0.00MB