Notice
Recent Posts
천천히 빛나는
알고리즘 : 자료구조(1) 스택 (Stack) (C++로 구현) 본문
스택 (Stack)
스택(stack)은 쌓아놓은 더미라는 의미 그대로, 책상에 쌓여있는 책을 생각하면 된다.
가장 큰 특징은 LIFO(Last In First Out-후입선출)이다. 제일 최근에 들어온 데이터가 가장 먼저 나가는 것이다. 편의점 아르바이트를 해보신 분들이 아는 선입선출과 반대되는 용어이다. 여기서 선입선출에 해당되는 자료구조는, 뒤에서 다룰 큐 (Queue)이다.
문서 편집기에서 되돌리기를 했을 때 바로 직전에 실행한 작업이 취소되는 것을 생각하면 된다.
push : 스택의 top에서 데이터 삽입
pop : 스택의 top에서 데이터 삭제
stack top : 스택에서 입출력이 이루어지는 부분
element : 스택에 저장되는 것
full stack : 포화 상태의 스택
스택의 기본 용어는 이렇게 된다.
class Stack {
private:
int stack_size = 100;
int top = -1;
int* stack;
public:
Stack();
~Stack();
void push(int element);
void pop();
void show_stack();
};
Stack::Stack() {
stack = new int[stack_size];
}
Stack::~Stack() {
delete[] stack;
}
c++을 이용해서 차근차근 구현해보도록 하겠다. 나는 stack의 크기를 100으로 설정해주었으나 입력받는 것으로 설정해도 괜찮다.
1. Push & Pop
void push(int x) {
if (top >= n - 1) // 스택이 꽉 찼음
cout << "Stack Over flow!\n";
else
stack[++top] = x;
}
void pop() {
if (top <= -1) // pop할 요소가 없음
cout << "Stack Underflow!\n";
else
cout << "The popped element is " << stack[top--] << "\n";
}
2. Show Stack
void Stack::show_stack() {
if (top >= 0) {
cout << "Stack elements :";
for (int i = top; i >= 0; i--)
{
cout << stack[i] << " ";
}
cout << "\n";
}
else {
cout << "Stack is empty\n";
}
}
모든 요소를 보여주는 함수이다.
3. 최종 코드
int main() {
Stack s;
int ch=0, val;
cout << "1) Push in stack\n";
cout << "2) Pop from stack\n";
cout << "3) Display stack\n";
cout << "4) Exit\n";
while (ch != 4) {
cout << "Enter your choice: ";
cin >> ch;
switch (ch) {
case 1: {
cout << "Enter value to be pushed: ";
cin >> val;
s.push(val);
break;
}
case 2: {
s.pop();
break;
}
case 3: {
s.show_stack();
break;
}
case 4: {
cout << "Exit" << endl;
break;
}
default: {
cout << "Invalid Choice" << endl;
}
}
}
return 0;
}
간단하게 구현을 해보았다.
4. STL을 이용한 Stack 구현
#include <stack>
stack<int> stack;
c++ STL을 이용해서 Stack을 구현할 수도 있다.
stack.push(element); // 데이터 추가
stack.pop(); // 데이터 삭제
stack.top(); // 가장 위에 있는 데이터 반환
stack.size(); // 현재 사이즈 반환
stack.empty(); // 비어있는지 반환
swap(stack1 , stack2); // 스택1과 스택2의 내용 바꾸기
이와 같은 함수를 사용할 수 있다.
https://better-tomorrow.tistory.com/entry/c%EB%A1%9C-stack-%EA%B5%AC%ED%98%84STL-without-STL
참고한 티스토리이다!
활용
재귀 알고리즘
DFS 알고리즘
'STUDY > ALGORITHM' 카테고리의 다른 글
알고리즘 : 자료구조(3) 덱 (Deque) (C++로 구현) (1) | 2023.09.19 |
---|---|
알고리즘 : 자료구조(2) 큐 (Queue) (C++로 구현) (0) | 2023.09.18 |
알고리즘 : 정렬이란? (C++로 구현) (0) | 2023.09.16 |
알고리즘 : 브루트 포스란 (0) | 2023.09.10 |
알고리즘: 시간 복잡도란 (1) | 2023.09.08 |