알고리즘 기초 4- [자료구조, 스택]

Stack

목차

Stack의 기본 개념

• 입력과 출력을 한 방향으로 제한한 자료 구조
• 바닥부터 데이터를 Stacking(쌓는) 느낌으로 접근

 

• push : 데이터에 순서를 적용해 차례로 저장
• pop : 가장 최신 데이터부터 차례로 가져온다.

 

Stack
data
data
data
data

위와 같은 방식을 LIFO (Last In First Out)라고 한다.

스택의 구조체

C

typedef struct _NODE {
    int Data;
    struct _NODE *Next;
}NODE;

 

Java

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

 

JavaScript

class Node {
    constrcutor(data) {
        this.data = data;
        this.next = null;
    }
}

 

Push / Pop

: ## 굵은 글씨가 현재 Top ##

• Push 0

  st1
  data0

• Push 1

  st1
  data1
  data0

• Pop (get data1)

  st1
  data0

 

링크드 리스트를 사용한 스택 알고리즘

C

---

 

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

typdef struct  _Node {
    int Data;
    struct _Node *Next;
}Node;

// 스택의 하위 자료구조용 노드

NODE *head, *end;
NODE *ptrNode;

void InitiazizeStack(void); //스택 함수 초기화
void Push(int); // 데이터 삽입
int Pop(void); // 데이터 삭제
void DisplayStack(void); // Display Stack

// 스택 초기화
void InitalizeStack(void) {
    head = (NODE *)malloc(sizeof(NODE));
    end = (NODE *)malloc(sizeof(NODE));
    head->Next=end;
    end->Next=end;
}

void Push(int data) {
    ptrNode = (NODE *)malloc(sizeof(NODE));
    ptrNode->Data = data;
    ptrNode->Next = head->Next;
    head->Next = ptrNode;
}

int Pop(void) {
    int ret;
    ptrNode = head->Next;
    head->Next = head->Next->Next;
    ret = ptrNode->Data;
    free(ptrNode);
}

void DisplayStack(void) {
    NODE *indexNode;
    printf("head -> ");
    for(indexNode = head->Next; indexNode != end; indexNode = indexNode->Next) {
        printf("%d -> ", indexNode->Data);
    }
    printf("end");
}

void main() {
    int ret;
    InitializeStack();

    Push(1);
    Push(3);
    Push(10);
    PusH(20);
    Push(12);

    printf("다섯 번의 Push() 함수 호출 실행 결과\n");
    DisplayStack();

    ret = Pop();
    ret = Pop();
    ret = Pop();

    printf("\n세 번의 Pop() 함수 호출 후 실행 결과\n");
    DisplayStack();
}

// 다섯 번의 Push() 함수 호출 실행 결과
// head -> 12 - > 20 -> 10 -> 3 -> 1 -> end
// 세 번의 Pop() 함수 호출 실행 결과
// head ->  3 -> 1 -> end

---

 

Java

---

    class Stack {
        static class Node {
            int data;
            Stack next;

            public Node(int data) {
                this.data = data;
                this.next = null;
            }
        }

        static Node head, end;
        static Node ptrNode;

        public static void initializeStack() {
            head = new Node(-1);
            end = new Node(-1);
            head.next = end;
            end.next = end;
        }

        public static void push(int data) {
            ptrNode = new Node(data);
            ptrNode.next = head.next;
            head.next = ptrNode;
        }

        public static int pop() {
            int ret = -1;
            ptrNode = head.next;
            ret = ptrNode.data;
            head.next = head.next.next;
            return ret;
        }

        public static void displayStack() {
            Node indexPtr;

            for(indexPtr = head.next; indexPtr != end; indexPtr = indexPtr.next) {
                System.out.print(String.format("%d -> ", indexPtr.data));
            }
            System.out.println();
        }

        public static void main(String[] args) {
            int ret;
            initializeStack();

            push(1);
            push(3);
            push(10);
            push(20);
            push(12);

            displayStack();

            ret = pop();
            ret = pop();
            ret = pop();

            displayStack();
        }
    }
// 결과
// 12 -> 20 -> 10 -> 3 -> 1
// 3 -> 1

---

 

JavaScript

---

 

    class Stack {
        constructor(data) {
            this.data = data;
            this.next = null;
        }
    }

    let head, end;
    let ptrNode;

    const initializeStack = () => {
        head = new Stack(-1);
        end = new Stack(-1);
        head.next = end;
        end.next = end;
    }

    const push = (data) => {
        ptrNode = new Stack(data);
        ptrNode.next = head.next;
        head.next = ptrNode;
    }

    const pop = () => {
        let ret = -1;
        ptrNode = head.next;
        ret = ptrNode.data;
        head.next = head.next.next;
        return ret;
    }

    const displayStack = () => {
        let indexPtr;
        let str = "";
        for(indexPtr = head.next; indexPtr != end; indexPtr = indexPtr.next) {
                str += `${indexPtr.data} ->`;
            }
        console.log(str);
    }

    const main = () => {
        let ret;
        initializeStack();

        push(1);
        push(3);
        push(10);
        push(20);
        push(12);

        displayStack();

        ret = pop();
        ret = pop();
        ret = pop();

        displayStack();
    }
  main();

// 결과
// 12 -> 20 -> 10 -> 3 -> 1
// 3 -> 1

---