数据结构小结（三）栈与队列

旧城等待， 2022-08-18 12:22 138阅读 0赞

## 第三章 栈 与 队列 ##

## 前言 ##

上一篇说了栈，这篇来说说队列，依然是使用数组与链表这两种

数据结构来具体实现。

## 队列 ##

队列（queue) 也是表，然而，使用队列时插入在一端进行而在另一端进行删除操作。

对与队列而言，不论是使用队列或者使用链表都是快速的O（1）时间完成操作。

### 核心思想 ###

先进先出

### 队列的数组实现 ###

### 几个需要注意的点 ###

队列可以使用数组与链表实现

数组实现：

其实数组实现就是我们常说的循环队列，循环队列的应用很多，比如作为缓冲区使用，内核就

是使用队列原理实现的内核缓冲区。

然而更重要的就是判断空队列，判断满队列的方法了，根据设置不同方法也不尽相同， 我们这

里使用的是少用一块空间的方法，判断队列空或者满。当然我们这里也是不保证线程安全的，

如果你需要保证线程安全，简单的就加一把锁，多处理器加自旋锁。也可以考虑无锁技术。

### 数组实现队列的一些前提 ###

\[c\]

\#define MAX 10

\#define SUCCESS 0

\#define FAIL -1

/\*这是一个循环队列，使用少用一个空间的办法解决判满判空的问题\*/

typedef struct queue\{

int front;

int rear ;

int count;

int \* queue\_array; /\*这里使用一个指针也是为了以后能动态开辟大小空间\*/

/\*在linux kernel 中也有int \* queue\_array\[0\] 这

种写法，都是为了动态扩大\*/

\}queue;

\[/c\]

### 创建队列 ###

\[c\]

queue \* queue\_create(void)\{

queue \* Q;

Q = (queue \*)malloc(sizeof(struct queue));

Q->queue\_array = (int \*)malloc(sizeof(int) \* MAX);

Q->front = Q->rear = MAX -1;

Q->count = 0;

return Q;

\[\\c\]  
<h3>入队操作</h3>  
\[c\]

int queue\_in(queue \* Q,int num)\{

if(!Q)\{

return FAIL;

if((Q->rear+1) % MAX == Q->front)\{

return FAIL;

\}else\{

Q->rear = (Q->rear + 1)%MAX;

Q->queue\_array\[Q->rear\] = num;

Q->count++;

return SUCCESS;

\[\\c\]  
<h3>出队操作</h3>  
\[c\]

int queue\_out(queue \* Q)\{

if(!Q)\{

return FAIL;

if(Q->front == Q->rear)\{

return FAIL;

\}else\{

Q->front = (Q->front+1)%MAX;

Q->count--;

return Q->queue\_array\[Q->front\];

\[/c\]

### 判断队满 ###

\[c\]

int EmptyisQueue(queue \*Q)\{

if(Q->front == Q->rear)\{

return SUCCESS;

\}else\{

return FAIL;

\[/c\]

## 队列的链表实现 ##

前提条件

\[c\]

typedef struct node\{

int data;

struct node \*next;

\}\_node;

typedef struct \_node\{

\_node \*head;

\_node \*tail ;

int count ;

\}\_ctl;

\[/c\]

### 入队操作 ###

\[c\]

void que\_inq(\_ctl \*ctl,\_node \*node)\{

if(NULL == ctl || NULL == node)\{

return ;

if(!ctl->count)\{

ctl->head = node ;

\}else\{

ctl->tail->next = node ;

ctl->tail = node ;

node->next = NULL;

ctl->count++;

\[/c\]

### 出队操作 ###

\[c\]

\_node \* que\_deq(\_ctl \* ctl)\{

\_node \*rst = NULL;

if(NULL == ctl)\{

return NULL;

rst = ctl->head;

if(rst)\{

ctl->head = rst->next;

ctl->count--;

rst->next = NULL;

return rst;

\[/c\]

### 删除一个队列 ###

\[c\]

void que\_del(\_ctl \*ctl)\{

\_node \*pos = NULL;

if(NULL == ctl)\{

return ;

pos = ctl->head;

while(pos != NULL)\{

ctl->head = pos->next;

free(pos);

pos = ctl->head;

\[/c\]

### 创建一个队列 ###

\[c\]

void que\_create(\_ctl \*ctl ,int len)\{

\_node \*pnt = NULL ;

int fact = 0 ;

if(NULL == ctl || len < 1)\{

return ;

while(fact < len)\{

pnt = (\_node \*)malloc(sizeof(\_node));

pnt->data = fact + 1;

que\_inq(ctl,pnt);

fact++;

\[/c\]

查看原文：[http://zmrlinux.com/2015/12/20/%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84%e5%b0%8f%e7%bb%93-%ef%bc%88%e4%b8%89%ef%bc%89%e6%a0%88%e4%b8%8e%e9%98%9f%e5%88%97/][http_zmrlinux.com_2015_12_20_e6_95_b0_e6_8d_ae_e7_bb_93_e6_9e_84_e5_b0_8f_e7_bb_93-_ef_bc_88_e4_b8_89_ef_bc_89_e6_a0_88_e4_b8_8e_e9_98_9f_e5_88_97]

[http_zmrlinux.com_2015_12_20_e6_95_b0_e6_8d_ae_e7_bb_93_e6_9e_84_e5_b0_8f_e7_bb_93-_ef_bc_88_e4_b8_89_ef_bc_89_e6_a0_88_e4_b8_8e_e9_98_9f_e5_88_97]: http://zmrlinux.com/2015/12/20/%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84%e5%b0%8f%e7%bb%93-%ef%bc%88%e4%b8%89%ef%bc%89%e6%a0%88%e4%b8%8e%e9%98%9f%e5%88%97/