[STL] C++ deque 덱 생성 및 삽입, 삭제

결과

결과

코드

#include <iostream>
#include <string>
#include <deque>
using namespace std;

int main() {
	deque<int> dq;
	deque<int> dq2 ( 5, 100);

	if (dq.empty()) cout << "덱이 비었습니다.\n";

	dq.push_back(4);	// 4
	dq.push_front(1);	// 1 4
	dq.push_front(3);	// 3 1 4
	dq.insert(dq.begin()+1, 2);	// 3 2 1 4

	cout << "dq1 순 서 : ";
	for (int i = 0; i < dq.size(); i++) {
		cout << dq[i] << " ";
	}

	cout << "\ndq2 순 서 : ";
	for (int i = 0; i < dq2.size(); i++) {
		cout << dq2[i] << " ";
	}
	cout << "\n";

	return 0;
}

Deque(double-ended queue) : 덱 혹은 디큐로 부른다. 구조는 '스택 + 큐' 같은 형태로 앞쪽으로 삽입, 삭제가 가능하면서 뒤쪽으로도 삽입, 삭제가 가능하다.

멤버 함수들은 vector와 거의 유사하다.

링크

[C++/STL] - C++ vector 생성 및 삽입, 삭제

push_back(), pop_back() : 뒤쪽으로 삽입, 삭제

push_front(), pop_front() : 앞쪽으로 삽입, 삭제

insert() : 중간 삽입

- 주로 특정 경우만 사용한다.

empty() : 비어있는지 검사

size() : 길이 리턴

[STL] C++ priority_queue 우선순위 큐

결과

결과 - int 오름차순

결과 - string 내림차순

코드

#include <iostream>
#include <string>
#include <queue>
using namespace std;

int main() {
	// priority_queue<int> q;	// 내림차순 
	// priority_queue<int, vector<int>, less<int> > q;	// 내림차순
	priority_queue<int, vector<int>, greater<int> > q;	// 오름차순

	if (q.empty()) cout << "우선순위 큐가 비었습니다.\n";

	q.push(4);
	q.push(4);
	q.push(2);
	q.push(1);
	q.push(3);

	cout << "맨 위 : " << q.top() << "\n";


	cout << "나가는 순서 : ";
	while (!q.empty()) {
		cout << q.top() << " ";
		q.pop();
	}
	cout << "\n";

	return 0;
}

우선순위 큐(priority_queue) : 스택(stack)과 큐(queue) 같은 자료형.

우선순위 큐는 각 원소들이 우선순위를 갖는다.

내림차순, 오름차순

- priority_queue는 기본적으로 내림차순으로 정렬한다.

- 오름차순으로 정렬하기 위해서는

priority_queue<int, vector<int>, greater<int> > q;	// 오름차순

해야한다.

empty() : 큐가 비었는지 검사

push() : 데이터를 삽입

size() : 길이를 리턴

top() : 가장 우선순위가 높은 원소

- pop() 했을 시 가장 먼저 나간다.

pop() : 데이터를 삭제

[STL] C++ queue 생성 및 삽입, 삭제

결과

결과

코드

#include <string>
#include <iostream>
#include <queue>
using namespace std;

int main() {
	queue<int> q;

	if (q.empty()) cout << "큐가 비었습니다.\n";

	q.push(4);
	q.push(2);
	q.push(1);
	q.push(3);

	cout << "맨 앞 : " << q.front() << "\n";
	cout << "맨 뒤 : " << q.back() << "\n";


	cout << "나가는 순서 : ";
	while (!q.empty()) {
		cout << q.front() << " ";
		q.pop();
	}
	cout << "\n";

	return 0;
}

Queue : 후입후출(or 선입선출)의 구조로 가장 먼저 들어온 것이 가장 먼저 나간다.

empty() : 큐가 비어있는지 검사

- 비어있지 않다면 false를 return 한다.

push() : 데이터를 삽입(push) 

front() : 가장 앞 값을 리턴

- 가장 앞(가장 먼저 나갈) 값을 리턴

back() : 가장 뒤 값을 리턴

- 가장 뒤(가장 나중에 나갈) 값을 리턴

