基于C/S架构的排队系统

一 问题来源

2014腾讯研发工程师笔试题：请设计一个排队系统，能够让每个进入队伍的用户都能看到自己在 中所处的位置和变化。队伍可能随时有人加入和退出，当有人退出影响到用户的位置排名时需要即时反馈到用户。

二 思路

排队即队列，要保证先进先出原则，队尾进，队头出。我把问题划分问两部分来解决：客户端和服务器端。客户端留给用户输入命令行，如“add x”，表示将用户x加入队列中，输入“rm y”表示将用户y从队列中删除，但是必须强调得是，加入某个用户必须在队尾实施插入操作，删除某个用户，此用户必须是队头用户，这是为了遵守队列“FIFO”原则，输入“show xx”表示显示用户xx的在队列中排名（位置）。

三 队列结构

四 运行效果

客户端：

服务器端：

五 编程体会

程序分为客户端与服务器端两部分，每部分都需要用到套接字编程，常用的操作有建立套接字、连接服务器、读写套接字等等。在服务器端，原本使用了“fork”创建子进程，在生成的子进程中对队列进行操作，如插入、删除结点，但是不断"fork"出的子进程有独立的地址空间，会使得队列无法连续生成，每个子进程都只能生成一个结点。所以回避了“fork”。这也是我调试了半天的经验。本系统使用了命令行的形式来对队列进行操作，能够完成题目的入队、出队和查看排名的要求，但实现的时候也有些不妥。比如如果某个用户离开队列，那么其他的用户怎样立即感知，这就不得不用“show XXX”这样的命令。所以还是有缺陷的，另外，gets函数比较危险，sscanf和sprintf函数不常用，但确实很有用。

六 代码

客户端：

