[자료구조] Stack, Queue

Stack

Stack은 자료구조 중 하나로, 단어 자체는 '쌓다', '더미' 의 뜻을 갖고 있다.

접시 더미와 비슷한 형태를 띄며. 나중에 들어온 것이 먼저 나가는 LIFO(Last In First Out) 구조를 갖고있다.

맨 위의 데이터를 top이라고 칭하는 경우가 많다.

 

 

 

스택의 4가지 기능

 

1. pop() : 마지막에 넣은 데이터를 가져오면서 지우는 것

2. push() : 새로운 데이터를 쌓아 올리는 것

3. peek() : 맨 마지막 데이터를 보는 것(맨 위)

4. isEmpty() : 스택에 데이터가 있는지 없는지 보는 것

5. size() : 스택의 사이즈를 확인하는 것 (스택 구현방법에 따라 존재여부 달라짐)

 

스택의 특징

 

1. 맨 위의 데이터만 알 수 있다.

2. 중간의 데이터는 알 수 없다......적어보니 위 특징이랑 같네여

 

스택의 시간복잡도

 

1. pop() : O(1) - 맨 위에 넣으니까!

2. push() :  O(1) - 맨 위에서 빼니까!

3. peek() : O(1) - 맨 위거 보니까!

4. isEmpty() : O(1) - top이 있는지 없는지만 보면 되니까!!

 

Queue

 

Queue는 자료구조 중 하나로 선착순 줄과 비슷한 형태를 띄며. 먼저 들어온 것이 먼저 나가는 FIFO(First In First Out) 구조를 갖고있다.

Queue 찾다가 알게 되었는데 게임에서 큐잡혔다의 큐가  Queue인것을 깨달았다.......... 먼저 돌린사람이 먼저하고.. 아하....!

맨 앞의 데이터를 front, 맨 뒤의 데이터를 rear라고 칭한다 

겜하고싶다... 롤.. 오버워치...배그...레식... 뭐든...

 

 

 

큐의 기능

 

1. enqueue() : 큐의 맨 뒤에 데이터를 넣는다.

2. dequeue() : 큐의 맨 앞 데이터를 가져오면서 지운다.

3. empty() : 큐가 비어있는지 확인한다.

4. getfront() : 맨앞 데이터를 확인한다.

5. size() : 큐의 사이즈를 확인한다.

 

큐의 시간복잡도

 

1. enqueue() : O(1) - 맨 뒤에 넣으니까!

2. dequeue() :  O(1) - 맨 앞에서 빼니까!

3. empty() : O(1) - front가 null인지 보면 되니까!

4. getfront() : O(1) - 맨 앞거 보면 되니까!

5. size() : O(1) - rear - front하면 되니까!!!