스택

관련 메서드
연결 리스트로 스택 구현(Javascript)
스택의 응용 - 후위 표기법
1. 후위 표기법
  1. 중위 표기법을 후위 표기법으로 변환하는 과정
  2. 후위 표기법 표기 수식의 연산 과정
References

데이터가 입력되면 입력되는 순서대로 쌓고, 나중에 들어온 것부터 먼저 사용하는 자료구조이다. 스택 형태의 데이터 구조를 LIFO(Last In First Out)형이라고 하며, 스택에 데이터를 넣는 것을 PUSH, 데이터를 꺼내는 것을 POP이라고 한다. 스택의 구현은 배열을 이용해도 되고, 연결 리스트를 이용해도 된다.

function Stack() {
  Stack = [];
  Stack.push('A');
  Stack.push('B');
  Stack.push('C');

  console.log(Stack);

  while (Stack.length) {
    console.log(Stack.pop());
  }
}

Stack(); // C B A

메서드	설명
append(data)	노드 추가
find(data)	노드 찾기
display()	스택의 모든 요소 출력
findPrevious(data)	이전 노드 찾기
remove(data)	노드 삭제
pop()	마지막 노드 제거
peek()	마지막 노드 반환
isEmpty()	스택이 비어있는지 확인

연결 리스트로 스택 구현(Javascript)

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

function Stack() {
  this.head = null;
}

// 노드 추가
Stack.prototype.append = function (data) {
  var node = new Node(data);
  var current;

  // 리스트가 비어있을 경우
  if (this.isEmpty()) {
    this.head = node;
  } else { // 리스트가 비어있지 않을 경우
    current = this.head
    // 리스트의 마지막 노드를 찾는다
    while (current.next !== null) {
      current = current.next;
    }
    // 리스트의 마지막 노드에 삽입할 노드 연결
    current.next = node;
  }
}

// 노드 찾기
Stack.prototype.find = function (data) {
  var current = this.head;
  while (current.data !== data) {
    current = current.next;
  }
  return current;
}

// 리스트의 요소 출력
Stack.prototype.display = function () {
  if (this.isEmpty()) {
    console.log('리스트가 비어있습니다.');
  } else {
    var result = [];
    var current = this.head;
    while (current !== null) {
      result.push(current.data);
      current = current.next;
    }
    result = result.join(',');
    console.log(result);
  }

}

// 이전 노드 찾기
Stack.prototype.findPrevious = function (data) {
  var current = this.head;
  while (current.next.data !== data) {
    current = current.next;
  }
  return current;
}

// 노드 삭제
Stack.prototype.remove = function (data) {
  // 첫 번쩨 노드일 경우
  if (this.head.data === data) {
    this.head = this.head.next;
  } else { // 첫 번째가 아닐 경우
    var prev = this.findPrevious(data)
    prev.next = prev.next.next;
  }
}

// 가장 마지막에 들어간 노드를 제거
Stack.prototype.pop = function () {
  var node = this.peek();
  // 만약 리스트의 노드가 하나밖에는 없다면
  if (this.head.next === null) {
    this.head = null;
  } else {
    var prev = this.findPrevious(node.data);
    prev.next = null;
  }
}

// 마지막 노드 반환
Stack.prototype.peek = function () {
  var current = this.head;
  while (current.next !== null) {
    current = current.next;
  }
  return current;
}

// 스택이 비어있는지 확인
Stack.prototype.isEmpty = function () {
  return this.head === null;
}

var list = new Stack();
list.append('A');
list.append('B');
list.append('C');
list.display(); // ABC
list.pop();
list.display(); // AB
list.pop();
list.append('D');
list.pop();
list.display(); // A

스택의 응용 - 후위 표기법

후위 표기법

역폴란드 표기법(RPN, reverse Polish notation) 또는 후위 표기법(후치 표기법)(後位 -, postfix notation)은 연산자를 연산 대상의 뒤에 쓰는 연산 표기법이다.

예를 들어, 중위 표기법에서 “1 + 2”와 같은 의미를 지니는 식은 역폴란드 표기법으로는

1 2 +

가 된다. 또한, (2 + 3) * 4를 역폴란드 표기법으로 쓰면 다음과 같다.

2 3 + 4 *

이와 같은 방식은 수식을 계산할 때 특별한 변환이 필요없이, 수식을 앞에서부터 읽어 나가면서 스택에 저장하면 된다는 장점이 있다. 또한, 중위 표기법에서는 연산자의 우선순위가 모호해서 괄호가 필요한 경우가 있지만, 역폴란드 표기법에서는 그러한 문제점이 발생하지 않는다. 그러나 인간의 눈으로 쉽게 이해하거나 계산하기 힘들다는 문제점이 있어 눈에 보이는 표기보다는 주로 프로그램 내부의 표기법으로 사용한다.