스택(Stack)
스택stack은 push 와 pop이라고 하는 두 종류의 조작이 가능 한 데이터 구조
LIFO(Last in First Out) : 마지막에 넣은 요소가 가장 먼저 나온다
push : 스택의 가장 윗부분에 데이터를 쌓는 조작 기능
pop : 스택의 가장 윗부분 데이터를 빼내는 조작 기능
스택을 조작하는 STL 라이브러리를 사용하는 언어는 상당히 많지만
c++ 라이브러리를 이용하여 알려주고자한다
- stack::pop : 가장 위에서 요소를 빼는 조작
- stack::push : 가장위에서 요소를 넣는 조작
- stack::top : 가장위에있는 요소를 확인하는 조작
- stack::empty : 데이터가 존재하는지
- stack::size : 데이터의 사이즈를 확인
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include<iostream>
#include<stack>
using namespace std;
int main()
{
stack<int> st;
st.push(1); //가장위에서부터 데이터를 삽입
st.push(2);
st.push(3);
cout << st.size() << endl; //3개가 있으니 3이 출력
while (!st.empty()) {
cout << st.top() << "\n"; // 3 -> 2 ->1 순차적으로 출력
st.pop();
}
}
|
cs |
큐(Queue)
큐queue는 스택과 마찬가지로 push pop이라는 두종류의 조작이 가능한 데이터 구조입니다.
큐는 스택과 반대로 가장 밑에서 데이터를 빼네는 작업을 하는 데이터 구조 입니다.
FIFO(First in First out) :즉 가장 먼저 넣은 요소가 가장 먼저 나오는 데이터구조
- queue::pop : 가장 아래에서 요소를 빼는 조작
- queue::push : 가장위에서 요소를 넣는 조작
- queue::front : 가장 아래 요소를 확인하는 조작
- queue::empty : 데이터가 존재하는지
- queue::size : 데이터의 사이즈를 확인
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include<iostream>
#include<queue>
using namespace std;
int main()
{
queue<int> q;
q.push(1); //가장위에서부터 데이터를 삽입
q.push(2);
q.push(3);
cout << q.size() << endl; //3개가 있으니 3이 출력
while (!q.empty()) {
cout << q.front() << "\n"; // 1 -> 2 ->3 순차적으로 출력
q.pop();
}
}
|
cs |
시간복잡도 분석
| Stack | Queue | |
| push | O(1) | O(1) |
| pop | O(1) | O(1) |
| top | O(1) | |
| front | O(1) | |
| size | O(1) | O(1) |
| empty | O(1) | O(1) |
두개의 스택으로 큐 구현하기
방법은 간단한다 두개의 스택을 st1과 st2
push : 작업은 st1을 넣어주면 된다
pop : st2에있는 데이터가 있으면 st2에 데이터를 위에서 꺼내주면 됩니다.
없다면 st1에 있는 모든 데이터를 st2에 넣어주면됩니다. 넣어 준후 st2에 있는 데이터를 위에서 꺼내줍니다.
empty : st1, st2가 둘다 데이터가 비어있는지 확인하면 됩니다.
front : pop과 마찬가지입니다. st2에 있는 데이터가 있다면 st2에있는 top을 보여주면됩니다.. 그러나 없다면
st1에 있는 데이터를 st2에 전부 옮겨준후 top을 해주면 됩니다.
size : st1과 st2의 사이즈를 더한값을 확인하면 됩니다.
다음 그림은 스택 2개로 큐를 구현했을때 동작과정의 그림입니다.
큐에 데이터가 1,2,3 이 들어가 있을때 어떻게 데이터가 빠지고 넣는지 동작하는 과정을 보여줍니다.
전체 pop하기 위해선 st2에 있는 데이터를 전부 빼낸후 st2가 비어있으면 st1에 있는 데이터를 st2에 옮긴후 다시 pop해주면 됩니다.
1,2,3,4,5가 순차적으로 출력되면서 pop이 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include<iostream>
#include<stack>
using namespace std;
class Queue{
private:
stack<int>st1, st2;
public:
void push(int data) {
st1.push(data);//push 작업은 st1에 데이터를 넣음
}
void pop() {
if (st2.empty()) {//st2가 비어있다면 st1에있는데이터를 모두 꺼내서 st2에 넣음
while (!st1.empty()) {
st2.push(st1.top());
st1.pop();
}
}
st2.pop();
}
int front() {
if (st2.empty()) {//st2가 비어있다면 st1에있는데이터를 모두 꺼내서 st2에 넣음
while (!st1.empty()) {
st2.push(st1.top());
st1.pop();
}
}
return st2.top();
}
int size() {
return st1.size() + st2.size();//데이터의 갯수는 2개가 가지고있는 데이터의 갯수의합
}
bool empty() {
return st1.empty() && st2.empty();//둘다 비었는지 확인
}
};
int main()
{
Queue q;
q.push(1);
q.push(2);
q.push(3);
cout << q.front() << "\n"; //1이출력
q.pop();
q.push(4);
q.push(5);
cout <<"사이즈 : " << q.size() << endl; //사이즈 4출력
while (!q.empty()) {
cout << q.front() << "\n"; //2 -> 3 -> 4 -> 5 출력
q.pop();
}
}
|
cs |
두개의 큐로 스택 구현하기
두개의 큐를 q1,q2라 하겠다
top: 과정을 생략하겠습니다. -> top이 pop과정까지 한꺼번에 할수있도록
push : q1에 넣는다
pop : q1안에 데이터가 하나가 될때까지 q2에 넣어준후 q1에 있는 데이터를 꺼내준후 q2에 있는 데이터를 q1에 넣어줌
empty :q1이 데이터가 있는지 확인
size : q1에 있는데이터 사이즈 확인
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include<iostream>
#include<queue>
using namespace std;
class Stack {
private:
queue<int> q1, q2;
public:
void push(int data) {
q1.push(data);
}
int pop() {
while (q1.size() != 1) {
q2.push(q1.front());
q1.pop();
}
int t = q1.front();
q1.pop();
while (!q2.empty()) {
q1.push(q2.front());
q2.pop();
}
return t;
}
int size() {
return q1.size();
}
bool empty() {
return q1.empty();
}
};
int main()
{
Stack st;
//1,2,3 삽입
st.push(1);
st.push(2);
st.push(3);
while (!st.empty()) {
cout << st.pop() << "\n";// 3-> 2-> 1출력
}
}
|
cs |
이것을 그림으로 표현하자면
와같이 됩니다.
그럼 시간복잡도를 분석해 볼까요?
| 2개의 queue로 -> Stack | 2개의 stack -> Queue | |
| push | O(1) | O(1) |
| pop | O(n) | O(1) |
| top | O(1) | |
| front | O(1) | |
| size | O(1) | O(1) |
| empty | O(1) | O(1) |
pop에서 차이가 나옵니다.
2개의 큐로 스택을 구현할때
pop같은경우는 q1에 n개의 데이터가 있을경우 하나만 꺼내기위해 q2에 데이터를 옮기고
마지막 하나가 될때 그것을꺼내준후 다시 q2에 있는 데이터를 q1에 넣기때문에 O(n) 매우 느릴수밖에 없습니다.
2개의 스택으로 큐를 구현할때 :
스택 st1에 n개의 데이터가 있다고 가정해봅시다. st2는 비어있습니다.
하나를 꺼낼때 n개의 데이터를 st2에 전부 넣어 st2에 꺼내줍니다. 이때는 n번의 연산을 진행하지만
다시 m번은 넣고 몇번을 꺼내더라도 st2가 데이터가 없을때까지 한번에 꺼내주기때문에 평균적으로 O(1)의 시간을 낼수있습니다.
'Computer Science > 자료구조' 카테고리의 다른 글
| 자료구조 hash (0) | 2022.04.22 |
|---|---|
| [CS 면접] 자료구조 정렬의 종류, 정렬의 차이 (0) | 2022.03.24 |
| [CS 자료구조] 그래프와 트리의 차이 (0) | 2022.03.07 |
| [자료구조] List → ArrayList vs LinkedList (0) | 2022.01.20 |
| [자료구조] Queue 구현하기 (0) | 2020.08.08 |
