栈与队列都是具有特殊存取方式的线性表，栈属于先进后出（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, , sizeof(fifo));
fifo_ptr->write_ptr = ;
fifo_ptr->read_ptr = ;
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) == -){
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 = ; 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) == ){
fifo_ptr->flag = EMPTY;
}
//printf("read_ptr = %d \n", fifo_ptr->read_ptr);
return data;
}else{
printf("fifo is empty, read invalide\n");
return -;
} return -;
}
我们可以写一个测试代码来测试它的性能：
#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(){
pthread_mutex_lock(&lock_fifo);
fifo_in(myfifo, );
pthread_mutex_unlock(&lock_fifo);
printf("producer1 put 1 into myfifo\n");
usleep();
}
return((void*));
} void * producer_thread2(void *pin){
pin = NULL;
while(){
pthread_mutex_lock(&lock_fifo);
fifo_in(myfifo, );
pthread_mutex_unlock(&lock_fifo);
printf("producer2 put 2 into myfifo\n");
usleep();
}
return((void*));
} void * consumer_thread1(void *pin){
int require = ;
pin = NULL; while(){
pthread_mutex_lock(&lock_fifo);
require = fifo_out(myfifo);
pthread_mutex_unlock(&lock_fifo);
printf(" consumer1 get %d form myfifo\n", require);
usleep();
}
return((void*));
} void * consumer_thread2(void *pin){
int require = ;
pin = NULL; while(){
pthread_mutex_lock(&lock_fifo);
require = fifo_out(myfifo);
pthread_mutex_unlock(&lock_fifo);
printf(" consumer2 get %d form myfifo\n", require);
usleep();
}
return((void*));
} void keyboard_exit(int signo){
printf("exit by keyboard \n");
fifo_destroy(myfifo);
_exit();
} 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, );
pthread_create(&th_producer2, NULL, producer_thread2, );
pthread_create(&th_consumer1, NULL, consumer_thread1, );
pthread_create(&th_consumer2, NULL, consumer_thread2, ); pthread_join(th_producer1, &ret);
pthread_join(th_producer2, &ret);
pthread_join(th_consumer1, &ret);
pthread_join(th_consumer2, &ret); while(){
printf("thread error\n");
}
return ;
}
写一个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 =
producer1 put into myfifo
write_ptr =
producer2 put into myfifo
read_ptr =
consumer1 get form myfifo
read_ptr =
consumer2 get form myfifo
fifo is empty, read invalide
consumer1 get - form myfifo
fifo is empty, read invalide
consumer2 get - form myfifo
write_ptr =
producer2 put into myfifo
write_ptr =
producer1 put into myfifo
read_ptr =
consumer1 get form myfifo
read_ptr =
consumer2 get form myfifo
write_ptr =
producer2 put into myfifo
read_ptr =
。。。。
。。。。
^Cexit by keyboard
destroy fifo
