[C++] 자료구조 - 스택 (Stack)

스택의 개요   

 

stack 컨테이너는 LIFO( Last In First Out)방식의 컨테이너를 구현한 템플릿 클래스다.

컨테이너지만 정확하게는 어댑터 컨테이너라고 불린다.

 

 

 

 

스택의 초기화   

#include <stack>
stack<int> s1; // 단일 스택 초기화

stack<pair<int, int>> s2; // 페어 스택 초기화

 

 

 

 

스택의 함수   

 

삽입

원소를 최상단에 삽입한다.

s.push(element)

 

삭제

최상단 원소를 제거한다.

s.pop()

 

참조 

최상단 원소를 반환한다.

s.top()

 

사이즈

현재 들어있는 원소의 개수를 int형으로 반환한다.

s.size()

 

비어있는지 확인

s.empty()

 

 

 

스택 예제   

 

기본예제

#include <iostream>
#include <stack>

using namespace std;

int main()
{
	stack<int> sung;

	sung.push (10);
	sung.push (20);
	sung.push (30);

	while (!sung.empty()) // 스택의 원소가 남아있지 않을때까지 반복
	{
		cout << sung.top() << endl;
		sung.pop();
	}

	cout << boolalpha << "스택이 비어 있나요? : " << sung.empty() << endl;

	return 0;

}

 

 

스택 구현   

 

생성자 Stack()

int형 변수를 매개변수로 받고, 필드에 새롭게 들어온 변수를 넣어, 그 사이즈만큼 배열을 만들고 
그 배열을 가리키는 포인터 변수인 stack을 정의한다.그리고 _top을 -1로 초기화한다. (-1은 비어있다는 의미인데, 그 이유는 스택에 처음 들어온 값을 0번째 인덱스로 나타내기 위함이다.)

소멸자 ~Stack()

delete[] 문을 이용해서 연속적으로 할당된 메모리를 해제해준다.

IsEmpty()

-1(비어있음)이면 true를 반환, 그렇지 않으면 false를 반환해준다.

Pop()

_top에 -1한 값을 반환시켜준다, 만약 비어있는채로 pop()을 하면 return한다.

push()

최상단 인덱스에 +1을더한 인덱스로 접근해서 값을 반환한다, 만약 스택이 다 찼으면 return한다.

Top()

스택이 비어있으면 -1을 반환하고, 최상단 인덱스로 접근해서 값을 반환시킨다.

Size()

top의 초기값은 -1로 비어있는 상태이므로, 스택에 몇개 들어있는지 확인하려면 top에 +1을해서 반환시키면 된다.

 

Stack.h

#pragma once

class Stack
{
public:
    Stack(int size);
    ~Stack();

    // 스택에 value를 삽입합니다.
    // 다 찬 경우 아무것도 하지 않습니다.
    void Push(int value);

    // 스택에서 데이터를 꺼내고, 반환합니다.
    // 스택에 데이터가 없는 경우 -1를 반환합니다.
    int Pop();

    // 스택에 가장 위에 있는 데이터를 반환합니다.
    // 스택에 데이터가 없는 경우 -1를 반환합니다.
    int Top();

    // 스택이 비었다면 true, 아니면 false입니다.
    bool IsEmpty();

    // 현재 원소의 수를 반환한다.
    int Size();

private:
    int _top;
    int _arrSize;
    int* stack;
};

 

stack.cpp

#include "Stack.h"
#include <iostream>

using namespace std;

Stack::Stack(int size) 
{
    _arrSize = size;
    stack = new int[_arrSize];
    _top = -1;
}

Stack::~Stack()
{
    delete[] stack;
}

bool Stack::IsEmpty()
{
    if (_top == -1)
    {
        return true;
    }

    else
    {
        return false;
    }
}

int Stack::Pop() 
{
    if (IsEmpty() == true)
    {
        return;
    }
    else
    {
        return stack[_top--];
    }
}

void Stack::Push(int value) 
{
    if (Size() == _arrSize)
    {
        return;
    }
    else
    {
        ++_top;
        stack[_top] = value;
    }
}

int Stack::Top()
{
    if (IsEmpty() == true)
    {
        return -1;
    }
    else
    {
        return stack[_top];
    }

}

int Stack::Size()
{
    return _top + 1;
}

 

main.cpp

#include <iostream>
#include "Stack.h"

using namespace std;
int main() 
{
    Stack stack(5);
    stack.Push(1);
    stack.Push(2);
    stack.Push(3);
    stack.Push(4);
    stack.Push(5);
    stack.Push(6);

    while (!stack.IsEmpty())
    {
        cout << stack.Top() << endl;
        stack.Pop();
    }
    stack.Pop();

    cout << "\n";

    cout << "스택이 비어있나요? : " << boolalpha << stack.IsEmpty() << endl;

    return 0;
}

출력 결과

 

