스택 Stack

---

LIFO - Last-In, First-Out

---

한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료구조 중 하나

가장 나중에 들어간 것이 가장 먼저 나온다. (후입선출)

LIFO - Last-In, First-Out

---

스택(Stack)의 관련 연산함수(ADT)

 * ADT : 추상 자료형(Abstract Data Type), 컴퓨터 과학에서 자료들과 그 자료들에 대한 연산들을 명기한 것

1. SInit()

   - 스택의 초기화

   - 스택 생성 후 가장 먼저 호출해야 한다.

2.  SPush(data)

 -  스택에 데이터를 넣어 저장한다.

   -  매개변수 data로 전달된 값을 요소로 저장

   -  스택의 가장 윗 요소(top)가 가리키는 자리 위(top + 1)에 메모리를 생성해 data를 넣는다.

3.  SPop()

   -  스택의 가장 윗 요소(top)를 삭제한다. 

   -  삭제된 데이터(top)은 반환(출력)된다.

   -  스택이 비었다면 연산 정의불가 상태

4.  STop()

   - 스택의 가장 윗 요소(top)를 반환(출력) 만 한다. (삭제 x)

   - 스택이 비었다면 연산 정의 불가 상태

5. SIsEmpty()

   - empty 여부를 확인한다.

   - 스택이 빈 경우 True(1)를 반환

   - 그렇지 않은 경우 False(0)를 반환

 

 

 

---

스택(Stack)은 1.배열 과 2.연결리스트 두가지 방법을 기반으로 구현할 수 있다.

하나의 자료구조를 사용해 다른 자료구조의 구현에 사용될 수 있다. 

'배열' 또한 하나의 자료구조인데 '리스트'의 구현 도구로 쓰였듯이, '배열' 과 '연결리스트'도 '스택'자료구조를 만드는데 사용된다.

---

1. 스택(Stack)의 '배열' 기반 구현

배열의 index가 부여되어있고,

index = 0 이 스택의 바닥으로 생각한다. 

스택(stack)의 가장 나중에 들어간 자료가 가장 먼저 나오기 위해 (LIFO) 

마지막에 저장된 데이터의 위치(top)을 기억해야한다. 

* 스택이 비어있을 때는 top = -1 로 설정한다.

* 데이터를 하나씩 넣을 때마다 top ++ 로 마지막 데이터 위치를 기억한다.

 

Push	1. top_index 를 +1 하고, 2. 해당 top_index에 data를 넣는다
Pop	1. top_index 가 가리키는 data를 삭제하고, 2. 해당 top_index를 -1 한다.

 

하나의 .c 파일에 stack을 구조체로 구현하고,  

가장 간단한 방식으로 다섯개의 ADT를 구현해

main 함수로 동작까지 확인해보았다. 

/*
	file name: Stack_ArrayBase.c
    배열 기반의 스택 구현
*/

#include<stdio.h>
#include<stdlib.h>					// exit(-1) 사용 위해 필요 ! 


// Stack 배열 기반!! 
struct Stack {
	int stack_arr[100];
	int top_index;
};
Stack stack;

// 스택 초기화 
void init() {
	stack.top_index = -1;
}
// IsEmpty
int isempty() {
	if (stack.top_index == -1)
		return 1;
	else
		return 0;

}
// Push
void push(int data) {
	stack.top_index++;
	stack.stack_arr[stack.top_index] = data;
}
// Top
int top() {
	if (isempty() == 1) {
		printf("stack 이 비었음");
		exit(-1);
	}
	return stack.stack_arr[stack.top_index];
}
// Pop
int pop(){
	if (isempty() == 1) {
		printf("stack 이 비었음");
		exit(-1);
	}
	int val = stack.stack_arr[stack.top_index];
	stack.top_index--;
	return val;
}


