(22.08.18)자료구조 6 - 스택(Stack)

스택?

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조

• 스택은 자료구조 그 자체로서는 단순하지만 여러 알고리즘에서 쓰일 수 있다.
  • 전위 표기법 -> 후위 표기법 전환
  • 후위 표기법의 연산
  • 괄호 검사
  • 문자열 역순으로 재배치
  • 실행 취소(undo)
  • 재귀 알고리즘
  • 웹 브라우저의 방문기록(뒤로가기)
  • 재귀 알고리즘
    재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
    재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.
    스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.
    또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
  • (출처: https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html)

 

ADT

• init
  스택을 초기화한다.
• isEmpty
  스택 내부가 비어있다면 true, 아니면 false를 반환한다.
• push
  스택의 최상단위에 값을 추가한다.
• pop
  스택의 최상단의 값을 반환하고 스택에서 제거한다.
  (조건 - 스택이 비어있지 않아야 한다.)
• peek
  스택 최상단의 값을 반환한다. (pop과 달리 제거는 하지 않는다.)
  (조건 - 스택이 비어있지 않아야 한다.)

 

스택의 구현

스택은 크게 2가지 방식으로 구현할 수 있다.

1. 배열 기반 구현 (array-based implementation)

정적 or 동적 배열을 통해 구현하는 스택

 

• top
  1. 변수로 현재 stack이 쌓여있는 최상단의 위치를 기록
  2. -1은 탑의 초깃값으로 비어있다는 것을 의미(isEmpty)
• push
  • top에 1을 더하고 배열에서 그 위치에 데이터를 추가
• pop
  1. isEmpty 체크
  2. top의 데이터를 반환하고 top에 1을 뺀다.
• peek
  1. isEmpty 체크
  2. top의 데이터를 반환

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

#define SIZE 100
typedef int data;

struct Array_Stack {
    data arr[SIZE];
    int top;
} typedef stack;

void init(stack *stk) {
    stk->top = -1;
}

int isEmpty(stack *stk) {
    if (stk->top == -1)
        return 1;
    else
        return 0;
}

void push(stack *stk, data value) {
    stk->top++;
    stk->arr[stk->top] = value;
}

data pop(stack *stk) {
    if (isEmpty(stk)) {
        printf("스택에 값이 없습니다. 종료합니다.");
        exit(-1);
    }

    data temp = stk->arr[stk->top];
    stk->top--;
    return temp;
}

data peek(stack *stk) {
    if (isEmpty(stk)) {
        printf("스택에 값이 없습니다. 종료합니다.");
        exit(-1);
    }

    return stk->arr[stk->top];
}

위의 코드는 정적배열로 구성된 stack이다.

 

2. 연결리스트 기반 구현 (linked-structure implementation)

연결리스트를 통해 구현한 스택

• head: 최상단의 Node를 가르키는 포인터 변수,
• init
  새로운 Node를 만들고, malloc으로 동적할당시켜준다.
• isEmpty
  head 값이 null일 경우 true, 아니면 false 반환
• push
  1. 동적할당으로 새로운 newNode를 만든다.
  2. 원래 head에 있던 Node를 newNode의 Next 변수에 할당
  3. head에 newNode를 할당
• pop
  1. isEmpty를 체크
  2. head에 있던 Node->next에 할당된 nextNode를 head에 할당
  3. 기존의 Node를 free
  4. Node의 값을 반환
• peek
  1. isEmpty를 체크
  2. head에 있는 Node의 값을 반환

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

typedef int data;

typedef struct node_ {
    data value;
    struct node_ *next;
} node;

typedef struct listStack {
    struct node_ *head;
} stack;

void init(stack *stk, data initData) {
    node *newNode = (node *) malloc(sizeof(node));
    newNode->value = initData;
    stk->head = newNode;
}

int isEmpty(stack *stk) {
    if (stk->head == '\0')
        return 1;
    else
        return 0;
}

void push(stack *stk, data newData) {
    node *newNode = (node *) malloc(sizeof(node));
    newNode->value = newData;
    newNode->next = stk->head;
    stk->head = newNode;
}

data pop(stack *stk) {
    if (isEmpty(stk)) {
        printf("스택에 값이 없습니다. 종료합니다.");
        exit(-1);
    }

    data temp = stk->head->value;
    node *tempNode = stk->head;
    stk->head = stk->head->next;
    free(tempNode);
    return temp;
}

data peek(stack *stk) {
    if (isEmpty(stk)) {
        printf("스택에 값이 없습니다. 종료합니다.");
        exit(-1);
    }

    return stk->head->value;
}

위 코드를 보시다시피 연결리스트 기반이기 때문에 

1. push를 할 때마다 메모리를 할당하고
2. pop할 때마다 메모리에서 제거해준다.

시간 복잡도

• 접근(Access)의 시간복잡도는 선형으로 배열보다 상대적으로 느리다.
• 반면, 삽입, 삭제는 상수의 시간복잡도를 가지므로 데이터의 크기에 관계없이 빠르다.
  
  

C++

Stack은 STL에 있기 때문에 #include <stack> 만 해주면 된다.

• stack<value_type, container_type> 변수명;
  이렇게 선언 해주면 초기화가 된다.
  • value_type: 담을 데이터의 자료형
  • container_type: 스택의 elment들을 담을 underlying container
    • deque: default로 설정되어 있다.
    • vector, list로도 구성할 수 있다.
    • stack의 성능은 container에 영향을 받는다.
  • ex) stack<int,vector<int>> stk;

그렇다면 stack 자료 형을 사용해서 얻는 이점은?

(vector도 push,pop이 가능하다.)

 

• 바로 가독성
• 그외에는 큰 이점이 없으니 C++ 에서는 vector를 쓰도록 하자!

Java

결론부터 말하면 Stack 대신 Deque를 쓰는 것이 낫다. (공식문서에서도 언급됨)

1. Stack 은 Class, Deque는 interface
   -> java는 다중상속을 지원하지 않기 때문에, Deque가 객체지향적 관점에서 확장성이 더 낫다.
2. 동기화, 메소드 성능
   -> Stack은 vector를 상속 받는데, Vector.class는 쓰레드 안전성(Thread Safe)를 보장하기 위한 전통적인 방법이다.
   그래서 여러 단점들이 생기는데,

- 모든 작업에서 Lock이 걸려 성능저하를 발생시킬 수 있다.
- 단일 스레드 작업 시 성능저하를 발생시킬 수 있다.

반면 deque는 쓰레드 안정성을 지원하지 않기 때문에 Stack보다 더 나은 성능을 보여줄 수 있다.

 

3. Java에서 Stack은 인덱스 접근이 가능하다.

• 즉, LIFO 규칙을 위반한다.
• 하지만, Deque도 양방향 대기열을 지원하기 때문에 LIFO를 위반할 수 있다.