<div id="readability-page-1" class="page"><div><h2 id="스택"><a href="#%EC%8A%A4%ED%83%9D" aria-label="스택 permalink"></a>스택</h2>
한 쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조
<img src="https://upload.wikimedia.org/wikipedia/commons/2/29/Data_stack.svg" alt="https://upload.wikimedia.org/wikipedia/commons/2/29/Data_stack.svg">
<ul>
<li>FILO (First In Last Out)</li>
<li>
Restricted Structure - 큐, 스택, 덱
<ul>
<li>특정 위치에서만 원소를 넣거나 뺄 수 있음</li>
</ul>
</li>
<li>원소의 추가와 제거, 최상단의 원소 확인 : O(1)</li>
<li>최상단이 아닌 나머지 원소의 확인/변경이 원칙적으로 불가능</li>
</ul>
<h2 id="구현"><a href="#%EA%B5%AC%ED%98%84" aria-label="구현 permalink"></a>구현</h2>
배열 or 연결리스트를 통해 구현 가능
by 배열
<div data-language="cpp"><pre><code>const int MX = 1000005;
int dat[MX];
int pos = 0;

void push(int x) { 
	dat[pos++] = x;
}
void pop() { 
	// 나중에 push가 발생하면 어짜피 그 때 들어올 값으로 덮어져서 해당 pos값 자체는 변경하지 않아도 O
	pos--;
} 
int top() { 
	return dat[pos-1];
}
void test() { }
int main(void) {
	test();
}</code></pre></div>
<h2 id="stl-stack"><a href="#stl-stack" aria-label="stl stack permalink"></a>STL stack</h2>
<div data-language="cpp"><pre><code>stack&lt;int&gt; s; // 선언
s.push(10); // item을 stack에 삽입, Vector의 addElement(item)과 동일
s.pop(); // Stack top에 있는 item 삭제
s.size(); // stack 사이즈 반환
s.top(); // top item 반환</code></pre></div>
<h2 id="수식의-괄호-쌍"><a href="#%EC%88%98%EC%8B%9D%EC%9D%98-%EA%B4%84%ED%98%B8-%EC%8C%8D" aria-label="수식의 괄호 쌍 permalink"></a>수식의 괄호 쌍</h2>
<h2 id="문제-해결-방법"><a href="#%EB%AC%B8%EC%A0%9C-%ED%95%B4%EA%B2%B0-%EB%B0%A9%EB%B2%95" aria-label="문제 해결 방법 permalink"></a>문제 해결 방법</h2>
<ol>
<li>여는 괄호가 나오면 스택에 추가</li>
<li>
닫는 괄호가 나왔을 경우,
<ol>
<li>스택이 비어있으면 올바르지 않은 괄호쌍</li>
<li>스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않는 괄호 쌍</li>
<li>스택의 top이 짝이 맞는 괄호일 경우 pop</li>
</ol>
</li>
<li>모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호 쌍, 남아있지 않으면 올바른 괄호 쌍</li>
</ol></div></div>

Seulog💘

이예슬

스택
한 쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조
FILO (First In Last Out)
Restricted Structure - 큐, 스택, 덱
특정 위치에서만 원소를 넣거나 뺄 수 있음
원소의 추가와 제거, 최상단의 원소 확인 : O(1)
최상단이 아닌 나머지 원소의 확인/변경이 원칙적으로 불가능
구현
배열 or 연결리스트를 통해 구현 가능
by 배열
const int MX = 1000005;
int dat[MX];
int pos = 0;
void push(int x) { 
	dat[pos++] = x;
}
void pop() { 
	// 나중에 push가 발생하면 어짜피 그 때 들어올 값으로 덮어져서 해당 pos값 자체는 변경하지 않아도 O
	pos--;
} 
int top() { 
	return dat[pos-1];
}
void test() { }
int main(void) {
	test();
}
STL stack
stack<int> s; // 선언
s.push(10); // item을 stack에 삽입, Vector의 addElement(item)과 동일
s.pop(); // Stack top에 있는 item 삭제
s.size(); // stack 사이즈 반환
s.top(); // top item 반환
수식의 괄호 쌍
문제 해결 방법
여는 괄호가 나오면 스택에 추가
닫는 괄호가 나왔을 경우,
스택이 비어있으면 올바르지 않은 괄호쌍
스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않는 괄호 쌍
스택의 top이 짝이 맞는 괄호일 경우 pop
모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호 쌍, 남아있지 않으면 올바른 괄호 쌍

Stack

댓글