size() : 큐의 길이를 리턴

pop() : front() 값을 삭제(pop)

- 큐는 선입선출의 구조이므로 가장 앞에(가장 먼저 들어온) 값을 삭제한다.

- return 형이 void형이므로 pop()을 해주기 전에 front() 값을 따로 저장해두어야만 이용할 수 있다.

- 큐가 비었을 경우 pop()을 한다면 에러가 발생한다.

pair을 사용하여서 queue의 2개 값 저장하기

링크

[C++/STL] - C++ pair 사용하여 쌍으로 값저장

Java List Collection - ArrayList, LinkedList, Vector

예시 리스트

1. ArrayList : 가변적인 크기의 배열

- 동작 방식(삽입)

AL1

AL2

ex) 2번 자리의 추가

2번 자리의 추가를 한다면 맨 뒤 빈자리가 추가된다.

이후 2~4번의 앉아있던 사람이 한칸씩 뒤로 이동한다.

그리고 이동 후 빈자리의 새 값이 들어간다.

=> 삭제도 마찬가지의 과정을 거친다.

※ 따라서 ArrayList는 검색 속도는 빠르지만, 중간 삽입/삭제가 많다면 아주 비효율적이다.

2. LinkedList : ArrayList와 사용 방법 등 똑같지만 내부 동작 구조가 다르다.

- 동작 방식(삽입)

LL1

LL2

ex) 2번 자리에 추가

LinkedList는 내부 객체들끼리 링크로 연결되어 있다.

따라서 ArrayList처럼 자리이동 없이 이 링크만 끊어준 후 다른곳으로 연결만 해주면 된다.

※ 이처럼 ArrayList와 달리 중간에 삽입/삭제가 발생하여도 빠르게 할 수 있다. 하지만 링크를 타고 움직이므로 탐색은 느리다.

3. Vector : ArrayList와 사용 방법 등 똑같지만 스레드의 안전(Thread-Safe) 하다.

결과

결과

코드

package pk;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Vector;

public class Test {

	public static void main(String[] args) {
		ArrayList<String> al = new ArrayList<>();
		Vector<String> v = new Vector<>();
		LinkedList<String> ll = new LinkedList<String>();
		
		System.out.println("- 객체 삽입 -");
		al.add("a");	// a
		al.add("c");	// a c
		al.add("b");	// a c b
		al.add("a");	// a c b a
		al.add(2, "x");	// a c x b a
		
		al.set(1, "y");	//  a y x b a
		System.out.print("값 확인 : ");
		for(String s : al) System.out.print(s + ", ");
		System.out.println("\n");
		
		
		System.out.println("- 객체 검색 -");
		if( !al.isEmpty() ) System.out.println("리스트가 비어있지 않습니다.");
		System.out.println("개수 : " + al.size());
		if( al.contains("a") ) System.out.println( "a가 있습니다." );
		System.out.println("index 2의 객체 : " + al.get(2) + "\n");
		
		
		System.out.println("- 객체 삭제 -");
		System.out.print("index 2 삭제 : ");		
		al.remove(2);	//  a y b a
		for(String s : al) System.out.print(s + ", ");
		System.out.print("\na 찾아서 삭제 : ");
		al.remove("a");	//  y b a
		for(String s : al) System.out.print(s + ", ");
		System.out.print("\n 리스트 비우기 : ");
		al.clear();
		if( al.isEmpty() ) System.out.println("리스트가 비었습니다.");
	}

}

List Collection 메소드들

boolean add(E e) : 맨 뒤에 객체 추가

void add(int index, E e) : 해당 인덱스의 객체 추가

E set(int index, E e) : 해당 인덱스 객체값 수정

boolean contain(Object o) : 해당 객체가 포함되어 있는지 여부

int size() : 저장된 객체 개수 리턴

E get(int index) : 해당 인덱스 값 가져오기

boolean isEmpty() : 비어있는지 검사

E remove(int index) : 해당 인덱스 객체 제거

boolean remove(Object o) : 인자로 받은 객체 제거 (앞에서부터 하나만)

void clear() : 리스트를 비움

Java 제네릭(Generic) 타입 

