[알고리즘 공부] Stack

---

참고

자료구조

---

자료구조는 데이터의 표현과 저장 방법을 의미
그러므로 , 자료구조를 알아야 알고리즘을 배울 수 있음.

1. 스택 (Stack)

---

스택은 연결리스트인데 뒤로 넣고 뒤로만 뺄 수 있습니다. push와 pop만 할 수 있으며, 스택은 실행이 되는 특정한 순서를 따르는 선형적 데이터 구조입니다.

출처: https://lsh424.tistory.com/51

순서는 두 가지가 존재합니다.

첫째, LIFO(Last In First Out) : 마지막에 들어온 데이터가 먼저가 먼저 나가는 데이터 구조로, 흔히 후입선출 구조라고도 부릅니다. 둘째, FILO(First In Last Out) : 처음 들어온 데이터가 마지막에 나가는 데이터 구조로, 흔히 선입후출라고도 이야기합니다.

이중 스택은 LIFO 구조입니다.

출처: geeksforgeeks.org

스택에서 3가지 기본 작업이 수행됩니다.

• Push : 스택 안으로 데이터를 넣습니다. 만약 스택이 꽉 찬 상태에서 데이터를 더 넣을 경우, Overflow condition(오버플로우 상태)라고 이야기합니다.

  • 스택은 크기를 고정해서 사용하기 때문에 고정된 크기의 스택에 데이터를 계속 넣어서 넘치게 되면, 다른 메모리 영역을 침범하게 됩니다.

• Pop : 스택 안에 있는 데이터를 제거합니다. 아이템은 넣어진 역순으로 빠져나옵니다. 만약 스택이 비어있는 상태에서 데이터를 꺼내려는 경우, Underflow condition(언더플로우 컨디션)라고 이야기합니다.

• Peek or Top : 스택의 꼭대기 요소를 반환합니다.

• isEmpty : 만약 스택이 비어있다면, true를 반환하고, 비어있지 않다면 false를 반환합니다.

스택의 구현

---

스택을 구현하는 두 가지 방법이 존재하는데,

배열(array)을 사용하거나 링크드 리스트(linked list)를 사용합니다.

스택을 배열을 사용할 경우

var Stack = (function () {
  function Stack() {
    this.top = null;
    this.count = 0;
  }
  function Node(data) {
    this.data = data;
    this.next = null;
  }
  Stack.prototype.push = function (data) {
    var node = new Node(data);
    node.next = this.top;
    this.top = node;
    return ++this.count;
  };
  Stack.prototype.pop = function () {
    if (!this.top) {
      // stack underflow 방지
      return false;
    }
    var data = this.top.data;
    this.top = this.top.next;
    // 예전 this.top의 메모리 정리
    this.count--;
    return data;
  };
  Stack.prototype.stackTop = function () {
    return this.top.data;
  };
  return Stack;
})();

호출 결과

var stack = new Stack();
stack.push(1); // 1
stack.push(3); // 2
stack.push(5); // 3
stack.pop(); // 5
stack.stackTop(); // 3

배열을 이용했을 경우의 장점과 단점(pros and cons)

장점: 구현하기 쉽다. 포함되지 않은 포인터로서 메모리는 저장된다.

단점: 다이내믹하지 않다. 런타임에 의해서 배열이 증가하거나 작아지지 않는다.

링크드리스트를 사용할 경우

var LinkedList = (function () {
  function LinkedList() {
    this.length = 0;
    this.head = null;
  }
  function Node(data) {
    this.data = data;
    this.next = null;
  }
  LinkedList.prototype.add = function (value) {
    var node = new Node(value);
    var current = this.head;
    if (!current) {
      // 현재 아무 노드도 없으면
      this.head = node; // head에 새 노드를 추가합니다.
      this.length++;
      return node;
    } else {
      // 이미 노드가 있으면
      while (current.next) {
        // 마지막 노드를 찾고.
        current = current.next;
      }
      current.next = node; // 마지막 위치에 노드를 추가합니다.
      this.length++;
      return node;
    }
  };
  LinkedList.prototype.search = function (position) {
    var current = this.head;
    var count = 0;
    while (count < position) {
      // position 위치만큼 이동합니다.
      current = current.next;
      count++;
    }
    return current.data;
  };
  LinkedList.prototype.remove = function (position) {
    var current = this.head;
    var before;
    var remove;
    var count = 0;
    if (position == 0) {
      // 맨 처음 노드를 삭제하면
      remove = this.head;
      this.head = this.head.next; // head를 두 번째 노드로 교체
      this.length--;
      return remove;
    } else {
      // 그 외의 다른 노드를 삭제하면
      while (count < position) {
        before = current;
        count++;
        current = current.next;
      }
      remove = current;
      before.next = remove.next;
      // remove 메모리 정리
      this.length--;
      return remove;
    }
  };
  return LinkedList;
})();

호출 결과

var list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);
list.length; // 3
list.search(0); // 1
list.search(2); // 3
list.remove(1);
list.length; // 2

링크드리스트의 장점과 단점(pros and cons)

장점: 런타임에 의해 스택의 실행이 증가하거나 줄어듭니다.

단점: 포인터를 포함해야 하기 때문에 추가적인 메모리가 필요로 합니다.

스택에 관련한 시간 복잡도

스택에서 사용되는 기본 작업들인 push, pop, isEmpty와 peek 메서드는 모두 O(1)의 시간 복잡도를 가집니다.

---