栈与队列都是具有特殊存取方式的线性表，栈属于先进后出（FILO），而队列则是先进先出（FIFO）。栈能够将递归问题转化为非递归问题，这是它的一个重要特性。除了FILO、FIFO这样的最普遍存取方式外，还有一些扩展的数据结构，如双端队列、双栈、超队列、超栈等，它们是一种扩展与变异结构。
线性表有顺序存储和链接存储两类，这是针对计算机的线性存储空间作出的分类。前者可以是数组，后者可以是链表。字符串是线性表最常见的应用。
这里我用C语言实现了一个基于数组环形队列，它具有固定的队列空间。相比于链表实现，它非常小巧和高效，特别是在负载可预计的情况下。
//fifo.h #ifndef __FIFO_H__ #define __FIFO_H__ #define FIFO_LENGTH 20 #define EMPTY 0x00 #define FULL 0x01 #define NORMAL 0x02 typedef struct require_fifo{ int item[FIFO_LENGTH]; int read_ptr; int write_ptr; int flag; }fifo; extern fifo* fifo_create(void); extern void fifo_destroy(fifo* fifo_ptr); extern void fifo_in(fifo* fifo_ptr, int data); extern int fifo_out(fifo* fifo_ptr); #endif
//fifo.c #include <stdio.h> #include <unistd.h> #include <stdlib.h> #include <memory.h> #include "fifo.h" fifo* fifo_create(void); void fifo_destroy(fifo* fifo_ptr); void fifo_in(fifo* fifo_ptr, int data); int fifo_out(fifo* fifo_ptr); fifo* fifo_create(void){ fifo *fifo_ptr = malloc(sizeof(fifo)); memset(fifo_ptr, 0, sizeof(fifo)); fifo_ptr->write_ptr = 0; fifo_ptr->read_ptr = 0; fifo_ptr->flag = EMPTY; return fifo_ptr; } void fifo_destroy(fifo* fifo_ptr){ free(fifo_ptr); printf("destroy fifo \n"); } void fifo_in(fifo* fifo_ptr, int data){ if(fifo_ptr->flag != FULL ){ fifo_ptr->item[fifo_ptr->write_ptr] = data; fifo_ptr->write_ptr ++; fifo_ptr->write_ptr %= FIFO_LENGTH; if((fifo_ptr->write_ptr - fifo_ptr->read_ptr) == -1){ fifo_ptr->flag = FULL; }else{ fifo_ptr->flag = NORMAL; } //printf("write_ptr = %d \n", fifo_ptr->write_ptr); }else{ printf("fifo is full, write invalide\n"); } } int fifo_out(fifo* fifo_ptr){ int data = 0; if(fifo_ptr->flag != EMPTY){ data = fifo_ptr->item[fifo_ptr->read_ptr]; fifo_ptr->read_ptr ++; fifo_ptr->read_ptr %= FIFO_LENGTH; if((fifo_ptr->write_ptr - fifo_ptr->read_ptr) == 0){ fifo_ptr->flag = EMPTY; } //printf("read_ptr = %d \n", fifo_ptr->read_ptr); return data; }else{ printf("fifo is empty, read invalide\n"); return -1; } return -1; }
我们可以写一个测试代码来测试它的性能：
#include <stdio.h> #include <pthread.h> #include <signal.h> #include <unistd.h> #include <sys/types.h> #include "../fifo.h" pthread_mutex_t lock_fifo; fifo* myfifo; void * producer_thread1(void *pin){ pin = NULL; while(1){ pthread_mutex_lock(&lock_fifo); fifo_in(myfifo, 1); pthread_mutex_unlock(&lock_fifo); printf("producer1 put 1 into myfifo\n"); usleep(2000000); } return((void*)0); } void * producer_thread2(void *pin){ pin = NULL; while(1){ pthread_mutex_lock(&lock_fifo); fifo_in(myfifo, 2); pthread_mutex_unlock(&lock_fifo); printf("producer2 put 2 into myfifo\n"); usleep(1500000); } return((void*)0); } void * consumer_thread1(void *pin){ int require = 0; pin = NULL; while(1){ pthread_mutex_lock(&lock_fifo); require = fifo_out(myfifo); pthread_mutex_unlock(&lock_fifo); printf(" consumer1 get %d form myfifo\n", require); usleep(1000000); } return((void*)0); } void * consumer_thread2(void *pin){ int require = 0; pin = NULL; while(1){ pthread_mutex_lock(&lock_fifo); require = fifo_out(myfifo); pthread_mutex_unlock(&lock_fifo); printf(" consumer2 get %d form myfifo\n", require); usleep(1000000); } return((void*)0); } void keyboard_exit(int signo){ printf("exit by keyboard \n"); fifo_destroy(myfifo); _exit(0); } int main(){ pthread_t th_producer1, th_producer2, th_consumer1, th_consumer2; void * ret; pthread_mutex_init(&lock_fifo, NULL); myfifo = fifo_create(); signal(SIGINT, keyboard_exit); pthread_create(&th_producer1, NULL, producer_thread1, 0); pthread_create(&th_producer2, NULL, producer_thread2, 0); pthread_create(&th_consumer1, NULL, consumer_thread1, 0); pthread_create(&th_consumer2, NULL, consumer_thread2, 0); pthread_join(th_producer1, &ret); pthread_join(th_producer2, &ret); pthread_join(th_consumer1, &ret); pthread_join(th_consumer2, &ret); while(1){ printf("thread error\n"); } return 1; }
写一个gcc的Makefile文件来编译链接：
CC = gcc CFLAGS := -g -Wall LIB := -lpthread OBJ = ../fifo.o ./test.o all: demo demo:test fifo $(CC) $(CFLAGS) -o ./demo $(OBJ) $(LIB) test: $(CC) $(CFLAGS) -o ./test.o -c ./test.c fifo: $(CC) $(CFLAGS) -o ../fifo.o -c ../fifo.c clean: rm ./test.o ./demo ../fifo.o .PHONY: $(PHONY) clean
在test目录下运行./demo。
输出结果：
write_ptr = 1 producer1 put 1 into myfifo write_ptr = 2 producer2 put 2 into myfifo read_ptr = 1 consumer1 get 1 form myfifo read_ptr = 2 consumer2 get 2 form myfifo fifo is empty, read invalide consumer1 get -1 form myfifo fifo is empty, read invalide consumer2 get -1 form myfifo write_ptr = 3 producer2 put 2 into myfifo write_ptr = 4 producer1 put 1 into myfifo read_ptr = 3 consumer1 get 2 form myfifo read_ptr = 4 consumer2 get 1 form myfifo write_ptr = 5 producer2 put 2 into myfifo read_ptr = 5 。。。。 。。。。 ^Cexit by keyboard destroy fifo