- 使用鏈表實現(xiàn)進(jìn)出排隊系統(tǒng)
// 練習(xí)：模擬銀行的排隊系統(tǒng)
#include <stdio.h>
#include "link_queue.h"
#include <pthread.h>
#include <unistd.h>
#include <semaphore.h>
#define MAX_CLIENT_COUNT 100
// 全局隊列：用于存放用戶ID的鏈?zhǔn)疥犃?link_queue_t *queue;
// 互斥鎖：用于保障生產(chǎn)者線程和消費者線程互斥訪問用戶隊列
pthread_mutex_t mutex;
// 用戶數(shù)信號量：用于表示當(dāng)前可用的用戶個數(shù)
sem_t client_sem;
// 空余排隊數(shù)信號量：用于表示當(dāng)前隊列中能夠繼續(xù)插入的用戶個數(shù)
sem_t free_space_sem;
// 生產(chǎn)者線程：用于模擬用戶的產(chǎn)生
void *producer_thread(void *arg);
// 消費者線程：用于模擬銀行柜臺的動作
void *consumer_thread(void *arg);
int main(int argc, char *argv[])
{
pthread_t producer_id;
pthread_t consumer_id;
// 初始化全局用戶隊列
queue = create_empty_link_queue();
// 初始化互斥鎖
pthread_mutex_init(&mutex, NULL);
// 初始化相關(guān)信號量
sem_init(&client_sem, 0, 0);
sem_init(&free_space_sem, 0, MAX_CLIENT_COUNT);
// create threads
pthread_create(&producer_id, NULL, producer_thread, NULL);
pthread_create(&consumer_id, NULL, consumer_thread, NULL);
// join threads
pthread_join(producer_id, NULL);
pthread_join(consumer_id, NULL);
sem_destroy(&client_sem);
sem_destroy(&free_space_sem);
return 0;
}
// 生產(chǎn)者線程：用于模擬用戶的產(chǎn)生
void *producer_thread(void *arg)
{
int client_no = 0;
while(1)
{
// 1.獲取 產(chǎn)生用戶的資格(即讓空余位置-1)
sem_wait(&free_space_sem);
// 2.模擬產(chǎn)生用戶ID
client_no = rand()%1000+1;
// 3.以互斥的方式向用戶隊列中插入用戶ID信息
pthread_mutex_lock(&mutex);
insert_to_link_queue(queue, client_no);
pthread_mutex_unlock(&mutex);
// 4.模擬打印用戶入隊信息
printf("client %d is in...queue length : %d\n", client_no, length_of_link_queue(queue));
// 5.可用用戶數(shù)目+1
sem_post(&client_sem);
// 6.模擬用戶的到達(dá)時間間隔
sleep(1);
}
}
// 消費者線程：用于模擬銀行柜臺的動作
void *consumer_thread(void *arg)
{
int client_no = 0;
while(1)
{
// 1.申請可用用戶資源(即對可用用戶數(shù)-1)
sem_wait(&client_sem);
// 2.以互斥的方式從全局用戶隊列中獲取用戶ID
pthread_mutex_lock(&mutex);
delete_from_link_queue(queue, &client_no);
pthread_mutex_unlock(&mutex);
// 3.模擬銀行柜臺的操作
printf("client %d is out...\n", client_no);
// 3.隊列空余資源數(shù)+1
sem_post(&free_space_sem);
// 4.模擬柜臺操作的時間間隔
sleep(rand()%5+1);
}
}
// 變式練習(xí)：
// 1.參考上述代碼三妈，實現(xiàn)單生產(chǎn)者多消費者問題
// 2.參考上述代碼牙勘，實現(xiàn)多生產(chǎn)者多消費者問題
#ifndef __SQ_QUEUE_H__
#define __SQ_QUEUE_H__
// 定義鏈?zhǔn)疥犃兄性氐膶嶋H類型的別名
// 注意：隊列中可以存放任意類型的數(shù)據(jù)
typedef int datatype_t;
// 定義鏈?zhǔn)疥犃兄薪Y(jié)點的類型及其別名
typedef struct _queue_node
{
datatype_t data;
struct _queue_node *next;
}queue_node_t;
// 定義存放鏈?zhǔn)疥犃嘘犑缀完犖仓羔樀慕Y(jié)構(gòu)類型及其別名
typedef struct _link_queue
{
queue_node_t *front;
queue_node_t *rear;
}link_queue_t;
// 創(chuàng)建一個空的鏈?zhǔn)疥犃?link_queue_t *create_empty_link_queue(void);
// 判斷鏈?zhǔn)疥犃惺欠駷榭臻先裕瑸榭辗祷?，否則劲室，0
int is_empty_of_link_queue(link_queue_t *queue);
// 求鏈?zhǔn)疥犃兄性氐膫€數(shù)即隊列長度
int length_of_link_queue(link_queue_t *queue);
// 入隊操作(即在隊尾插入數(shù)據(jù)結(jié)點)
int insert_to_link_queue(link_queue_t *queue,
datatype_t x);
// 出隊操作(即在對頭刪除數(shù)據(jù)結(jié)點)
int delete_from_link_queue(link_queue_t *queue,
datatype_t *px);
// 清空鏈?zhǔn)疥犃?void clear_link_queue(link_queue_t *queue);
// 銷毀鏈?zhǔn)疥犃?void destroy_link_queue(link_queue_t *queue);
// 遍歷打印鏈?zhǔn)疥犃兄械臄?shù)據(jù)
void print_data_info_of_link_queue(link_queue_t *queue);
#endif
#include "link_queue.h"
#include <stdlib.h>
#include <stdio.h>
// 創(chuàng)建鏈?zhǔn)疥犃?link_queue_t *create_empty_link_queue(void)
{
// 為包含隊首和隊尾指針的結(jié)點動態(tài)申請空間
link_queue_t *queue = (link_queue_t *)malloc(sizeof(link_queue_t));
// 隊首指針和隊尾指針均指向頭結(jié)點
queue->front = queue->rear = (queue_node_t *)malloc(sizeof(queue_node_t));
queue->front->next = NULL;
return queue;
}
// 判斷鏈?zhǔn)疥犃惺欠駷榭胀凡恚瑸榭辗祷?会烙，否則0
int is_empty_of_link_queue(link_queue_t *queue)
{
return queue->front == queue->rear;
// return queue->front->next == NULL;
}
// 求鏈?zhǔn)疥犃械臄?shù)據(jù)元素個數(shù)即隊列長度
int length_of_link_queue(link_queue_t *queue)
{
int len = 0;
queue_node_t *p = queue->front;
while(p->next != NULL)
{
len++;
p = p->next;
}
return len;
}
// 入隊操作瓮恭，成功觅廓，返回0载城，失敗-1
int insert_to_link_queue(link_queue_t *queue,
datatype_t x)
{
// 隊列不存在峭判，插入失敗返回
if(queue == NULL)
return -1;
// 1.為插入的數(shù)據(jù)申請結(jié)點空間
queue_node_t *p = (queue_node_t *)malloc(sizeof(queue_node_t));
p->data = x;
// 2.插入到隊尾指針的后一個位置
p->next = queue->rear->next;
queue->rear->next = p;
// 3.更新隊尾指針
queue->rear = queue->rear->next;
return 0;
}
// 出隊操作碱茁，成功涕癣，返回0官脓；失敗协怒，-1
int delete_from_link_queue(link_queue_t *queue,
datatype_t *px)
{
// 如果隊列不存在或隊列為空，出隊失敗
if(queue == NULL || is_empty_of_link_queue(queue))
return -1;
// 1.定位出隊的數(shù)據(jù)結(jié)點的位置
queue_node_t *p = queue->front->next;
// 2.將該結(jié)點從鏈?zhǔn)疥犃兄幸瞥? queue->front->next = p->next;
// 3.如果需要卑笨，將待出隊元素的值傳出
if(px != NULL)
*px = p->data;
// 4.釋放結(jié)點空間
free(p);
// 注意：如果出隊之后孕暇，隊列為空，重定位尾指針的位置
if(queue->front->next == NULL)
queue->rear = queue->front;
return 0;
}
// 清空鏈?zhǔn)疥犃?void clear_link_queue(link_queue_t *queue)
{
queue_node_t *p = NULL;
// 循環(huán)的采用頭刪法刪除鏈?zhǔn)疥犃械臄?shù)據(jù)結(jié)點直到隊列為空
while(!is_empty_of_link_queue(queue))
{
p = queue->front->next;
queue->front->next = p->next;
free(p);
}
}
// 銷毀鏈?zhǔn)疥犃?void destroy_link_queue(link_queue_t *queue)
{
// 清空鏈?zhǔn)疥犃? clear_link_queue(queue);
// 釋放鏈?zhǔn)疥犃蓄^結(jié)點空間
free(queue->front);
// 釋放隊首和隊尾指針結(jié)點空間
free(queue);
}
// 根據(jù)實際datatype_t類型打印數(shù)據(jù)
static void print_data(datatype_t x)
{
printf("%d ", x);
}
// 遍歷打印鏈?zhǔn)疥犃械臄?shù)據(jù)結(jié)點
void print_data_info_of_link_queue(link_queue_t *queue)
{
queue_node_t *p = queue->front;
printf("linkqueue : ");
while(p->next != NULL)
{
p = p->next;
print_data(p->data);
}
printf("\n");
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
