chapter02 자료구조 스택

2.1.1 스택의 개념

활용도가 높은 자료구조
(아래서는 자료구조를 말하지만 메모리에서) 지역변수는 스택에 할당된다.
요소의 삽입과 삭제가 한쪽 끝에서만 이루어진다
 
스택의 주요기능 : Push (삽입), Pop (제거)
 

2.2 배열로 구현하는 스택

각 노드를 동적으로 생성하고 제거하는 대신
스택 생성 초기에 사용자가 부여한 용량만큼의 노드를 한꺼번에 생성한다. (미리 메모리 용량을 정해줘야 함…)
그리고 최상위 노드의 위치를 나타내는 변수를 두고 삽입과 제거 연산을 수행한다.
(아래에서는 다르지만, 생성 함수에서 바로 스택의 주소를 반환하면 포인터변수를 선언함과 동시에 값을 삽입할 수 있다.)
 

#include <stdio.h>
#include <stdlib.h>

//배열기반으로 구현되는 스택의 노드  
typedef int ElementType;
typedef struct tagNode {
    ElementType Data;
} Node;

//스택 구조체
typedef struct tagArrayStack {
    int Capacity; //용량
    int Top; // 최상위 노드의 위치
    Node* Nodes; // 노드 배열
}ArrayStack;
//최상위 노드의 위치는 삽입,제거 연산을 할 때 최상위 노드에 접근
//노드 배열은 스택에 쌓이는 노드를 보관하는데 사용 자유저장소에 할당한 배열의 첫번째 요소를 가리킨다.


void AS_CreateStack(ArrayStack** Stack, int Capacity);
void AS_DestroyStack(ArrayStack* Stack);
void AS_Push(ArrayStack* Stack, ElementType Data);
ElementType AS_Pop(ArrayStack* Stack);
ElementType AS_Top(ArrayStack* Stack);
int AS_GetSize(ArrayStack* Stack);
int AS_IsEmpty(ArrayStack* Stack);



int main() {

    int i = 0;
    ArrayStack* Stack = NULL;

    AS_CreateStack(&Stack, 10);

    AS_Push(Stack, 3);
    AS_Push(Stack, 4);
    AS_Push(Stack, 5);
    AS_Push(Stack, 7);

    printf("Capacity : %d, Size : %d, Top : %d\n\n", Stack->Capacity, AS_GetSize(Stack), AS_Top(Stack));

    for (i = 0; i < 4; i++) {
        if (AS_IsEmpty(Stack))
            break;

        printf("Popped:%d,", AS_Pop(Stack));

        if (!AS_IsEmpty(Stack))
            printf("Current Top : %d\n", AS_Top(Stack));
        else
            printf("Stack Is Empty.\n");
    }

    AS_DestroyStack(Stack);


    return 0;
}

//스택 생성 함수
void AS_CreateStack(ArrayStack** Stack, int Capacity) {
    //스택을 자유 저장소에 생성
    (*Stack) = (ArrayStack*)malloc(sizeof(ArrayStack));

    //입력된 Capacity 만큼의 노드를 자유 저장소에 생성, 노드 배열의 시작 주소가 저장됨)
    (*Stack)->Nodes = (Node*)malloc(sizeof(Node) * Capacity);

    //Capacity 및 Top 초기화
    (*Stack)->Capacity = Capacity;
    (*Stack)->Top = -1;
}

//노드 및 스택 해제 함수
void AS_DestroyStack(ArrayStack* Stack) {
    // 노드를 자유 저장소에서 해제(Nodes는 Node배열을 가리키는 포인터임)
    free(Stack->Nodes);
    //스택을 자유 저장소에서 해제
    free(Stack);
}

//노드 삽입 연산.최상위 노드에 1을 더한 곳에 새 노드 입력
void AS_Push(ArrayStack* Stack, ElementType Data) {
    Stack->Top++;
    Stack->Nodes[Stack->Top].Data = Data;
}

//노드 제거 연산.최상위 노드를 1 낮추면 된다. pop은 반환도 함.
ElementType AS_Pop(ArrayStack* Stack) {
    int Position = Stack->Top--;
    return Stack->Nodes[Position].Data;
}