// 동작확인 
int main() {
	init();
	push(1);
	push(2);
	push(3);
	printf("%d ", pop());
	printf("%d ", pop());
	printf("%d ", pop());

	return 0;
}

 

'더보기'를 클릭하면, 

헤더파일, class 파일로 구분해 구현해 놓은 코드를 확인할 수 있다. 

---

'윤성우의 열혈 자료구조'의 Chapter 06 스택(Stack)을 참고한 구현코드이다. 
사용할 ADT함수를 미리 선언하고 type을 지정하는 헤더파일 'ArrayBaseStack.h' ,
이 헤더파일에서 선언만 한 ADT함수의 기능을 구현한 class파일 'ArrayBaseStack.c',
헤더파일을 포함해 구현한 함수 동작을 확인하는 용도의 main파일 'ArrayBaseStackMain.c'   
세 파일로 구성되어, 세 파일을 한 디렉토리에 작성 후 Main.c 파일로 구현동작을 확인한다.

 

1. ArrayBaseStack.h

/*
	file name : ArrayBaseStack.h 
	Stack - 배열기반 구현 _ 헤더파일 .h
*/
#pragma once
#ifndef __AB_STACK_H__
#define __AB_STACK_H__

#define TRUE 1
#define FALSE 0
#define STACK_LEN 100

// Data 라는 자료형 지정 
typedef int Data;			

// 스택 (구조체) = '해당 스택의 배열' + top index 
typedef struct _arrayStack {
	Data stackArr[STACK_LEN];	// int stackArr[100]  와 동치, 배열 선언
	int topIndex;				
} ArrayStack;

// Stack : 위에서 설정한 스택 구조체를 자료형으로 재선언 
typedef ArrayStack Stack;

// 함수를 (헤더파일에) 미리 선언        // 모두 포인터 매개변수 사용
void SInit(Stack* pstack);				// (자료형 * 매개변수이름)
int SIsEmpty(Stack* pstack);
void SPush(Stack* pstack, Data data);
Data SPop(Stack* pstack);
Data STop(Stack* pstack);

#endif

 

2. ArrayBaseStack.c

/*
	file name : ArrayBaseStack.c
	Stack - 배열기반 구현 _ 헤더파일의 class구현 모음 .c
*/
#include <stdio.h>
#include <stdlib.h>
#include "ArrayBaseStack.h"

void SInit(Stack* pstack) {
	pstack->topIndex = -1;		// 구조체인 pstack의 topIndex요소에 포인터 접근
}								// 그럼 기존의 메모리는 어떻게 삭제함????

int SIsEmpty(Stack* pstack) {
	if (pstack->topIndex == -1)
		return TRUE;
	else
		return FALSE;
}

void SPush(Stack* pstack, Data data) {
	pstack->topIndex += 1;
	pstack->stackArr[pstack->topIndex] = data;
}

Data SPop(Stack* pstack) {
	int rIdx;
	// 비어있다면,
	if (SIsEmpty(pstack)) {
		printf("Stack Memory Error!");
		exit(-1);			// exit => 프로그램 강제 종료
	}
	// 안 비어있다면, 
	rIdx = pstack->topIndex;	// 스택의 top을 가져옴
	pstack->topIndex -= 1;		// top 번호 하나 내리기

	return pstack->stackArr[rIdx];	// 배열의 topIndex접근해 반환
}

Data STop(Stack* pstack) {
	// 비어있다면,
	if (SIsEmpty(pstack)) {
		printf("Stack Memory Error!");
		exit(-1);
	}
	// 안 비어있다면,
	return pstack->stackArr[pstack->topIndex];
}

 

3. ArrayBaseStackMain.c

/*
	file name : ArrayBaseStackMain.c
	Stack - 배열기반 구현 _ 구현 동작 확인용 main파일 .c
*/
#include <stdio.h>
#include "ArrayBaseStack.h"		// 직접만든 헤더파일

