[ ᴀʟɢᴏʀɪᴛʜᴍ ] Stack ( 스택 )

NewHa·2023년 10월 17일

ᴀʟɢᴏʀɪᴛʜᴍ

목록 보기

8/14

🌱 STACK ( 스택 )

👉🏻 스택 (stack, '쌓다, 포개다') : 직역 그대로 데이터를 순서대로 쌓는 구조입니다. 새로운 요소의 삽입과 기존 요소의 제거가 하나의 방향, 즉 스택의 최상단(top)에서만 발생하는 선형 데이터 구조입니다. 쉽게 말하자면 프링글스 감자칩을 먹을 때 뚜껑쪽에서 하나하나 꺼내먹는 상황입니다. 이런 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부릅니다.

데이터를 삽입, 삭제, 조회하는 것이 스택의 최상단에서만 접근할 수 있기 때문에 제한적 접근 특징을 가집니다. 그렇기 때문에 하나씩 삽입, 삭제 할 수 있습니다. 이 때 마지막에 삽입된 요소가 먼저 나오는 후입선출(LIFO)의 구조적 특성으로 스택 구조 내에서 특정 데이터를 조회할 수 없습니다.

☀️ Type of Stack ( 유형 )

고정 크기 스택

고정 크기 스택은 고정 크기를 가지며 동적으로 늘어가거나 줄어들 수 없습니다. 스택이 가득 차고 여기에 요소를 추가하려고 하면 오버플로 오류가 발생합니다. 스택이 비어 있고 스택에서 요소를 제거하려고 하면 언더플로 오류가 발생합니다.

동적 크기 스택

동적 크기 스택은 동적으로 늘어나거나 줄어들 수 있습니다. 스택이 가득 차면 새 요소를 수용할 수 있도록 자동으로 크기가 늘어나고, 스택이 비어 있으면 크기가 줄어듭니다. 스택 크기를 쉽게 조정할 수 있으므로 연결 목록을 사용하여 구현됩니다.

재귀 스택

컴퓨트 프로그램에서 함수 호출을 추적하고 함수가 반환될 때 오바른 함수로 제어를 반환하는 데 사용됩니다.

메모리 관리 스택

프로그램 카운터의 값과 레지스터의 값을 컴퓨터 프로그램에 저장하여 함수가 반환될 때 프로그램이 이전 상태로 돌아갈 수 있도록 하는 스택 유형입니다.

실행 취소 - 다시 실행 스택

스택은 컴퓨터 프로그램에서 사용자가 작업을 실행 취소하고 다시 실행할 수 있도록 하는 데 사용됩니다.

☀️ Characteristic of Stack( 특징 )

🪴 기본 작업

Method	시간복잡도	작 업
push()	O(1)	스택에 요소를 삽입합니다. 스택이 가득 차면 overflow 상태라고 합니다.
pop()	O(1)	스택에서 요소를 제거합니다. 푸시된 순서의 역순으로 pop 되며, 스택이 비어 있으면 underflow의 조건이라고 합니다.
isEmpty()	O(1)	스택이 비어 있으면 true, 그렇지 않으면 false를 반환합니다.
isFull()	O(1)	스택이 가득 차 있으면 treu, 그렇지 않으면 false를 반환합니다.
size()	O(1)	스택 내의 모든 요소들의 개수(크기)를 반환합니다.
top()	O(1)	스택의 최상위 요소를 반환합니다.
peek()	O(1)	top 포인터가 가리키는 데이터를 조회(확인)합니다.

🪴 장 점

배열이나 연결 리스트를 사용해 구현하기 쉽고, 이해하기 쉽습니다.
인접한 메모리 블록을 사용하므로 다른 데이터 구조에 비해 메모리 활용이 더 효율적 입니다.
스택 상단에서 요소가 추가﹒제거되며 엑세스 시간이 빠릅니다.
함수 호출과 해당 상태를 저장하는 데 스택 데이터 구조가 사용됩니다. 재귀 함수 호출을 효율적으로 구현하는 데 도움이 됩니다.
이전 상태를 저장하여 가능한 모든 솔류션을 탐색하기 위해 문제해결에 사용되는 역추적 알고리즘을 지원합니다.
프로그래밍 언어의 구문 분석을 위한 컴파일러 설계에 사용됩니다.
텍스트 편집기, 그래픽 디자인 도구, 소프트웨어 개발 환경과 같은 다양한 응용 프로그램에서 실행 취소 및 다시 실행 작업을 활성화하는 데 사용됩니다.

🪴 단 점