/* * Copyright (C) 2013 wangzhicheng <2363702560@qq.com> *This program is free software; you can redistribute it and/or modify *it under the terms of the GNU Gernal Public License as published by *the Free software Foundation, version1.0 * Author: *     wangzhicheng <2363702560@qq.com> *     2013/10/6 * */#include <stdio.h>#include <unistd.h>#include <stdlib.h>#include <string.h>#include <sys/types.h>#include <pthread.h>#include <sys/socket.h>#include <signal.h>#include <netinet/in.h>#include <ctype.h>#define LEN 20/* * to define a Person structure and initialize * */typedef struct User {    char name[LEN];    unsigned int pos;}User;/* * the linked queue structure  * */typedef struct QueueNode {    User user;    struct QueueNode *next;}QueueNode;typedef struct LinkedQueue {    QueueNode *front;    QueueNode *rear;}LinkedQueue;pthread_mutex_t mutext;/* * to parse the command line  * @type: the type argument as add, rm and show  * @val: the value argument as username  * */int parse_cmdline(char *cmdline, char *type, char *val) {    int err = 0;    char *cp;    /*     * change the first '\n' into '\0'     * */    cp = strchr(cmdline, '\n');     if(cp) {*cp = '\0';    }    if(sscanf(cmdline, "%5s %12s", type, val) != 2) err = 1;    if(!strcmp(type, "add") && !strcmp(type, "rm") && !strcmp(type, "show")) {    err = 1;    }    return err;}/* * a function of queue system can add, remove or query  * @type: the type of cmdline as add, rm, show * @val: the username  * @resultstring: the result string which should return to the client socket * */void Do(LinkedQueue **Q, char *type, char *val, char *resultstring) {    QueueNode *p;            // point to the current node    QueueNode *pre;          // point to the previous of current node     QueueNode *r;            // point to the node should be deleted     int find;               // whether the node is located     if(strcmp(type, "add") == 0) {/* * to check whether check repeatedly * */find = 0;p = (*Q)->front;while(p) {    if(strcmp(p->user.name, val) == 0) {find = 1;break;    }    p = p->next;}if(find) {    strcpy(resultstring, "add repeatedly!\n");    return;}/* * to add a user to the queue system  * *//* * to create a new queue node  * */p = (QueueNode *)malloc(sizeof(QueueNode));if(!p) {         // Maybe this will hardly happen    fprintf(stderr, "memory error!\n");    exit(EXIT_FAILURE);}p->next = 0;User user;strncpy(user.name, val, 16);user.pos = 0;p->user = user;/* * to add the new queue node to the queue system * */if((*Q)->rear == NULL) {   // the queue system is empty    p->user.pos = 1;    (*Q)->front = p;    (*Q)->rear = p;}else {        // insert into the rear of queue system    p->user.pos = (*Q)->rear->user.pos + 1;    (*Q)->rear->next = p;    (*Q)->rear = p;}strcpy(resultstring, "add a new user to the queue system!\n");    }    /*     * to remove a node from the queue system     * */    else if(strcmp(type, "rm") == 0) {if(!(*Q)->front) {    // the queue system is empty    strcpy(resultstring, "remove failed, the queue system is empty!\n");    return;}else {    if(strcmp((*Q)->front->user.name, val)) {strcpy(resultstring, "You are not the head of queue!\n");return;    }    else {r = (*Q)->front;(*Q)->front = r->next;free(r);if(!(*Q)->front) (*Q)->rear = NULL;    }    strcpy(resultstring, "the head of queue has been deleted!\n");}/* * change the rank  * */p = (*Q)->front;while(p) {    p->user.pos--;    p = p->next;}    }    /*     * to show the rank      * */    else {if(!(*Q)->front) {    // the queue system is empty    strcpy(resultstring, "show failed, the queue system is empty!\n");        }        find = 0;p = (*Q)->front;while(p) {    if(strcmp(p->user.name, val) == 0) {sprintf(resultstring,"the rank is:%d", p->user.pos);find = 1;break;    }    else p = p->next;}if(!find) strcpy(resultstring, "show failed, no user!\n");    }}int main() {    /*     * create a empty queue system      * */    LinkedQueue *Q = (LinkedQueue *)malloc(sizeof(LinkedQueue));    Q->front = NULL;    Q->rear = NULL;    /*     * the socket fd is same the file descriptor     * */    int server_sockfd = -1;    int client_sockfd = -1;    int client_len = 0;    /*     * to define socket address     * */    struct sockaddr_in server_addr;    struct sockaddr_in client_addr;    /*     * to create a socket      * a socket contains domain, type and protocal     * */    server_sockfd = socket(AF_INET, SOCK_STREAM, 0);//  bzero(&server_addr, sizeof(server_addr));  // to clear the server_addr    /*     * to initialize the socket address      * */    server_addr.sin_family = AF_INET;    server_addr.sin_addr.s_addr = htonl(INADDR_ANY);    /*     * pay attention     * the port should be same with the port from client      * */    server_addr.sin_port = htons(9736);    /*     * to bind the sockect and its address      * */    bind(server_sockfd, (struct sockaddr *)&server_addr, sizeof(server_addr));    /*     * to listen the port      * */    listen(server_sockfd, 5);    /*     * to ignore child processes which stop      * */    signal(SIGCHLD, SIG_IGN);    char msg[LEN];    char cmdline[LEN];    char type[5];    char val[12];    char resultstring[2 * LEN];       while(1) {client_len = sizeof(client_addr);        printf("server is waiting...\n");        /*  *  to accept a connect from a client socket          * */client_sockfd = accept(server_sockfd, (struct sockaddr *)&client_addr, &client_len);        /*         * let the child process to deal with   * *//* * read data from socket  * */read(client_sockfd, &cmdline, sizeof(cmdline)); if(parse_cmdline(cmdline, type, val)) {    strcpy(resultstring, "cmdline contains error!\n"); }else {    Do(&Q, type, val, resultstring);    /*     * write the data to socket      * */    write(client_sockfd, &resultstring, sizeof(resultstring));}close(client_sockfd);    }    close(server_sockfd);    return 0;}