int main(void) {
	
	// stack의 생성, 초기화
	Stack stack;
	SInit(&stack);					// 포인터 매개변수 전달 

	// 데이터 넣기	
	SPush(&stack, 1);				
	SPush(&stack, 2);
	SPush(&stack, 3);
	SPush(&stack, 4);
	SPush(&stack, 5);

	
	// 데이터 꺼내기
	while (!SIsEmpty(&stack))			// 스택이 empty가 아닌동안,
		printf("%d ", SPop(&stack));	// 위에서 부터 꺼내보기
	
	return 0;
}

---

2. 스택(Stack)의 '연결 리스트' 기반 구현

단순 연결 리스트 인지, 스택인지는 메모리 구조가 같아 구분할 수 없다.

단, 이 메모리 구조를 바탕으로 push, pop 연산을 구현한다면 스택이 된다. 

 

Push	1. 새 노드를 생성한다. 2. 만든 노드 안에 값넣고, 3. 만든 노드를 연결하고,  4. 헤드가 새 노드를 가리키도록 한다.
Pop	1. 헤드가 가리키는 값을 따로 저장한다. 2. 헤드가 가리키는 노드주소도 따로 저장한다. 3. 헤드가 '삭제될 노드'의 이전 노드를 가리키도록 한다. 4. '2'에서 저장한 노드 삭제(free) 5. '1'에서 저장한 값 return

 

하나의 .c 파일에 연결리스트의 node를 구조체로 구현하고, 

가장 간단한 방식으로 다섯개의 ADT를 구현해

main 함수로 동작까지 확인해보았다. 

 

/*
	file name: Stack_ListBase.c
    연결리스트 기반의 스택 구현
*/

#include<stdio.h>
#include<stdlib.h>					// exit(-1) 사용 위해 필요 ! 


// 연결리스트 먼저 구현
struct node {
	int data;
	struct node * next;
};
// 연결리스트 사용 스택 구현
struct Stack {
	node * head;
 };

Stack stack;
///////////////////////////////////////////////////////////////////
// ADT 구현
void init() {
	stack.head = NULL;
}
int isempty() {
	if (stack.head == NULL)
		return 1;
	else
		return 0;
}
int top() {
	if (isempty()) {
		printf("stack 이 비어있음");
		exit(-1);
	}
	return (stack.head)->data;
}
void push(int data) {
	// 1. 노드부터 생성
	node* newnode = (node*)malloc(sizeof(node));
	// 2. 노드 안에 값넣기 
	newnode->data = data;
	// 3. 링크 연결하기
	newnode->next = stack.head;
	// 4. 헤드가 새 노드를 가리킴
	stack.head = newnode;
}
int pop() {
	if (isempty()) {
		printf("stack 이 비어있음");
		exit(-1);
	}
	// 1. 가리키는 값 먼저 저장
	int value = (stack.head)->data;
	// 2. 가리키는 노드주소도 저장
	node* rnode = stack.head;
	// 3. head를 한 칸 옮기기
	stack.head = (stack.head)->next;
	// 4. 원래 가리키던 노드 삭제 
	free(rnode);
	return value;
}
int main() {
	init();
	push(1);
	push(2);
	push(3);
	printf("%d ", pop());
	printf("%d ", pop());
	printf("%d ", pop());

	return 0;
}

 

 

'더보기'를 클릭하면,

헤더파일, class 파일로 구분해 구현해 놓은 코드를 확인할 수 있다. 

---

'윤성우의 열혈 자료구조'의 Chapter 06 스택(Stack)을 참고한 구현코드이다. 
사용할 ADT함수를 미리 선언하고 type을 지정하는 헤더파일 'ListBaseStack.h' ,
이 헤더파일에서 선언만 한 ADT함수의 기능을 구현한 class파일 'ListBaseStack.c',
헤더파일을 포함해 구현한 함수 동작을 확인하는 용도의 main파일 'ListBaseStackMain.c'   
세 파일로 구성되어, 세 파일을 한 디렉토리에 작성 후 Main.c 파일로 구현동작을 확인한다.

 

