Stack (스택)

Stack 란?

한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조
먼저 들어간 원소가 제일 나중에 나오는 FILO(First In Last Out) 자료구조
큐나 덱도 스택처럼 특정 위치에서만 원소를 넣거나 뺄 수 있는데 이들을 Restricted Structure라고 한다.

push & pop

Stack의 성질

• 원소의 추가가 O(1)
• 원소의 제거가 O(1)
• 제일 상단의 원소 확인이 O(1)
• 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
• 단 배열을 이용해 스택을 구현하면 기본적인 스택의 기능 이외도 제일 상단이 아닌 나머지 원소들의 확인/변경이 가능

 

Stack 구현 및 기능

배열 혹은 연결 리스트를 이용하여 구현할 수 있다.
배열을 이용한 stack의 구현이 더 쉽다.
스택을 배열로 구현할 때는 원소를 담은 큰 배열 한개와 인덱스를 저장할 변수 한 개만 필요하다.
Stack은 push, pop, top 메서드로 구성되어 있다.

#include <bits/stdc++.h>
using namespace std;

const int MX = 1000005;
int dat[MX];
int pos = 0;

void push(int x){

}

void pop(){

}

int top(){

}

void test(){
  push(5); push(4); push(3);
  cout << top() << '\n'; // 3
  pop(); pop();
  cout << top() << '\n'; // 5
  push(10); push(12);
  cout << top() << '\n'; // 12
  pop();
  cout << top() << '\n'; // 10
}

int main(void) {
	test();
}

내가 생각한 구현

package com.example.algo.stack;

public class StackImpl {

    private static final int MX = 1000005;
    private static int[] dat = new int[MX];
    private static int pos = 0;

    public void push(int x) {
        dat[pos++] = x;
    }
    public void pop() {
        if(pos > 0) pos--;
    }

    public int top() {
        return dat[pos-1];
    }

    public void test() {
        push(5); push(4); push(3);
        System.out.println(top());
        pop(); pop();
        System.out.println(top());
        push(10); push(12);
        System.out.println(top());
        pop();
        System.out.println(top());
    }

    public static void main(String[] args) {
        StackImpl stack = new StackImpl();
        stack.test();
    }
}

STL stack & JCF Stack

https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html

https://cplusplus.com/reference/stack/stack/

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x05/stack_example.cpp

 

강의 정리

배열과 pos라는 인덱스를 활용해 스택을 구현하는 법을 알아봤다.
stack에는 push, pop, top 메서드를 활용해서 요소들을 다룬다.
empty 상황에 주의하자.

 

활용법

• 수식의 괄호 쌍
• 전위/중위/후위 표기
• DFS
• Flood Fill