스택(Stack)

스택(Stack)

:한쪽 끝에서 자료를 넣고 뺄때 쓰이는 자료구조

 목록의 한쪽끝을 Top이라고 할때, Top에서 Push와 Pop이 이루어진다. 즉, LIFO(Last In First Out) 형식이다.

 원칙적으로 중간에서 삭제,추가가 불가능하며 Top에 위치한것만 알 수 있다.

 

<출처: 위키백과>

 

일차원 배열로 구현이 가능하다.

int stack[1000];
int size = 3; //스택의 크기
-----------------------------------------------------

//push
void push(int data){
	stack[size] = data;
    size += 1
}
-------------------------------------------------------

//pop
void pop(int data){
	stack[size] = data;
    size -= 1
}

 

일일히 구현할수도 있지만 제공해주는 라이브러리가 있기때문에 라이브러리 사용을 추천한다.

Java

    - Stack

        - import java.util.*;

             - Stack<T> stack = new Stack<>();

             - push() : 스택에 삽입

             - pop() : 스택에서 가장 위에 있는 값 반환하고 없앰

             - peek() : 스택에서 가장 위에 있는 값 반환

             - isEmpty() : 스택이 비어있는지를 반환

             - size() : 스택에 있는 요소의 크기 반환

---

 

스택의 LIFO 성질을 이용하여 다양한 알고리즘을 구현할수 있다. 대표적인 몇가지를 살펴보겠다.

1. 단어뒤집기

2. 괄호문자열

3. 스택수열

4. 에디터

 

1.  단어뒤집기

         N개의 문장이 주어졌을때 단어를 모두 뒤집어야한다.

        단어의 순서를 바꿀 수 없고, 영어알파벳으로만 이루어져있다.

             -> 알파벳을 스택에 넣었다가 빼면 역순이 된다. 

             -> 공백이나 문자열 끝이면 스택에서 모두 꺼내서 역순을 만든다.

             -> 시간복잡도는 push O(1),  pop  O(1)  이니 넣었다가 빼면 O(N)이된다.

 

스택으로 단어 뒤집기

2.  괄호

올바른 괄호문자열을 찾아야 하는 문제

•   괄호문자열 : ( 와 ) 로만 이루어진 문자열

•   올바른 괄호문자열 : (), ()(())  , ((()))     ->   (), ()(())  , ((()))    

•   짝이 맞는 괄호문자열.  최종 스텍이 비어있는게 옳바른 괄호문자열  (() 는 올바르지 않다.

    항상 가장 가까운 여는괄호 닫는괄호가 짝을 이룬다      ex)  (()())

 

    1) 닫는괄호 앞에 있는 여는괄호                               ex)  (()())

    2) 다른 여는괄호와 짝이 아닌 닫는괄호                     ex)  (()())

    3) 1,2 해당시 가장 가까운 여는괄호와 짝을짓는다.       ex)  (()())

 

    단어의 길이가 N이면 시간복잡도는 O(N^2)  (최악의 경우 앞에있는것을 다 검사할수 있어서)

 

2-1.스택 구현으로 풀기 

        ( 일경우 ( push한다.

        ) 일경우 ) 가아닌지 맞는지 확인후 ( pop한다.

 

2-2.스택의 크기로 풀기

      스택을 구현하지 않아도 스택의 크기로 구현가능함 

using namespace std;
string valid(string s){
	int cnt = 0;   //스택의 크기
	for (int i = 0; i<s.size(); i++){
		if(s[i] == '(') {        //여는괄호일때
	 		 cnt += 1;	
		} else {                //닫는괄호일때
			 cnt -= 1;
		}
        
	if (cnt < 0){
	return "NO"   //여는 괄호 부족
	}
	}
//모든 과정이 끝난후 옳바른 스텍이 비었는지 확인
	if(cnt == 0) {
		return "YES";
	} else {
		return "NO";
    }
}

 

3. 수열

        1.....N 까지의 숫자를 스택에 넣었다가 뺌으로 수열A를 만들 수 있다.

        pop되는 순서대로 수열A가 만들어진다

        시간복잡도는 push O(1),  pop  O(1)  이니 넣었다가 빼면 O(N)이된다.

        ex)  A = [4,3,6,8] 일때  ++++--++-++- 로 만들 수 있다

 

스택으로 수열 만들기

4. 에디터

•   커서 : 문장의 맨앞,뒤,중간 임의의 곳에 위치할 수 있다.

•   L  : 왼쪽으로 한칸 옮김           abc|xz  -> ab|cxz

•   D : 오른쪽으로 한칸 옮김        abc|xz  -> abcx|z

•   B : 왼쪽으로 한칸 삭제           abc|xz  -> ab|xz

•   P d : 커서왼쪽에 글자 추가     abc|xz  -> abcd|xz

 

  문자열의 길이가 M이라 하였을때,

  문자열로만 구현을 한다면 N(M^2)나 걸림....3600억  (1초=1억)

 

  커서를 기준으로 왼쪽스택 오른쪽스택으로 나누어서 pop, push 한다.

  시간복잡도는 L,D,B,P 각각 O(1) 씩 걸린다.

  명령을 수행하는데 걸리는 시간은 총 O(M)이 된다.

 

스택의 L연산 

 

이문제는 링크드 리스트로도 구현 가능하다. 

 

---

 

 

<참고>

백준사이트

gorani95.tistory.com/150