코딩테스트 자료구조 (1)

📖 연결리스트 (Linked List)

연결리스트 배열과 반대.. 연결리스트 : 삽입 삭제 O(1), 탐색 O(N) 배열 : 삽입 삭제 O(N), 탐색 O(1)

📖 stack : LIFO

• 삽입, 삭제 O(1),
• 탐색 O(N)

c++에서 stack 사용법

---

//C++
#include <iostream>
#include <stack>
using namespace std;

stack<int> s;
s.push(7);
s.push(5);
s.push(4);
printf("size: %d\n", s.size());
while(!s.empty()){
  printf("%d\n", s.top()); //맨 위의 값 출력
  s.pop(); //맨 위의 값 삭제(출력은 안함)
}

python에서 stack 사용법

---

#Python
s = []
s.append(7)
s.append(5)
s.append(4)
print("size: ", len(s))
while len(s) > 0:
  print(s[-1])
  s.pop() 

여기서 마지막 배열[-1] 은 배열의 맨 뒤를 의미한다.

swift에서 stack 사용법

---

//Swift
var s = [Int]()
s.append(7)
s.append(5)
s.append(4)
print("size: ", s.count)
while !s.isEmpty {
  print(s.last!)
  s.removeLast()
}

📖 queue : FIFO

• 삽입, 삭제 O(1),
• 탐색 O(N)

c++에서 queue 사용법

---

//C++
#include <iostream>
#include <queue>
using namespace std;

queue<int> q;
q.push(7);
q.push(5);
q.push(4);
printf("size: %d\n", q.size());
while(!q.empty()){
  printf("%d\n", q.front());
  q.pop();
}

python에서 queue 사용법 (리스트로 구현)

---

#Python
"""
from queue import Queue
q = Queue()
q.put(7)
q.put(5)
q.put(4)
print("size: ", q.qsize())
while not q.empty():
  print(q.get()) #맨 앞의 값 출력

thread-safe : 멀티스레드 환경에서 안전하게 사용할 수 있는 자료구조(속도 느림)
"""
#deque 라이브러리 사용
from collections import deque

q = deque()
q.append(7)
q.append(5)
q.append(4)
print("size: ", len(q))
while len(q) > 0:
  print(q[0])
  q.popleft() #맨 앞에서 꺼내기(큐)
  #q.pop() #맨 뒤에서 꺼내기(스택) 

• c++에서도 deque 사용 가능