Glib 학습 (3) 양 끝 대기 열 Double - ended Queues
2 단 대기 열 은 삽입 과 삭제 작업 을 제한 하 는 데이터 구조 로 대기 열과 창고 의 성질 을 가지 고 있다.
(deque, 전체 이름 double - ended quue) 는 대기 열과 창고 의 성질 을 가 진 데이터 구조 이다.양 끝 대기 열 에 있 는 요 소 는 양 끝 에서 팝 업 할 수 있 으 며, 표 의 양 끝 에 삽입 과 삭제 작업 을 한정 하여 진행 할 수 있 습 니 다.
즉, 쌍 단 대기 열 은 대기 열과 창고 의 집합 으로 규칙 을 통 해 대기 열과 창고 의 기능 을 유연 하 게 실현 한다.
다음은 GLib Reference Manual 사이트 입 니 다.
http://web.mit.edu/barnowl/share/gtk-doc/html/glib/glib-Double-ended-Queues.html#g-queue-copy
GQueue 구조 체 와 관련 함수 가 표준 대기 열 데이터 구 조 를 제공 합 니 다.내부 에서 GQueue 는 glist 와 같은 데이터 구 조 를 사용 하여 요 소 를 저장 합 니 다.int 형 데 이 터 를 저장 하거나 형식 변환 매크로 를 사용 할 수 있 습 니 다. Type Conversion Macros, 모든 데이터 형식의 지침 으로 변환 합 니 다.
대기 열 만 들 기
g_queue_new()정적 대기 열 을 초기 화 하려 면 GQUEUE_INIT 혹은 g_queue_init() 이것 은 new 와 init 의 차이 와 관련된다. 운영 체제 에서 동적 신청 메모 리 를 통 해 더미 에 분 배 된 new 사용 을 실현 하고 창고 에 분 배 된 init 사용 을 실현 한다.프로 그래 밍 의 차 이 는 바로 new 의 방법 이 프로그램 에서 동적 으로 실 현 될 수 있다 는 것 이다. init 는 컴 파일 하기 전에 이미 어디 에 있 는 지 알 고 있다.
요소 추가 사용
g_queue_push_head() , g_queue_push_head_link() , g_queue_push_tail() 화해시키다 g_queue_push_tail_link() 요소 삭제 사용
g_queue_pop_head() 화해시키다 g_queue_pop_tail() 모든 대기 열 사용 해제
g_queue_free() 구조 체 를 살 펴 보 겠 습 니 다.
GQueue
typedef struct {
GList *head;
GList *tail;
guint length;
} GQueue;head 가 대기 열의 첫 번 째 요 소 를 가리 키 고 있 습 니 다.
tail 은 대기 열의 마지막 요 소 를 가리 키 고 있 습 니 다.
length 는 대기 열의 요소 갯 수 입 니 다.
다음은 대기 열 에서 제공 하 는 함수 입 니 다.
Synopsis
#include <glib.h>
GQueue;
GQueue* g_queue_new (void);
void g_queue_free (GQueue *queue);
#define G_QUEUE_INIT
void g_queue_init (GQueue *queue);
void g_queue_clear (GQueue *queue);
gboolean g_queue_is_empty (GQueue *queue);
guint g_queue_get_length (GQueue *queue);
void g_queue_reverse (GQueue *queue);
GQueue* g_queue_copy (GQueue *queue);
void g_queue_foreach (GQueue *queue,
GFunc func,
gpointer user_data);
GList* g_queue_find (GQueue *queue,
gconstpointer data);
GList* g_queue_find_custom (GQueue *queue,
gconstpointer data,
GCompareFunc func);
void g_queue_sort (GQueue *queue,
GCompareDataFunc compare_func,
gpointer user_data);
void g_queue_push_head (GQueue *queue,
gpointer data);
void g_queue_push_tail (GQueue *queue,
gpointer data);
void g_queue_push_nth (GQueue *queue,
gpointer data,
gint n);
gpointer g_queue_pop_head (GQueue *queue);
gpointer g_queue_pop_tail (GQueue *queue);
gpointer g_queue_pop_nth (GQueue *queue,
guint n);
gpointer g_queue_peek_head (GQueue *queue);
gpointer g_queue_peek_tail (GQueue *queue);
gpointer g_queue_peek_nth (GQueue *queue,
guint n);
gint g_queue_index (GQueue *queue,
gconstpointer data);
void g_queue_remove (GQueue *queue,
gconstpointer data);
void g_queue_remove_all (GQueue *queue,
gconstpointer data);
void g_queue_insert_before (GQueue *queue,
GList *sibling,
gpointer data);
void g_queue_insert_after (GQueue *queue,
GList *sibling,
gpointer data);
void g_queue_insert_sorted (GQueue *queue,
gpointer data,
GCompareDataFunc func,
gpointer user_data);
void g_queue_push_head_link (GQueue *queue,
GList *link_);
void g_queue_push_tail_link (GQueue *queue,
GList *link_);
void g_queue_push_nth_link (GQueue *queue,
gint n,
GList *link_);
GList* g_queue_pop_head_link (GQueue *queue);
GList* g_queue_pop_tail_link (GQueue *queue);
GList* g_queue_pop_nth_link (GQueue *queue,
guint n);
GList* g_queue_peek_head_link (GQueue *queue);
GList* g_queue_peek_tail_link (GQueue *queue);
GList* g_queue_peek_nth_link (GQueue *queue,
guint n);
gint g_queue_link_index (GQueue *queue,
GList *link_);
void g_queue_unlink (GQueue *queue,
GList *link_);
void g_queue_delete_link (GQueue *queue,
GList *link_);다음은 테스트 코드 를 제공 합 니 다.
#include <stdio.h>
#include <glib.h>
//#include <glib/gprintf.h>
struct map {
int key;
char *value;
} m[10] = {
{0,"zero"},
{1,"one"},
{2,"two"},
{3,"three"},
{4,"four"},
{5,"five"},
{6,"six"},
{7,"seven"},
{8,"eight"},
{9,"nine"},
};
typedef struct map map;
static void
myPrintInt(gpointer p1, gpointer fmt)
{
g_printf(fmt, *(gint *)p1);
}
static void
myPrintStr(gpointer p1, gpointer fmt)
{
g_printf(fmt, (gchar *)p1);
}
static void
test_queue_1(void)
{
// GQueue* g_queue_new(void);
GQueue *queue = g_queue_new();
// gboolean g_queue_is_empty(GQueue *queue); ， 1
gboolean b = g_queue_is_empty(queue);
g_printf("The queue should be empty now.\t\tResult: %s.
", b ? "YES" : "NO");
// void g_queue_push_tail(GQueue *queue, gpointer data); data
gint i;
for (i = 0; i < sizeof (m) / sizeof (m[0]); i++)
g_queue_push_tail(queue, m[i].value);
// void g_queue_foreach(GQueue *queue, GFunc func, gpointer user_data); func ，user_data
g_printf("Now the queue[after push tail] :
");
g_queue_foreach(queue, myPrintStr, "%s, ");// ， map value，
g_printf("
");
// guint g_queue_get_length(GQueue *queue);
g_printf("The lenght should be '%d' now.\t\tResult: %d.
", 10, g_queue_get_length(queue));
// void g_queue_reverse(GQueue *queue);
g_queue_reverse(queue);
g_printf("Now the queue[after reverse] :
");
g_queue_foreach(queue, myPrintStr, "%s, ");
g_printf("
");
// gpointer g_queue_pop_head(GQueue *queue);
g_printf("The head should be '%s' now.\t\tResult: %s.
", "nine", (gchar *)g_queue_pop_head(queue));
// gpointer g_queue_pop_tail(GQueue *queue);
g_printf("The tail should be '%s' now.\t\tResult: %s.
", "zero", (gchar *)g_queue_pop_tail(queue));
g_printf("Now the queue[after pop head and tail] :
");
g_queue_foreach(queue, myPrintStr, "%s, ");
g_printf("
");
// gpointer g_queue_pop_nth(GQueue *queue, guint n); n
g_printf("The head should be '%s' now.\t\tResult: %s.
", "eight", (gchar *)g_queue_pop_nth(queue, 0));
// void g_queue_push_head(GQueue *queue, gpointer data); data
g_queue_push_head(queue, "zero");
g_queue_push_head(queue, "eight");
// void g_queue_push_nth(GQueue *queue, gpointer data, gint n); data n
g_queue_push_nth(queue, "nine", 2);
g_printf("Now the queue[after push 'zero' 'eight' 'nine'] :
");
g_queue_foreach(queue, myPrintStr, "%s, ");
g_printf("
");
// gpointer g_queue_peek_head(GQueue *queue); ，
g_printf("The head should be '%s' now.\t\tResult: %s.
", "eight", (gchar *)g_queue_peek_head(queue));
// gpointer g_queue_peek_tail(GQueue *queue); ，
g_printf("The tail should be '%s' now.\t\tResult: %s.
", "one", (gchar *)g_queue_peek_tail(queue));
// gpointer g_queue_peek_nth(GQueue *queue, guint n); n ，
g_printf("The head should be '%s' now.\t\tResult: %s.
", "eight", (gchar *)g_queue_peek_nth(queue, 0));
/*
// void g_queue_clear(GQueue *queue); ， ， ， init ，new free
g_queue_clear(queue);
g_printf("Now the queue[after clear] :
");
g_queue_foreach(queue, myPrintStr, "%s, ");
g_printf("
");
*/
// void g_queue_free(GQueue *queue);
g_queue_free(queue);
}
static gint
sort(gconstpointer p1, gconstpointer p2, gpointer user_data)//
{
gint32 a, b;
a = *(gint*)(p1);
b = *(gint*)(p2);
return (a > b ? +1 : a == b ? 0 : -1);
}
static gint
myCompareInt(gconstpointer p1, gconstpointer p2)//
{
const int *a = p1;
const int *b = p2;
return *a - *b;
}
static gint
sort_r(gconstpointer p1, gconstpointer p2, gpointer user_data)//
{
gint32 a, b;
a = *(gint*)(p1);
b = *(gint*)(p2);
return (a < b ? +1 : a == b ? 0 : -1);
}
static void
test_queue_2(void)
{
GQueue *queue = NULL;
/*
// void g_queue_init(GQueue *queue);
g_queue_init(queue);
*/
queue = g_queue_new();
// void g_queue_insert_sorted(GQueue *queue, gpointer data, GCompareDataFunc func gpointer user_data); func
gint i;
for (i = 0; i < sizeof (m) / sizeof (m[0]); i++)
g_queue_insert_sorted(queue, &m[i].key, sort_r, NULL);
g_printf("Now the queue[after insert sorted] :
");
for (i = 0; i < queue->length; i++)
g_printf("%d, ", *(gint *)g_queue_peek_nth(queue, i));
g_printf("
");
// void g_queue_remove(GQueue *queue, gconstpointer data); data ，
g_queue_remove(queue, &m[3].key);
g_printf("Now the queue[after remove '%d'] :
", m[3].key);
for (i = 0; i < queue->length; i++)
g_printf("%d, ", *(gint *)g_queue_peek_nth(queue, i));
g_printf("
");
// GList* g_queue_find_custom(GQueue *queue, gconstpointer data, GCompareFunc func); func data
// void g_queue_insert_before(GQueue *queue, GList *sibling, gpointer data); data sibling
// void g_queue_insert_after(GQueue *queue, GList *sibling, gpointer data); data sibling
g_queue_insert_before(queue, g_queue_find_custom(queue, &m[5].key, myCompareInt), &m[3].key);
g_queue_insert_after(queue, g_queue_find_custom(queue, &m[5].key, myCompareInt), &m[3].key);
g_printf("Now the queue[after insert '%d' around '%d'] :
", m[3].key, m[5].key);
g_queue_foreach(queue, myPrintInt, "%d, ");
g_printf("
");
// void g_queue_sort(GQueue *queue, GCompareDataFunc compare, gpointer user_data); compare
g_queue_sort(queue, sort, NULL);
g_printf("Now the queue[sorted] :
");
g_queue_foreach(queue, myPrintInt, "%d, ");
g_printf("
");
// GQueue* g_queue_copy(GQueue *queue); ， ， ，
GQueue *q = g_queue_copy(queue);
g_printf("Now the queue[copy] :
");
g_queue_foreach(q, myPrintInt, "%d, ");
g_printf("
");
// void g_queue_remove_all(GQueue *queue, gconstpointer data); data
g_queue_remove_all(q, &m[3].key);
g_printf("Now the queue[remove '%d'] :
", m[3].key);
g_queue_foreach(q, myPrintInt, "%d, ");
g_printf("
");
g_queue_free(q);
g_queue_free(queue);
}
int
main(void)
{
printf("BEGIN:
************************************************************
");
printf("
------------------------------------------------------------
test_queue_1:
");
test_queue_1();
printf("------------------------------------------------------------
");
printf("
------------------------------------------------------------
test_queue_2:
");
test_queue_2();
printf("------------------------------------------------------------
");
printf("
************************************************************
DONE
");
return 0;
}
실행 결과:
linux@ubuntu:~/16021/glibdemo$ gcc -o Double_ended_Queues Double_ended_Queues.c -lglib-2.0
Double_ended_Queues.c: In function ‘test_queue_2’:
Double_ended_Queues.c:183:17: warning: initialization makes pointer from integer without a cast [enabled by default]
linux@ubuntu:~/16021/glibdemo$ ./Double_ended_Queues
BEGIN:
************************************************************
------------------------------------------------------------
test_queue_1:
The queue should be empty now. Result: YES.
Now the queue[after push tail] :
zero, one, two, three, four, five, six, seven, eight, nine,
The lenght should be '10' now. Result: 10.
Now the queue[after reverse] :
nine, eight, seven, six, five, four, three, two, one, zero,
The head should be 'nine' now. Result: nine.
The tail should be 'zero' now. Result: zero.
Now the queue[after pop head and tail] :
eight, seven, six, five, four, three, two, one,
The head should be 'eight' now. Result: eight.
Now the queue[after push 'zero' 'eight' 'nine'] :
eight, zero, nine, seven, six, five, four, three, two, one,
The head should be 'eight' now. Result: eight.
The tail should be 'one' now. Result: one.
The head should be 'eight' now. Result: eight.
------------------------------------------------------------
------------------------------------------------------------
test_queue_2:
Now the queue[after insert sorted] :
9, 8, 7, 6, 5, 4, 3, 2, 1, 0,
Now the queue[after remove '3'] :
9, 8, 7, 6, 5, 4, 2, 1, 0,
Now the queue[after insert '3' around '5'] :
9, 8, 7, 6, 3, 5, 3, 4, 2, 1, 0,
Now the queue[sorted] :
0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9,
Now the queue[copy] :
0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9,
Now the queue[remove '3'] :
0, 1, 2, 4, 5, 6, 7, 8, 9,
------------------------------------------------------------
************************************************************
DONE
linux@ubuntu:~/16021/glibdemo$
자, 자주 사용 하 는 함 수 는 기본적으로 이것들 입 니 다. 내일 은 순서에 따라 서열 이 어야 합 니 다. 그러나 서열 은 데이터 뱅 크 의 메 인 키 에 사용 되 고 모든 데이터 베 이 스 는 통 일 된 규칙 이 있 기 때문에 응용 이 많 지 않 습 니 다. 잠시 연 구 를 하지 않 고 순서대로 hash 연 구 를 합 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
2 단 대기 열 (deque) 의 응용n - k} {1<=k<=n<=1e6;0<=ai<=1e9} sample input n=5 k=3 a={1,3,5,4,2} sample ouput b = {1, 3, 2} [분석]: solution 1...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