- Java API Document를 보면 많은 제네릭 타입을 사용하고 있으므로 이를 이해하고 있어야만 정확히 이해하고, 사용할 수 있다.

https://docs.oracle.com/javase/8/docs/api/

- 제네릭 타입은 "<>" 부호를 사용하며 타입을 인수로 받을 수 있도록 한다.

- 제네릭 타입을 사용함으로써 타입 검사를 강화함으로써 에러를 줄일 수 있다.

또한, 캐스팅(타입 변환)을 없애주므로 성능을 향상시킬 수 있다.

결과

결과

코드

package pk;

public class Test<T, S> {
	T num;
	S[] count;
	
	public Test(T n, int size) {
		this.num = n;
		this.count = (S[]) new Object[size];
	}
	
	void getC() {
		System.out.print(num + ". ");
		for(S i : count) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		Test<Integer, String> t = new Test<Integer, String>(1, 3);
		Test<Integer, Integer> t2 = new Test<>(3, 4);
		t.getC();
		t2.getC();
	}

}

- 제네릭 타입은 클래스<T, S> 이렇게 쓰곤 한다. (보통 대문자로 표기한다.)

- 제네릭 타입은 멤버 변수 타입을 지정하거나 메소드 리턴형을 지정할 때나 다 사용할 수 있다.

- 21라인 : int형을 지정하고자 하면 Integer를 사용해야 한다.

- 9라인 : 제네릭 타입 배열을 초기화 해줄 때는 Object 객체형으로 생성한 후 강제 형변환으로 변환해주어야 한다.

(Object는 모든 객체의 최상위 부모이다.)

- 22라인 : 뒤쪽을 보면 21라인과 달리 "<>" 속 값을 생략할 수도 있다.

제네릭 타입 제한

- 제네릭 타입<?> : 모든 클래스나 인터페이스가 올 수 있다.

- 제네릭 타입<? extends 클래스> : 상위 클래스 제한

해당 클래스 및 해당 클래스의 자식 클래스만이 올 수 있다.

- 제네릭 타입<? super 하위타입> : 하위 클래스 제한

해당 클래스 및 해당 클래스의 부모 클래스만이 올 수 있다.

[STL] C++ stack 생성 및 삽입, 삭제

결과

결과

코드

#include <string>
#include <iostream>
#include <stack>
using namespace std;

int main() {
	stack<int> s;

	if (s.empty()) cout << "스택이 비었습니다.\n";

	s.push(4);	// 4
	s.push(3);	// 4 3
	s.push(5);	// 4 3 5
	s.push(1);	// 4 3 5 1
	s.push(6);	// 4 3 5 1 6
	s.push(2);	// 4 3 5 1 6 2
	
	cout << "가장 꼭대기 : " << s.top() << "\n";
	cout << "개수 : " << s.size() << "\n";

	cout << "하나씩 출력 : ";
	while (!s.empty()) {
		cout << s.top() << " ";
		s.pop();
	}
	cout << "\n";

	return 0;
}

Stack : 후입선출(or 선입후출)의 구조로 가장 나중에 들어온 것이 가장 먼저 나간다.

ex) 한줄로만 넣을 수 있는 박스의 물건을 넣는다고 생각하면 된다. 이렇게 된다면 가장 위에 물건을 꺼내야만 그 아래의 있는 물건을 꺼낼 수 있다.

empty() : 스택이 비었는지 검사한다.

- 스택이 비었다면 true를 return 한다.

push() : 데이터를 삽입(push) 한다.

top() : 가장 꼭대기의 값을 리턴한다,

- 가장 꼭대기의 값이므로 pop()했을 때 나오는 값이다.

size() : 스택의 길이를 리턴한다.

pop() : 꼭대기의 값을 삭제(pop) 한다.

- return 형이 void이므로 꼭대기 값을 이용하기 위해서는 pop()하기 전 top()으로 값을 가져와야 한다.

- 스택이 비워져 있을 때 pop()을 실행한다면 오류가 발생한다.

pair을 사용하여서 값 쌍으로 저장하기

링크

[C++/STL] - C++ pair 사용하여 쌍으로 값저장