백준 10828

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
	vector <int> stack;
	int length;

	cin >> length;

	for (int i = 0; i < length; i++)
	{
		string command;
		cin >> command;

		if (command == "push")
		{
			int num;
			cin >> num;
			stack.push_back(num);
		}

		else if (command == "pop")
		{
			if (stack.empty())
			{
				cout << "-1" << endl;
			}
			else
			{
				cout << stack.back() << endl;
				stack.pop_back();
			}
		}

		else if (command == "size")
		{
			cout << stack.size() << endl;
		}

		else if (command == "empty")
		{
			cout << stack.empty() << endl;
		}

		else if (command == "top")
		{
			if (stack.empty())
			{
				cout << "-1" << endl;
			}
			else
			{
				cout << stack.back() << endl;
			}
		}

	}
}

 

백준 10773

#include <iostream>
#include <stack>

using namespace std;

int totalNum = 0;

int main()
{
    std::stack<int> s;

    int action;
    cin >> action;

    while (action > 0)
    {
        int JaminNum;
        cin >> JaminNum;

        if (JaminNum == 0 && action != 0)
        {
            s.pop();
        }

        if (JaminNum != 0)
        {
            s.push(JaminNum);
        }

        --action;
    }

    int newSize = s.size();

    for (int i = 0; i < newSize; i++)
    {
        totalNum += s.top();
        s.pop();
    }

    cout << totalNum << "\n";

}

 

백준 9012

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int BracketCnt = 0;
bool isBracketClose = false;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int action;
    cin >> action;
    std::stack<char> s;

    int size = 0;
    while (action > 0)
    {
        // 1. 입력
        string Brackets;
        cin >> Brackets;


        // 2. 처리
        for (int i = 0; i < Brackets.size(); i++)
        {
            s.push(Brackets[i]);
        }

        size = s.size();

        // 3. 출력
        for (int i = 0; i < size; i++)
        {
            if (s.top() == '(')
            {
                if (i == 0 || BracketCnt == 0)
                {
                    // 첫번째 부터 (가 나오면 NO를 반납
                    cout << "NO" << "\n";
                    isBracketClose = true;
                    break;
                }

                // )모양 카운트가 1이상이면 ( 카운트를 1없애준다.
                else if (BracketCnt > 0)
                {
                    --BracketCnt;

                    if (BracketCnt < 0)
                    {
                        cout << "NO" << "\n";
                        isBracketClose = true;
                        break;
                    }
                }
            }

            if (s.top() == ')')
            {
                ++BracketCnt; // )
            }
            s.pop();
        }

        if (!isBracketClose)
        {
            if (BracketCnt > 0)
            {
                cout << "NO" << endl;
            }

            if (BracketCnt == 0)
            {
                cout << "YES" << endl;
            }
        }

        BracketCnt = 0;
        isBracketClose = false;

        while (!s.empty())
        {
            s.pop();
        }
        --action;
    }

}

 

백준 4949

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);


    while (1)
    {
        // 1. 입력
        std::string inputStr;
        getline(cin, inputStr);


        // 글자가 하나고 점일때 탈출..
        std::stack<char> s;
        bool result = true;

        if (inputStr == ".")
        {
            break;
        }

        // // 2. 처리 : 스택에 요소를 담는다.
        for (int i = 0; i < inputStr.length(); i++)
        {
            if (inputStr[i] == '(' || inputStr[i] == '[')
            {
                s.push(inputStr[i]);
            }

            if (inputStr[i] == ')')
            {
                if (s.empty() || s.top() == '[')
                {
                    result = false;
                }
                else
                {
                    s.pop();
                }

            }

            if (inputStr[i] == ']')
            {
                if (s.empty() || s.top() == '(')
                {
                    result = false;
                }
                else
                {
                    s.pop();
                }
            }
        }

        if (s.empty() && result)
        {
            cout << "yes" << '\n';
        }
        else
        {
            cout << "no" << '\n';
        }

    }
    return 0;
}

 

백준 17928

#include <iostream>
#include <stack>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    std::stack<int> s1; // 조건에 따라 담는 스택
    std::stack<int> s2; // 인덱스 담는 스택

    int length;

    // 1. 입력
    cin >> length;
    int* SeqArray = new int[length]; // 배열 초기화

    int stackNum = 0; // 받을 숫자 초기화
    for (int i = 0; i < length; i++)
    {
        SeqArray[i] = -1;

        cin >> stackNum; // 넘버를 입력받는다.

        if (i == 0)
        {
            s1.push(stackNum);
            s2.push(i);
        }

        // 현재 최상단에 있는 스택이 들어오는 값보다 컸을때

        if (s1.top() > stackNum)
        {
            s1.push(stackNum);
            s2.push(i);
        }

        else if (s1.top() <= stackNum)
        {
            while (!s1.empty() && s1.top() < stackNum)
            {
                SeqArray[s2.top()] = stackNum;
                s1.pop();
                s2.pop();
            }

            s1.push(stackNum);
            s2.push(i);
        }

    }

    // 3. 출력
    for (int i = 0; i < length; i++)
    {
        cout << SeqArray[i] << ' ';
    }


    // 4. 메모리 해제
    while (!s1.empty())
    {
        s1.pop();
        s2.pop();
    }

    delete[] SeqArray;

    return 0;
}