[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 사용하여 쌍으로 값저장





C++ pair 사용하여 쌍으로 값저장, vector를 사용한 예

 

 

 

 

Pair<[Type], [Type] > 이란?

 

- 2개의 각각 지정한 타입의 값을 저장한다.

 

- 저장한 값은 .first 와 .second로 각각 접근할 수 있다.

 

- 2개의 연관된 값을 같이 저장할 수 있어서 관리를 용이하게 할 수 있다.

 

- 특히, 연관된 2개의 값에서 각각의 조건에 따라 정렬한 결과를 얻고자 할 때 사용하면 좋다. 

( 즉, 2개의 정렬 조건으로 정렬을 하고 싶을 때)

 

 

 

 

 

 

[ 코 드 ]

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool comp(pair<int, double> a, pair<int, double> b) {
    if (a.second == b.second) a.first < b.first;
    return a.second > b.second;
}

int main() {
    vector<int> v;
    int N = 8;
    pair< int, int> test = make_pair(1, 2);
    vector<pair<int, double>> vv;
    v.push_back(1);
    v.push_back(3);
    v.push_back(2);
    v.push_back(1);
    v.push_back(0);
    
    for (int i = 0; i < v.size(); i++) {
        vv.push_back(make_pair(i + 1, (double)v[i] / N));
        N -= v[i];
    } // (1, 0.125) (2, 0.4285) (3, 0.5) (4, 0.5) (5, 0) 순으로 데이터가 있다.
	

    sort(vv.begin(), vv.end(), comp); // 2번째 값이 큰 순으로, 1번째 값이 작은 순으로 정렬을 한다.
    
    for (int i = 0; i < vv.size(); i++) {
        cout << vv[i].first << " " << vv[i].second << "\n";
    }

	return 0;
}

 

- 14라인 : pair변수를 선언하고 값을 할당한다. 값을 줄 때는 make_pair( 값1, 값2)를 사용해준다.

 

- 15라인 : vector의 pair타입을 사용하여 선언함으로써 pair 변수를 저장할 수 있게 한다.

 

- 23라인 : pair 타입을 저장하는 vector이므로 make_pair을 사용해 주어서 값을 저장하고 있다.

 

 

 

 

 

 

[ 결 과 ]

 

 

 

- 결과를 보면 2번째 값에 따라서 내림차순 정렬이 되며, 2번째 값이 같을 경우 1번째 값에 따라 오름차순 정렬이 되었다.

 

 

 

 

 

C++ vector 오름차순, 내림차순으로 정렬하기

 

 

 

 

 

sort() 함수

 

- 사용하기 위해서는  #include <algorithm>  을 해주어야 한다.

 

- 디폴트(기본)적으로 오름차순으로 정렬을 해준다.

 

- 내림차순으로 정렬을 하고자 하거나 특정 조건에 따라서 정렬을 하고자 할 때는 비교함수를 만들어서 인수로 주어야 한다.

( 비교함수명은 본인이 지정하면 된다. )

 

- 비교함수는 리턴형은 bool 형으로 매개변수들의 타입은 정렬하는 vector의 저장하는 값의 타입을 준다.

 

- sort() 함수는 퀵 솔트(Quick sort)으로 구현되어 있어 빠른 속도로 정렬을 한다. 

 

- sort() 함수를 사용한다면 일반적인 배열또한 정렬할 수 있다.

 

 

 

 

[ 코 드 ]

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool comp(int a, int b) {
    return a > b;
}

int main() {
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(7);
    v.push_back(8);
    v.push_back(1);
    v.push_back(5);
    
    for (int i = 0; i < v.size(); i++) cout << v[i] << " ";
    cout << " 정렬 전\n\n";

    sort(v.begin(), v.end());   // 오름차순 정렬

    for (int i = 0; i < v.size(); i++) cout << v[i] << " ";
    cout << " 오름차순 정렬 후\n\n";

reverse(v.begin(), v.end());	// 1. 내림차순 정렬 (오름차순정렬 후 같이 사용)
    sort(v.rbegin(), v.rend());		// 2. 내림차순 정렬 ( rbegin()과 rend()를 사용)
    sort(v.begin(), v.end(), comp); // 3. 내림차순 정렬 (비교함수를 사용)

    for (int i = 0; i < v.size(); i++) cout << v[i] << " ";
    cout << " 내림차순 정렬 후\n\n";

	return 0;
}

 

 

- 23라인 : 추가적으로 비교함수를 인수를 주지 않았다. 그러므로 디폴트 값인 오름차순으로 정렬이 된다.

 

 

※ 

- 28라인 : reverse 함수는 뜻 그대로 반대로 뒤집는다. 그래서 이를 오름차순으로 정렬한 후 사용한다면 내림차순으로 정렬한 것과 같은 결과를 얻을 수 있다.

( reverse 함수또한 사용하기 위해서는 #incldue <algorithm> 을 해주어야 한다.

 

- 29라인 : 오름차순 정렬할 때는 인수로 v.begin(), v.end()를 주었었다. 하지만 이대신 v.rbegin(), v.rend()를 주면 내림차순으로 정렬이 된다. ( r은 아마 reverse )

 

- 30라인 : 추가적으로 비교함수를 인수로 주었다. 비교 함수에서 준 조건에 따라 내림차순으로 정렬이 된다. 이 방법은 굳이 내림차순 정렬만이 아니라 특정 조건에 따라서 정렬을 하고자 할 때 사용할 수 있다.

 

 

 

 

 

[ 결 과 ]

 

 

결과를 보면 각각 오름차순과 내림차순으로 각각 잘 정렬된 것을 확인할 수 있다.

 

 

 

 

 

 

 

 

 

+ Recent posts