Stack
stack은 데이터를 저장하는 자료구조 중 하나로 후입선출(Last In First Out) 의 구조를 따른다. 즉, 나중에 추가된 데이터가 먼저 제거되는 구조이다.
활용 예시: 함수 호출이나 재귀 알고리즘, 데이터를 저장하고 추출하는 데에 있어서 효율적이다.
call stack, 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록, 깊이 우선 탐색(DFS)
queue와 stack
시간 순서상 먼저 입력된게 가장 먼저 출력되는 선입선출 구조를 따르는 큐와 달리 스택은 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 형식으로 데이터를 저장한다.
push
stack에서 데이터를 추가 하는 것, push의 경우 스택의 맨 뒤에 데이터를 추가하면 완료되기 때문에 시간복잡도는 O(1)이다.
pop
stack에서 맨 위의 데이터를 추출 하는 것, pop의 경우 스택의 맨 뒤에 데이터를 삭제하면 완료되기 때문에 시간복잡도는 O(1)이다.
push와 pop모두 스택의 top(가장 나중의 데이터)에 원소를 추가하거나 삭제하는 형식으로 구현
구현
- stack 헤더를 포함하고, 타입을 지정해 스택 선언
#include <stack>
stack<int> stack;//정수형 스택- 스택에 데이터 추가하기
스택이름.push(데이터) 형태로 데이터 추가
stack.push(element)- 스택에 데이터 삭제하기
스택이름.pop(데이터) 형태로 스택의 top 데이터 삭제
stack.pop()- 스택의 제일 위(탑, top) 데이터 반환
스택이름.top() 형태로 제일 최상위 데이터 반환
stack.top()- 스택의 사이즈 반환
스택이름. size() 형태로 스택의 현재 사이즈 반환
stack.size()- 스택이 비어있는 지 확인
스택이름.empty() 형태로 스택이 비어있는 지 확인
stack.empty()- 두 스택의 내용 바꾸기
스택1과 스택2 두 스택의 내용을 바꾸고 싶은 경우, 내장된 swap 함수를 사용
swap(stack1 , stack2)stack과 Queue
Q. 스택 두 개를 이용해 큐를 구현하기
⭐️핵심: stack 두 개를 사용해서 enqueue ,dequeue를 구현하는 것에 초점을 맞춘다.
큐의 enqueue() 를 구현할 때 첫 번째 스택을 사용하고 dequeue()를 구현할 때 두번째 스택을 사용하면 큐를 구현할 수 있다.
- enqueue에 사용할 스택을 instack이라 부르고 dequeue에 사용할 스택을 oustack이라 가정
- enqueue():: instack에 push() 하여 데이터 저장 instack.push()
- dequeue()::
1. 만약 현재 outstack이 비어있다면 instack.pop()을 하고 oustack.push()를 하여 instack의 데이터를 outstack으로 모두 옮겨 넣는다. 이 결과로 가장 먼저 온 데이터가 outstack의 top을 차지하게 된다.
LIFO으로 정렬되어 있던 instack의 데이터들을 반대로 옮겨 넣어서 FIFO의 outstack을 만든다.- outstack.pop()으로 가장 먼저 왔던 데이터를 추출한다. (FIFO)
코드
#include <iostream>
#include <stack>
using namespace std;
class MyQueue {
private:
stack<int> instack;
stack<int> outstack;
public:
// 큐에 요소를 추가하는 함수
void enqueue(int x) {
instack.push(x);
}
// 큐에서 요소를 제거하고 반환하는 함수
int dequeue() {
if (outstack.empty()) {
// outstack이 비어있는 경우, instack의 모든 요소를 outstack으로 이동
while (!instack.empty()) {
outstack.push(instack.top());
instack.pop();
}
}
// outstack에서 요소를 꺼내 반환
int front = outstack.top();
outstack.pop();
return front;
}
};
int main() {
MyQueue q;
// enqueue 연산 수행
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
// dequeue 연산 수행
cout << q.dequeue() << endl; // 출력: 1
cout << q.dequeue() << endl; // 출력: 2
// enqueue 연산 수행
q.enqueue(4);
// dequeue 연산 수행
cout << q.dequeue() << endl; // 출력: 3
cout << q.dequeue() << endl; // 출력: 4
return 0;
}
시간복잡도
- enqueue(): instack.push() 한 번의 수행만 하면 되기 때문에 시간복잡도는 O(1)
- dequeue():
1. worst case: outstack이 비어있는 경우
-> instack에 있는 n개의 데이터를 instack.pop()한 다음 outstack.push()해주는 과정을 거쳐야 하기 때문에 총 2n번의 operation 이 실행되어야 하므로 O(n)의 시간 복잡도
2. outstack이 비어있지 않은 경우
outstack.pop()만 해주면 되기 때문에 O(1)의 시간복잡도를 갖는다.
=>이를 종합해봤을 때 amortized O(1)의 시간복잡도를 갖는다.
Q. ⭐️큐 두 개를 이용해 스택 구현하기
핵심: queue 두 개를 사용해 스택의 push, pop을 구현하는 것에 초점을 맞춰서 문제 해결
push에 사용할 큐는 q1, pop에 사용할 큐는 q2로 가정
- push():: q1으로 enqueue()하여 데이터 저장
- pop()::
- q1에 저장된 데이터의 갯수가 1 이하로 남을 때까지 dequeue()한 후, 추출된 데이터를 q2로 enqueue()한다. 결과적으로 가장 최근에 들어온 데이터를 제외한 모든 데이터는 q2로 옮겨진다.
- q1에 남아있는 하나의 데이터를 dequeue()해서 가장 최근에 저장된 데이터를 반환(LIFO)
- 다음에 진행될 pop()을 위와 같은 알고리즘으로 진행하기 위해 q1 과 q2의 이름을 swap
코드
#include <iostream>
#include <queue>
using namespace std;
class MyStack {
private:
queue<int> q1;
queue<int> q2;
public:
// 스택에 요소를 추가하는 함수
void push(int x) {
// q1에 요소 추가
q1.push(x);
}
// 스택에서 요소를 제거하고 반환하는 함수
int pop() {
// q1에 저장된 데이터의 갯수가 1 이하로 남을 때까지 q1의 모든 요소를 q2로 이동
while (q1.size() > 1) {
q2.push(q1.front());
q1.pop();
}
// q1에 남아있는 하나의 데이터를 제거하여 반환
int topElement = q1.front();
q1.pop();
// q1과 q2의 이름을 swap하여 다음 pop을 위해 준비
swap(q1, q2);
return topElement;
}
};
int main() {
MyStack s;
// push 연산 수행
s.push(1);
s.push(2);
s.push(3);
// pop 연산 수행
cout << s.pop() << endl; // 출력: 3
cout << s.pop() << endl; // 출력: 2
// push 연산 수행
s.push(4);
// pop 연산 수행
cout << s.pop() << endl; // 출력: 4
cout << s.pop() << endl; // 출력: 1
return 0;
}
시간복잡도
- push() : q1.enqueue()를 한번만 하면 되기 때문에 O(1)의 시간복잡도
- pop() : q1에 저장되어 있는 n개의 원소중 n-1 개를 q2로 옮겨야하기 때문에 O(n)