1. ListBaseStack.h

/*
	file name : ListBaseStack.h 
	Stack - 연결리스트기반 구현 _ 헤더파일 .h
*/

#pragma once
#ifndef __AB_STACK_H__
#define __AB_STACK_H__

#define TRUE 1
#define FALSE 0
// 연결리스트 기반 스택은 길이를 미리 한정지을 필요가 없음!!

// Data 라는 자료형 지정 
typedef int Data;			

// 연결리스트 node 구현
typedef struct _node {
	Data data;
	struct _node* next;
} Node;

// node로 이루어진 스택 
typedef struct _listStack {
	Node* head;					// head 만 필요
} ListStack;

// Stack : 위에서 설정한 스택 구조체를 자료형으로 재선언 
typedef ListStack Stack;

// 함수를 (헤더파일에) 미리 선언        // 모두 포인터 매개변수 사용
void SInit(Stack* pstack);				// (자료형 * 매개변수이름)
int SIsEmpty(Stack* pstack);
void SPush(Stack* pstack, Data data);
Data SPop(Stack* pstack);
Data STop(Stack* pstack);

#endif

 

2. ListBaseStack.c

/*
	file name : ListBaseStack.c
	Stack - 연결리스트기반 구현 _ 헤더파일의 class구현 모음 .c
*/
#include <stdio.h>
#include <stdlib.h>
#include "ListBaseStack.h"

// head가 가리키는 것이 곧 top 
// 연결리스트의 head에 새 노드를 추가함.

void SInit(Stack* pstack) {
	pstack->head = NULL;		// 비어있는 상태 	
}								

int SIsEmpty(Stack* pstack) {
	if (pstack->head == NULL)
		return TRUE;
	else
		return FALSE;
}

void SPush(Stack* pstack, Data data) {
	// 새 노드 생성
	Node* newNode = (Node*)malloc(sizeof(Node));	// 메모리 공간 마련
	// 새 노드에 데이터 저장&연결
	newNode->data = data;
	newNode->next = pstack->head;
	// head가 새 노드를 가리킴
	pstack->head = newNode;
}

Data SPop(Stack* pstack) {
	Data rdata;
	Node* rnode;

	// 비어있다면,
	if (SIsEmpty(pstack)) {
		printf("Stack Memory Error!");
		exit(-1);			// exit => 프로그램 강제 종료
	}
	// 안 비어있다면, 
	rdata = pstack->head->data;		// 삭제할 노드의 데이터
	rnode = pstack->head;			// 삭제할 노드의 주소값

	pstack->head = pstack->head->next;
	free(rnode);					// 노드 삭제 
	return rdata;	// 배열의 topIndex접근해 반환
}

Data STop(Stack* pstack) {
	// 비어있다면,
	if (SIsEmpty(pstack)) {
		printf("Stack Memory Error!");
		exit(-1);
	}
	// 안 비어있다면,
	return pstack->head->data;
}

 

3. ListBaseStackMain.c

/*
	file name : ListBaseStackMain.c
	Stack - 연결리스트기반 구현 _ 구현 동작 확인용 main파일 .c
*/
#include <stdio.h>
#include "ListBaseStack.h"		// 직접만든 헤더파일

int main(void) {
	
	// stack의 생성, 초기화
	Stack stack;
	SInit(&stack);					// 포인터 매개변수 전달 

	// 데이터 넣기	
	SPush(&stack, 1);				
	SPush(&stack, 2);
	SPush(&stack, 3);
	SPush(&stack, 4);
	SPush(&stack, 5);

	
	// 데이터 꺼내기
	while (!SIsEmpty(&stack))			// 스택이 empty가 아닌동안,
		printf("%d ", SPop(&stack));	// 위에서 부터 꺼내보기
	
	return 0;
}