스택 데이터 구조는 고정된 수의 요소만 보유할 수 있으므로 용량이 제한되어 있습니다. 스택이 가득 차 있는데 새 요소를 추가하면 stack overflow가 발생하여 데이터가 손실될 수 있습니다. 따라서 재귀 함수 호출을 하며 너무 많이 호출하면 stack overflow로 이어져 프로그램이 종료될 수 있습니다.
스택이 비어 있는데도 요소를 제거하려고 pop()하면 stack underflow가 발생할 수 있습니다.
스택 상단에서 요소를 추가하고 제거하는 것만 허용하고, 해당 요소에 대한 무작위 접근를 허용하지 않습니다. 스택 중간에 있는 요소에 접근하려면 그 위의 모든 요소를 제거해야 합니다.
연속적인 메모리 블록을 사용하므로 요소가 자주 추가되고 제거되면 메모리 조각화가 발생할 수 있습니다.
검색 또는 정렬 알고리즘과 같이 중간에 있는 요소에 접근해야 하는 애플리케이션에는 적합하지 않습니다.

🪴 활 용

컴퓨터 과학에서 표현식 평가, 함수 호출, 메모리 관리 등 다양한 응용 분야에 일반적으로 사용됩니다.

다양한 애플리케이션의 실행취소 - 다시 실행 기능, 브라우저의 방문 웹 페이지 추적에 스택이 사용됩니다. 작업 혹인 url이 스택에 push되고 실행취소(뒤로 가기)버튼을 누르면 스택의 최상위 요소(작업이나 url)가 pop됩니다.
표현식 평가, 함수호출, 메모리 관리를 비롯한 다양한 컴퓨터 과학에서 일반적으로 사용됩니다. 표현식 평가에서 처리되는 피연산자와 연산자를 저장합니다. 함수 호출에서 호출되는 순서를 추적하고 마지막으로 호출된 함수를 먼저 완료해 반환하면 pop 되어 이전 함수의 실행을 재개합니다. 메모리 관리에서 실행 목적을 위한 기본관리로 스택을 사용합니다. 프로그램 카운터의 값과 레지스터의 값을 저장해 함수가 반환될 때 사용할 수 있습니다.
트리순회 등의 알고리즘에서 사용할 수 있습니다.
YouTube 다운로드 및 알림을 비롯한 모든 갤러리, 통화기록, 이메일 등도 LIFO 형식으로, 최신항목을 먼저 표시합니다.

☀️ Implements of Stack( 구현 )

배열이나 연결리스트를 사용하여 구현할 수 있습니다. 스택에는 최상위 포인터가 포함됩니다.

🕶️ 배열로 구현

스택을 위한 배열을 하나 만듭니다. index가 0이면 스택이 비어 있는 것이고, 스택에 요소를 삽입할 때 index 자리에 넣고 index를 올립니다. index가 초기 배열 크기 이상이면 stack이 꽉 찬 것이고, 요소를 삭제할 때는 index에 있던 값을 반환하고 index를 하나 줄입니다.

let index = -1; // 👉🏻 index가 pointer이므로 메모리를 덜 사용합니다.
let MAX = 1000; // 👉🏻 스택의 크기를 미리 정해야 해서 메모리 크기가 동적이지 않습니다.
const stack = Array(MAX).fill(0);

function isEmpty() {
  return index < 0
  // || return stack.length === 0 ? true : false;
}

function push(element) {
  if(index >= (MAX - 1)) {
    console.log("Stack Overflow!😱");
    return false
  } else {
    index++;
    stack[index] = element;
    return true
  }
}

function pop() {
  if(index < 0) {
    console.log("Stack Underflow!😰")
    return 0;
  } else {
    let x = stack[index];
    index--;
    return x
  }
}

function peek() {
  if(index < 0) {
    console.log("Stack Underflow!😰")
    return 0
  } else {
    let x = stack[index];
    return x
  }
}

🕶️ 연결 리스트로 구현

물리 메모리 상에서는 순서와 관계없이 무작위로 공간을 할당하고, 새 요소를 추가할 때 새 노드를 만들고 현재 최상위 노드의 다음 포인터로 새 노드 요소를 연결하면 됩니다. 런타임 시 필요에 따라 메모리가 확장﹒축소될 수 있어서 Overflow가 불가능합니다. 하지만 포인터 관련으로 추가 메모리가 필요하고 연결 리스트의 특징으로 무작위 접근이 불가능합니다.

let pointer;

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

function isEmpty() {
  if(pointer === null) return true;
  else return false;
}

function push(value) {
  let newNode = new Node(value);
  
  if(pointer === null) pointer = newNode;
  else {
    let temp = pointer;
    pointer = newNode;
    newNode.next = temp;
  }
}

function pop() {
  let poped = Number.MIN_VALUE;
  if(pointer === null) console.log("Stack if Empty🤷🏻‍♀️");
  else {
    poped = pointer.data;
    pointer = pointer.next;
  }
  return poped;
}

function peek() {
  if(pointer === null) {
    console.log("Stack is empty🤷🏻‍♀️");
    return Number.MIN_VALUE;
  } else return pointer.data;
}