//top에 있는 요소 출력
ElementType AS_Top(ArrayStack* Stack) {
    return Stack->Nodes[Stack->Top].Data;
}

//현재 Nodes배열에 몇개의 요소가 들어가 있는지
int AS_GetSize(ArrayStack* Stack) {
    return Stack->Top + 1;
}

//비어있으면 Ture
int AS_IsEmpty(ArrayStack* Stack) {
    return (Stack->Top == -1);
}

2.3 링크드리스트로 구현하는 스택

#include <stdio.h>
#include <stdlib.h>

typedef struct tagNode {
char* Data;
struct tagNode* NextNode;
}Node;
//char*형은 포인터이기 때문에 문자열이 저장된 주소를 담는다.
//링크드리스트에 필요없는 것 : 스택의 용량, 최상위 노드의 인덱스
//필요한 것 : 리스트 포인터, 헤드와 테일에 대한 포인터

typedef struct tagLinkedListStack{
Node* List; //데이터를 담는 링크드리스트 헤드 노드포인터
Node* Top; //링크드리스잍 테일의 포인터=최상위 노드에 대한 포인터
} LinkedListStack;

void LLS_CreateStack(LinkedListStack** Stack);
void LLS_DestroyStack(LinkedListStack* Stack);
Node* LLS_CreateNode(char*NewData);
void LLS_DestroyNode(Node* _Node);
void LLS_Push (LinkedListStack* Stack, Node* NewNode);
Node* LLS_Pop(LinkedListStack* Stack);
Node* LLS_Top(LinkedListStack* Stack);
int LLS_GetSize(LinkedListStack* Stack);
int LLS_IsEmpty(LinkedListStack* Stack);

int main(){
  printf("nice");
  return 0;
}

void LLS_CreateStack(LinkedListStack** Stack){
  //스택을 자유 저장소에 생성
  (*Stack) = (LinkedListStack*)malloc(sizeof(LinkedListStack));
  (*Stack)->List = NULL;
  (*Stack)->Top=NULL;
}

void LLS_DestroyStack(LinkedListStack* Stack) {
 //먼저 노드 제거
  while(!LLS_IsEmpty(Stack)){
    Node* Popped = LLS_Pop(Stack);
    LLS_DestroyNode(Popped);
  }

  //스택을 자유 저장소에서 해제
  free(Stack);
}

//노드 생성
Node* LLS_CreateNode(char*NewData){
  Node* NewNode = (Node*)malloc(sizeof(Node));
  NewNode->Data = (char*)malloc(strlen(NewData)+1);

  strcpy(NewNode->Data,NewData);
  NewNode->NextNode = NULL;
  return NewNode;
}

//노드 소멸
void LLS_DestroyNode(Node* _Node){
  free(_Node->Data);
  free(_Node);
}

//노드 삽입
void LLS_Push (LinkedListStack* Stack, Node* NewNode){
  if (Stack->List ==NULL){
    Stack->List = NewNode;
  }
  else {
    //스택의 Top 위에 새 노드를 얹는다.
    Stack->Top->NextNode = NewNode;
  }

  //스택의 Top 필드에 새 노드의 주소를 등록한다.
  Stack->Top = NewNode;
}

Node* LLS_Pop(LinkedListStack* Stack){
  // LLS_Pop 함수가 반환할 최상위 노드 저장
  Node* TopNode = Stack->Top;

  if (Stack->List == Stack->Top ){
    Stack->List = NULL;
    Stack->Top = NULL;
  }
  else{
    //Top 아래에 있던 노드를 새로운 CurrentTop에 저장
    Node* CurrentTop = Stack->List;
    while(CurrentTop!= NULL && CurrentTop -> NextNode!= Stack->Top){
      CurrentTop = CurrentTop->NextNode;  
    }
    Stack->Top = CurrentTop;
    Stack->Top->NextNode = NULL;
    
  }
  return TopNode;
}

Node* LLS_Top(LinkedListStack* Stack){
  return Stack->Top;
}

int LLS_GetSize(LinkedListStack* Stack){
  int Count = 0;
  Node* Current = Stack->List;

  while(Current!=NULL) {
    Current = Current->NextNode;
    Count++;
  }
  return Count;
}

int LLS_IsEmpty(LinkedListStack* Stack){
  return (Stack->List ==NULL);
}