🎈목차
1. 스택(stack) 자료구조의 이해
2. array stack 구현
3. list를 이용한 stack 구현
4. 느낌점
🎆1-(1) 스택(stack)자료구조의 이해
* 스택은 자료를 차곡차곡 쌓아 올린 자료구조
* 자료의 입력과 출력은 한쪽 방향에서만 이루어짐
* 후입 선출 구조(LIFO : :Last Input First Output)
* 배열로 구현하거나 연결리스트로 구현 할 수 있음.
1-(2)
기본 용어 정리
- size : 스택의 공간 크기
- push : 스택에 데이터를 넣는 작업
- pop : 스택에서 데이터를 꺼내는 작업
- top : 스택에서 입출력할 데이터의 위치
스택의 주요 기능
1. 스택 생성하기
2. 스택이 꽉 차있는지 검사
3. 스택이 완전히 비어있는지 검사
4. 스택 상단에 데이터 추가하기
5. 스택 상단에서 데이터 꺼내오기
6. 스택 내의 모든 데이터 출력하기
7. 스택 소멸하기
🎇2. array stack 구현하기
(1) 생성
#pragma once
enum BOOL { FALSE, TRUE };
typedef struct _stack {
int *stack; /* stack으로 사용되는 동적할당 배열을 가리키는 포인터 변수 */
int size; /* 스택의 크기(size) */
int top; /* 스택의 입,출구 위치정보 저장 */
}Stack;
(2) 스택 기능 함수 목록
BOOL createStack(Stack *, int); /* 스택 메모리 할당 및 멤버 초기화 함수 */
BOOL isStackFull(Stack *sPtr); /* 스택이 꽉 차있는지 검사 */
BOOL isStackEmpty(Stack *sPtr); /* 스택이 완전히 비어있는가 검사 */
BOOL push(Stack *, int); /* 스택에 데이터 저장하는 함수 */
BOOL pop(Stack *, int *); /* 스택에서 데이터를 꺼내는 함수 */
void printStack(const Stack*); /* 스택 내의 모든 데이터를 출력하는 함수 */
void destroyStack(Stack *); /* 스택 메모리 해제 함수 */
(3) 스택 기능 함수 구현하기
arrayStack.h [1]
//#pragma once
//enum BOOL { FALSE, TRUE };
//
//typedef struct _stack {
// int *stack; /* stack으로 사용되는 동적할당 배열을 가리키는 포인터 변수 */
// int size; /* 스택의 크기(size) */
// int top; /* 스택의 입,출구 위치정보 저장 */
//}Stack;
//
//BOOL createStack(Stack *, int); /* 스택 메모리 할당 및 멤버 초기화 함수 */
//BOOL isStackFull(Stack *sPtr); /* 스택이 꽉 차있는지 검사 */
//BOOL isStackEmpty(Stack *sPtr); /* 스택이 완전히 비어있는가 검사 */
//BOOL push(Stack *, int); /* 스택에 데이터 저장하는 함수 */
//BOOL pop(Stack *, int *); /* 스택에서 데이터를 꺼내는 함수 */
//void printStack(const Stack*); /* 스택 내의 모든 데이터를 출력하는 함수 */
//void destroyStack(Stack *); /* 스택 메모리 해제 함수 */
arrayStack.cpp [2]
#include "14~15강 arrayStack .h "
#include <stdio.h>
#include <malloc.h>
/*----------------------------------------------------------------------------------
Function name : createStack - 지정된 크기의 스택을 생성하는 함수
Parameters : sp - 스택관리 구조체의 주소
size - 스택의 크기
Returns : 성공 - TRUE / 실패 - FALSE
----------------------------------------------------------------------------------*/
BOOL createStack(Stack *sp, int size)
{
if (sp == NULL) {//sp 포인터 NULL check
return FALSE;
}
sp->stack = (int*)calloc(size, sizeof(int)); //stack 포인터 할당
if (sp->stack != NULL) { //stack 메모리 할당 성공 시
sp->size = size; //스택 size 초기화
sp->top = 0; //top 0으로 초기화
return TRUE;
}
else { // stack 메모리 할당 실패 시
return FALSE;
}
}
/*-----------------------------------------------------------------------------------
Function name : isStackFull - 스택이 꽉 차있는지 검사
Parameters : sp - 스택관리 구조체의 주소
Returns : 스택이 꽉 차있으면 TRUE, 아니면 FALSE 리턴
-----------------------------------------------------------------------------------*/
BOOL isStackFull(Stack *sp)
{
if (sp == NULL) { //sp 포인터 NULL check
return FALSE;
}
if (sp->size == sp->top) { //stack이 꽉 차였으면
return TRUE;
}
else {
return FALSE;
}
}
/*-----------------------------------------------------------------------------------
Function name : isStackEmpty - 스택이 완전히 비어있는지 검사
Parameters : sp - 스택관리 구조체의 주소
Returns : 스택이 완전히 비어있으면 TRUE, 아니면 FALSE 리턴
-----------------------------------------------------------------------------------*/
BOOL isStackEmpty(Stack *sp)
{
if (sp == NULL) {//sp 포인터 NULL check
return FALSE;
}
if (sp->top == 0) { // stack이 비어 있으면
return TRUE;
}
else {
return FALSE;
}
}
/*--------------------------------------------------------------------------------------
Function name : push - 스택에 데이터 하나를 저장함
Parameters : sp - 스택관리 구조체의 주소
inData - 스택에 저장할 데이터
Returns : 성공적으로 저장하면 TRUE, 실패하면 FALSE 리턴
--------------------------------------------------------------------------------------*/
BOOL push(Stack *sp, int inData)
{
if (sp == NULL) {//sp 포인터 NULL check
return FALSE;
}
if (isStackFull(sp)){//stack이 다 차있으면
return FALSE;
}
else { //데이터를 top 위치에 저장한 후 top를 증가시킴
sp->stack[sp->top] = inData;
sp->top++;
return TRUE;
}
}
/*--------------------------------------------------------------------------------------
Function name : pop - 스택에서 데이터 하나를 꺼냄
Parameters : sp - 스택관리 구조체의 주소
popData - 꺼낸 데이터를 저장할 기억공간의 주소
Returns : 성공적으로 꺼내면 TRUE, 실패하면 FALSE 리턴
--------------------------------------------------------------------------------------*/
BOOL pop(Stack * sp, int *popData)
{
if (sp == NULL) {//sp 포인터 NULL check
return FALSE;
}
if (isStackEmpty(sp)) {//stack이 비어있으면
return FALSE;
}
else { //데이터를 top번 위치에서 꺼내 popData가 가리키는 곳에 저장함
--sp->top;
*popData = sp->stack[sp->top];
return TRUE;
}
}
/*--------------------------------------------------------------------------------------
Function name : printStack - 스택의 모든 데이터 출력(pop하면 나오는 순서대로 출력)
Parameters : sp - 스택관리 구조체의 주소
Returns : 없음
--------------------------------------------------------------------------------------*/
void printStack(const Stack* sp)
{
int i = sp->top;
if (sp == NULL) {//sp포인터 NULL check
return;
}
while (i != 0) {
printf("%5d\n", sp->stack[--i]);
}
printf("\n");
}
/*--------------------------------------------------------------------------------------
Function name : destroyStack - 스택 소멸 함수
Parameters : sp - 스택관리 구조체의 주소
Returns : 없음
--------------------------------------------------------------------------------------*/
void destroyStack(Stack *sp)
{
if (sp == NULL) { //SP 포인터 NULL check
return;
}
if (sp->stack != NULL) {//stack으로 사용되는 배열 메모리 해제
free(sp->stack);
}
sp->stack = NULL;//stack 멤버를 NULL poniter로 초기화
sp->size = 0; //size top 맴버를 0으로 초기화
sp->top = 0;
}
main.cpp [3]
#define _CRT_SECURE_NO_WARNINGS
#include "14~15강 arrayStack .h"
#include <stdio.h>
int menu(const char **mList, size_t menuCnt); /* 메뉴 출력 및 메뉴번호 입력 함수 */
void mInput(Stack *sp); /* 입력메뉴 처리 함수 */
void myDelete(Stack *sp); /* 삭제메뉴 처리 함수 */
void mOutput(Stack *sp); /* 출력메뉴 처리 함수 */
void myflush(); /* 입력 버퍼 flush 함수 */
/*----------------------------------------------------------------------------------
Function name : main
----------------------------------------------------------------------------------*/
int main()
{
Stack stk; /* 스택생성*/
const char *menuList[] = { "입력하기", "삭제하기", "출력하기", "종료" }; /* 메뉴 리스트*/
int menuCnt; /* 메뉴개수 저장변수*/
int menuNum; /* 메뉴번호 저장변수*/
createStack(&stk, 5); /* 스택 초기화*/
menuCnt = sizeof(menuList) / sizeof(menuList[0]); /* 메뉴 개수 계산하기*/
while (1)
{
menuNum = menu(menuList, menuCnt);
if (menuNum == menuCnt) /* 종료메뉴 선택 시 반복문 탈출하기*/
{
break;
}
switch (menuNum)
{
case 1: mInput(&stk); break;
case 2: myDelete(&stk); break;
case 3: mOutput(&stk); /* stack내의 모든 데이터 출력하기*/
}
}
destroyStack(&stk);
return 0;
}
/*--------------------------------------------------------------------------------------
Function name : mInput() - 스택에 데이터를 반복적으로 입력함
Parameters : sp - 스택의 주소
Returns : 없음
--------------------------------------------------------------------------------------*/
void mInput(Stack *sp)
{
int data;
while (1) {
printf("Push할 정수형데이터를 입력하시오(문자나 입력 시 종료) : ");
if (scanf("%d", &data) != 1) { /* 문자가 입력되면 while문을 빠져나감*/
myflush();
break;
}
if (push(sp, data) == FALSE)
printf("push 실패!\n");
}
}
/*--------------------------------------------------------------------------------------
Function name : myDelete() - 스택의 데이터를 반복적으로 꺼냄
Parameters : sp - 스택의 주소
Returns : 없음
--------------------------------------------------------------------------------------*/
void myDelete(Stack *sp)
{
int i;
int cnt; /* pop할 횟수를 입력받아 저장할 변수*/
int popData; /* pop한 데이터를 저장할 변수*/
int res; /* pop()함수의 리턴값을 저장할 변수*/
printf("Stack에서 데이터를 pop할 횟수를 입력하시오: ");
scanf("%d", &cnt);
for (i = 0; i < cnt; i++) {
res = pop(sp, &popData);
if (res == 1) /* 성공적으로 pop 작업을수행했으면*/
{
printf("pop 데이터: %5d\n", popData);
}
else
printf("pop 실패!\n");
}
}
/*--------------------------------------------------------------------------------------
Function name : mOutput - 스택의 모든 데이터 출력 하기
Parameters : sp - 스택의 주소
Returns : 없음
--------------------------------------------------------------------------------------*/
void mOutput(Stack *sp)
{
printStack(sp);
}
/*--------------------------------------------------------------------------------------
Function name : menu() - 메뉴를 출력하고 메뉴번호를 입력받아 리턴함
Parameters : menuLIst - 메뉴출력할 문자열
menuCnt - 메뉴개수
Returns : 선택된메뉴번호
--------------------------------------------------------------------------------------*/
int menu(const char **menuList, size_t menuCnt)
{
size_t i;
size_t menuNum = 0; /* 입력된 메뉴번호 저장 변수*/
int res; /* scanf()함수의 리턴값 저장 변수*/
for (i = 0; i < menuCnt; i++)
{
printf("%d. %s\n", i + 1, menuList[i]);
}
while (menuNum<1 || menuNum>menuCnt) /* 메뉴번호 범위내의 번호가 입력될때 까지 반복*/
{
printf("# 메뉴번호를 입력하세요 : ");
res = scanf("%u", &menuNum);
if (res != 1) /* 정수가 입력되지 않았으면*/
{
myflush(); /* 입력버퍼 비우기*/
continue;
}
}
return menuNum;
}
/*----------------------------------------------------------------------------------
Function name : myflush - 입력 버퍼 내의 모든 데이터 지우는 함수
Parameters : 없음
Returns : 없음
----------------------------------------------------------------------------------*/
void myflush()
{
while (getchar() != '\n')
{
;
}
}
3. 🧨list를 이용한 stack 구현
(1) list stack 의 특징
- stack 을 구현하는 방법
-배열(array)을 이용해서 구현하는 방법
-list를 이용해서 구현하는 방법
- 배열을 이용한 구현에서느 stack size가 고정되나, stack의 size에 제한 받지 않고 저장하기 위해서는 list 로 구현하면 된다.
- 후입선출 구조 형태를 유지하는 stack을 구현할 수 있다.
(2) list stack 구현에 사용되는 데이터형
#pragma once
enum BOOL { FALSE, TRUE };
typedef struct _stacknode Snode;
struct _stacknode
{
int data; /* int 데이터 영역 */
Snode *next; /* 다음 노드를 가리키는 포인터 영역 */
};
typedef struct _stack /* stack 관리 구조체 */
{
Snode *head; /* head pointer (head node 가리킴) */
Snode *tail; /* tail pointer (tail node 가리킴) */
}Stack;
(3) 스택 기능 함수 목록
BOOL createStack(Stack *sp); /* 링크드리스트로 관리되는 스택 생성 함수 */
BOOL isStackEmpty(const Stack *sp); /* 스택이 완전히 비어있는가 검사 */
BOOL push(Stack *sp, int pushData); /* 스택에 데이터 저장하는 함수 */
BOOL pop(Stack *sp, int *popData); /* 스택에서 데이터를 꺼내는 함수 */
void printStack(const Stack*sp); /* 스택 내의 모든 데이터를 출력하는 함수 */
void destroyStack(Stack *sp); /* 스택 메모리 해제 함수 */
(4) 스택 기능 함수 구현
-list.cpp [1]
#include "16강 liststack.h"
#include <stdio.h>
#include <malloc.h>
/*--------------------------------------------------------------------------------------
Function name : createStack - 링크드리스트로 관리되는 스택 생성 함수
Parameters : sp - 스택관리 구조체의 주소
Returns : 성공 - TRUE / 실패 - FALSE
--------------------------------------------------------------------------------------*/
BOOL createStack(Stack *sp)
{
if (sp == NULL) {
return FALSE;
}
sp->head = (Snode*)calloc(1, sizeof(Snode));
if (sp->head == NULL) {
return FALSE;
}
sp->tail = (Snode*)calloc(1, sizeof(Snode));
if (sp->tail == NULL) {
free(sp->head);
return FALSE;
}
sp->head->next = sp->tail;
sp->tail->next = sp->tail;
return TRUE; // 리턴값은 수정해주세요
}
/*--------------------------------------------------------------------------------------
Function name : isStackEmpty() - 스택이 비어있는가 검사
Parameters : sp - 스택관리 구조체의 주소
Returns : 완전히 비어있으면 TRUE 리턴, 비어있지 않으면 FALSE 리턴
--------------------------------------------------------------------------------------*/
BOOL isStackEmpty(const Stack *sp)
{
if (sp == NULL) {
return FALSE;
}
if (sp->head->next == sp->tail) {
return TRUE;
}
else {
return FALSE;
}
}
/*--------------------------------------------------------------------------------------
Function name : push() - 스택에 데이터 하나를 저장함
Parameters : sp - 스택관리 구조체의 주소
pushData - 스택에 저장할 데이터
Returns : 성공적으로 저장하면 TRUE, 실패하면 FALSE 리턴
--------------------------------------------------------------------------------------*/
BOOL push(Stack *sp, int pushData)
{
Snode*cur;
if (sp == NULL) {
return FALSE;
}
cur = (Snode*)calloc(1, sizeof(Snode));
if (cur == NULL) {
return FALSE;
}
else {
cur->next = sp->head->next;
sp->head->next = cur;
cur->data = pushData;
return TRUE;
}
}
/*--------------------------------------------------------------------------------------
Function name : pop() - 스택에서 데이터 하나를 꺼냄
Parameters : sp - 스택관리 구조체의 주소
popData - 꺼낸 데이터를 저장할 기억공간의 주소
Returns : 성공적으로 꺼내면 TRUE, 실패하면 FALSE 리턴
--------------------------------------------------------------------------------------*/
BOOL pop(Stack *sp, int *popData)
{
Snode*cur;//작업용 Snode 포인터 선어
if (sp == NULL) {//sp포인터 NULL check
return FALSE;
}
if (isStackEmpty(sp)==TRUE) {//stack이 비어져 있으면 pop 실패
return FALSE;
}
else {
*popData = sp->head->next->data;//head node 뒤애서 데이터를 꺼낸 후 데이터 노드삭제
cur = sp->head->next;
sp->head->next = sp->head->next->next;
free(cur);
return TRUE;
}
}
/*--------------------------------------------------------------------------------------
Function name : printStack - 스택의 모든 데이터 출력(pop하면 나오는 순서대로 출력)
Parameters : sp - 스택관리 구조체의 주소
Returns : 없음
--------------------------------------------------------------------------------------*/
void printStack(const Stack *sp)
{
Snode*cur;//작업을 Snode 포인터 선언
if (sp == NULL) {//sp포인터 NULL check
return;
}
if (isStackEmpty(sp) == TRUE) {
printf("Stack이 비어 있습니다 \n");
return ;
}
cur = sp->head->next;
while (cur != sp->tail) {
printf("%8d\n", cur->data);
cur = cur->next;
}
printf("\n");
return;
}
/*--------------------------------------------------------------------------------------
Function name : destroyStack() - 스택 소멸 함수
Parameters : sp - 스택관리 구조체의 주소
Returns : 없음
--------------------------------------------------------------------------------------*/
void destroyStack(Stack *sp)
{
Snode*cur;//작업용 Snode 포인터 선언
if (sp == NULL) {//sp 포인터 NULL check
return;
}
//데이터 첫 노드로부터 맨 뒤의 노드까지 모두 삭제
while (sp->head->next != sp->tail) {
cur = sp->head->next;
sp->head->next =sp-> head->next->next;
free(cur);
}
free(sp->head);
free(sp->tail);
sp->head = sp->tail = NULL;
return;
}-main.cpp[2]
#define _crt_secure_no_warnings
#include "16강 liststack.h"
#include <stdio.h>
int menu(const char **mlist, size_t menucnt); /* 메뉴 출력 및 메뉴번호 입력 함수 */
void minput(stack *sp); /* 입력메뉴 처리 함수 */
void mydelete(stack *sp); /* 삭제메뉴 처리 함수 */
void moutput(stack *sp); /* 출력메뉴 처리 함수 */
void myflush(); /* 입력 버퍼 flush 함수 */
/*----------------------------------------------------------------------------------
function name : main
----------------------------------------------------------------------------------*/
int main()
{
stack stk; /* 스택생성*/
const char *menulist[] = { "입력하기", "삭제하기", "출력하기", "종료" }; /* 메뉴 리스트*/
int menucnt; /* 메뉴개수 저장변수*/
int menunum; /* 메뉴번호 저장변수*/
createstack(&stk); /* 스택 초기화*/
menucnt = sizeof(menulist) / sizeof(menulist[0]); /* 메뉴 개수 계산하기*/
while (1)
{
menunum = menu(menulist, menucnt);
if (menunum == menucnt) /* 종료메뉴 선택 시 반복문 탈출하기*/
{
break;
}
switch (menunum)
{
case 1: minput(&stk); break;
case 2: mydelete(&stk); break;
case 3: moutput(&stk); /* stack내의 모든 데이터 출력하기*/
}
}
destroystack(&stk);
return 0;
}
/*--------------------------------------------------------------------------------------
function name : minput() - 스택에 데이터를 반복적으로 입력함
parameters : sp - 스택의 주소
returns : 없음
--------------------------------------------------------------------------------------*/
void minput(stack *sp)
{
int data;
while (1) {
printf("push할 정수형데이터를 입력하시오(문자나 입력 시 종료) : ");
if (scanf("%d", &data) != 1) { /* 문자가 입력되면 while문을 빠져나감*/
myflush();
break;
}
if (push(sp, data) == false)
printf("push 실패!\n");
}
}
/*--------------------------------------------------------------------------------------
function name : mydelete() - 스택의 데이터를 반복적으로 꺼냄
parameters : sp - 스택의 주소
returns : 없음
--------------------------------------------------------------------------------------*/
void mydelete(stack *sp)
{
int i;
int cnt; /* pop할 횟수를 입력받아 저장할 변수*/
int popdata; /* pop한 데이터를 저장할 변수*/
int res; /* pop()함수의 리턴값을 저장할 변수*/
printf("stack에서 데이터를 pop할 횟수를 입력하시오: ");
scanf("%d", &cnt);
for (i = 0; i < cnt; i++) {
res = pop(sp, &popdata);
if (res == 1) /* 성공적으로 pop 작업을수행했으면*/
{
printf("pop 데이터: %5d\n", popdata);
}
else
printf("pop 실패!\n");
}
}
/*--------------------------------------------------------------------------------------
function name : moutput - 스택의 모든 데이터 출력 하기
parameters : sp - 스택의 주소
returns : 없음
--------------------------------------------------------------------------------------*/
void moutput(stack *sp)
{
printstack(sp);
}
/*--------------------------------------------------------------------------------------
function name : menu() - 메뉴를 출력하고 메뉴번호를 입력받아 리턴함
parameters : menulist - 메뉴출력할 문자열
menucnt - 메뉴개수
returns : 선택된메뉴번호
--------------------------------------------------------------------------------------*/
int menu(const char **menulist, size_t menucnt)
{
size_t i;
size_t menunum = 0; /* 입력된 메뉴번호 저장 변수*/
int res; /* scanf()함수의 리턴값 저장 변수*/
for (i = 0; i < menucnt; i++)
{
printf("%d. %s\n", i + 1, menulist[i]);
}
while (menunum<1 || menunum>menucnt) /* 메뉴번호 범위내의 번호가 입력될때 까지 반복*/
{
printf("# 메뉴번호를 입력하세요 : ");
res = scanf("%u", &menunum);
if (res != 1) /* 정수가 입력되지 않았으면*/
{
myflush(); /* 입력버퍼 비우기*/
continue;
}
}
return menunum;
}
/*----------------------------------------------------------------------------------
function name : myflush - 입력 버퍼 내의 모든 데이터 지우는 함수
parameters : 없음
returns : 없음
----------------------------------------------------------------------------------*/
void myflush()
{
while (getchar() != '\n')
{
;
}
}
