[Algorithm][Stack] 스택 개념 및 구현

순서

I. 스택(Stack)이란?

II. 스택의 기본 개념

III. 구현
1. C++ STL/ 2. 직접구현

 

I. 스택(Stack) 이란?

스택은 자료구조이다.

큐(Queue) 가 선입선출(FIFO)의 방식이였다면,
스택(Stack) 은 후입선출(LIFO)의 방식이다.

단어 그대로 물건을 "쌓는" 형태인데
물건을 아래에서 부터 위로 쌓으면
뺄 때는 위에서 부터 아래로 빼는 것과 같은 원리라고 볼 수 있다.

주로 "실행취소", "웹페이지 뒤로가기", "계산기" 등등 많은 곳에서 활용한다.

 

II. 스택의 기본 개념

위에서 말한 것 처럼 스택은 후입 선출의 방식을 갖는다.
이를 그림으로 표현하면 다음과 같다.

Stack의 push, pop 구조

그림에서 처럼 우리는 Stack을 구현할 때 push()라는 함수와 pop()이라는 함수를 사용할 것이다.

또한 push와 pop은 데이터를 넣고 빼는 과정이므로,
현재 맨 위 데이터를 참조하는 top()함수도 필요 할 것이다.

스택은 활용도가 굉장이 높고, 알고리즘 문제에서도 응용이 많이 된다.

간단한 개념에 비해 활용이 어려우므로 많은 문제를 풀어보는 것이 좋은 것 같다ㅠㅠ

---

III. 구현

---

1. C++ STL

#include <iostream>
#include <stack>
using namespace std;

// 스택 선언
stack<int> S;

int main() {

    // 0~9 까지 저장
	for (int i = 0; i < 10; i++) {
		printf("push %d\n", i);
        //S.push()로 추가
		S.push(i);
	}
	cout << endl;
    
    // 저장된 데이터의 길이 출력
    printf("Stack size : %d\n",S.size());
    
    // 스택 비우기
	for (int i = 0; i < 11; i++) {
		// 스택이 비어있는 것 확인 S.empty()
		if (S.empty()) {
			cout << endl << "Stack is already empty()" << endl;
		}
        // 남아있으면 S.top()으로 참조 및 S.pop()으로 제거
		else {
			cout << S.top() << " ";
			S.pop();
		}
	}

	return 0;
}

1. 선언 : stack<자료형> Varname;

2. 데이터 추가 : Varname. push(데이터)

3. 맨 위 데이터 참조 : Varname. top()

4. 맨 위 데이터 제거 : Varname. pop()

5. 비어있는지 확인 : Varname. empty()

6. 사이즈 확인 : Varname. size()

---

2. 직접구현

#include <stdio.h>
#include <iostream>

int MAXLEN = 10;
int S[MAXLEN]; // 길이는 사용자 설정.
int curidx{-1};

// push함수
void Spush(int data){
    curidx++;
    
	if(curidx == MAXLEN) {
    	printf("Exceed stack size\n");
        return;
    }
    else    S[curidx] = data;
}

// pop 함수
void Spop(){
    if( curidx == -1){
        printf("No data in stack\n");
        return;
    }
    else    curidx--;
}

// top함수
int Stop(){
    if(curidx == -1){
        printf("No data in stack\n");
        return -1;
    }
    else return S[curidx];
}

// size() 함수
int Ssize(){
    return curidx+1;
}

// empty()함수
int isSempty(){
    if (!(curidx+1)) return 1;
    else return 0;
}

사실 함수들을 구현하는 것은 자기 스타일대로 구현하면 된다.

나 같은 경우는 인덱스로 판단하는 것이 편해서 인덱스를 기준으로 구현을 진행하였다.

하지만 단점은 Array로 스택을 만들게 되면 크기를 처음에 지정해줘야 하는데, 

이것이 불편하다면 STL의 vector를 사용해도 된다.
그런데 STL로 vector쓰면서 stack구현할바에,,, 그냥 STL stack을...