9. 스택

스택

• 한쪽 끝에서만 데이터를 삽입(Push)하거나 삭제(Pop)할 수 있는 구조
• 후입 선출(LIFO: Last In First Out) 구조

스택의 구조

 

삽입(push)

Top 포인터

: 가장 나중에 삽입되는 데이터 가리킴( = 삭제할 지점을 가리킴)

- 삽입하고 top 포인터를 1 증가 시켜야 함.

삭제(pop)

Top 포인터

: 가장 나중에 삽입되는 데이터 가리킴 (= 삭제할 지점을 가리킴)

- 삭제하고 top 포인터를 1 감소 시켜야 함.

 

스택에서 발생하는 오류

오버플로(overflow)

언더플로(underflow)

연습문제

<퀴즈>

나의 답변: 1.  X / 삭제는 가장 위의 top에 있는 데이터만 삭제가능하다?

나의답변: 2. O / 스택은 나중에 들어온 값이 먼저 나가게 되는 LIFO 구조이다.

나의답변: 3. O / pop()연산의 시간복잡도와 push()연산의 시간복잡도는 O(1)로 동일하다.

나의답변: 4. O / 가장 위에 있는 원소만 제거가 가능하다.

 

<문제1>

참고글: https://notepad96.tistory.com/25

나의 답변: set result = s.size()를 하면 스택에 담기는 값이 2 아닌가?

result += s.pop()하면 어떻게 되지? 그전에 뺀 값을 다시 더해주는건가...?

그렇게 가정하면 result = 2 + 20+ 15 = 37 , 37*2 = 74?

<문제2>

 

나의 답변:

solution(10)
0~9까지
solution(0) Hello
solution(1) ->(0)호출 Hello
solution(2)-> (0)호출 Hello (1) 호출 -> (0) 호출 Hello 
solution(3)-> (0) 호출 Hello (1) 호출 -> (0) 호출 Hello
 (2) 호출-> (0) 호출 Hello (1) 호출-> (0) 호출 Hello
solution(4)-> (0)호출 Hello
 (1) 호출 -> (0) 호출 Hello
 (2) 호출 -> (0) 호출 Hello (1) 호출 ->(0)호출 Hello
 (3) 호출 -> (0)호출 Hello (1)호출 -> (0)호출 Hello (2)호출 -> (1)호출 ->(0)호출 Hello
Hello: 15개?
'콜' 스택이 뭐지?

<문제3>

나의 코드:

#include<iostream>
using namespace std;

#define SIZE 10
class Stack
{
public:
	void init(char c)
	{
		this->name = c;
		cout << "Constructing stack " << name << endl;
		topIndex = -1; //가리키고 있는 top
	}
	void push(char ch) //삽입
	{
		if (topIndex >= 9) // 가득 차면
		{
			cout << "Stack " << name << " is full" << endl;
		}
		else
		{
			stackArr[++topIndex] = ch; // 전위연산자. 먼저 +=1 하고 대입함
		}
	}
	char pop() // 삭제
	{
		if (topIndex < 0) // 비었으면
		{
			cout << "Stack" << name << "is empty" << endl;
			return NULL; // 반환형이 char이므로
		}
		else
		{
			return stackArr[topIndex--]; //후위연산자. return하고난 뒤 topIndex -= 1;
		}
	}
public:
	int topIndex;
	char name;
	char stackArr[SIZE];
};

int main()
{
	Stack s1, s2;
	int i;
	s1.init('A');
	s2.init('B');

	s1.push('d'); // stackArr[0] = d; 
	s1.push('a'); // stackArr[1] = a;
	s1.push('t'); // stackArr[2] = t;
	s1.push('a'); // stackArr[3] = a; top:3

	s2.push('s'); // [0] = s;
	s2.push('t'); // [1] = t;
	s2.push('a'); // [2] = a;
	s2.push('c'); // [3] = c;
	s2.push('k'); // [4] = k; top:4

	for (i = 0; i < 5; i++) //0~4
		cout << "Pop s1: " << s1.pop() << '\n';
	cout << endl;
	for (i = 0; i < 5; i++) //0~4
		cout << "Pop s2: " << s2.pop() << '\n';
	return 0;

}

<문제4>

<도전 문제 1>

나의 코드:

#include <iostream>
#include <stack>

using namespace std;

void solution(int arr[])
{
	stack<int> s;
	for (int i = 0; i < 6; i++)
	{
		if (s.empty() == true || arr[i] > s.top()) //첫번째 수이거나 마지막 수보다 더 크다면
		{
			s.push(arr[i]);
			cout << arr[i] << " ";
		}

	}
}

int main()
{
	int arr[6] = { 10,30,20,50,60,15 };
	 solution(arr);
}

<도전 문제 2>

나의 코드:

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

int main()
{
	int input;
	cout << "10진수 값 입력: ";
	cin >> input;
	stack<int> s;
	while (input != 0)
	{
		s.push(input % 2);
		input /= 2;
	}

	while (!s.empty())
	{
		cout << s.top();
		s.pop();
	}





}

<도전 문제 3>

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

	stack<char> s;
void PrintComma(string num)
{
	int cnt = 0;
	for (int i = num.length() - 1; i >= 0; i--)
	{
		s.push(num[i]);
		cnt++;
		if (cnt%3 == 0)
		{
			s.push(',');
		}
	}
}
int main()
{
	string input;
	cin >> input;
	PrintComma(input);
	while (!s.empty())
	{
		cout << s.top();
		s.pop();
	}

}

계획

백준 스택 문제 풀기

• 다짐일: 4월 15일~
• 완수일: