基于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;}