数据结构——顺序队列与链式队列的实现-2

简介: 数据结构——顺序队列与链式队列的实现

数据结构——顺序队列与链式队列的实现-1

https://developer.aliyun.com/article/1507982


6、出队

C语言实现如下所示:

bool out_seqqueue(seq_pqueue q,datatype *D)
{
  //判断队列是否空
  if(is_empty_seqqueue(q)){
    printf("队列已空!\n");
    return false;
  }
 
  //出队
  q->front=(q->front+1)%MAXSIZE;
  *D=q->data[q->front];
 
  return true;
}


7、打印队列

C语言实现如下所示:

void show_seqqueue(seq_pqueue q)
{
  int i;
  if(is_empty_seqqueue(q))
    return;
  //非空时,从对头打印到队尾
  for(i=(q->front+1)%MAXSIZE;i!=(q->rear+1)%MAXSIZE;i=(i+1)%MAXSIZE)
  {
    printf("%d\t",q->data[i]);
  }
  printf("\n");
}


8、队列的顺序表实现源码

seqqueue.h

#ifndef __SEQQUEUE_H__
#define __SEQQUEUE_H__
 
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
#define MAXSIZE 10
typedef int datatype;
 
typedef struct seqqueue{
  datatype data[MAXSIZE];
  int front,rear;
}seq_queue,*seq_pqueue;
 
extern seq_pqueue init1_seqqueue(void);
extern void init_seqqueue(seq_pqueue *Q);
extern bool is_full_seqqueue(seq_pqueue q);
extern bool is_empty_seqqueue(seq_pqueue q);
extern bool in_seqqueue(datatype data,seq_pqueue q);
extern bool out_seqqueue(seq_pqueue q,datatype *D);
extern void show_seqqueue(seq_pqueue q);
 
#endif


seqqueue.c

#include "seqqueue.h"
 
seq_pqueue init1_seqqueue(void)
{
  seq_pqueue q;
  q=(seq_pqueue)malloc(sizeof(seq_queue));
  if(q==NULL)
  {
    perror("malloc");
    exit(-1);
  }
  q->front=q->rear=MAXSIZE-1;
 
  return q;
}
 
void init_seqqueue(seq_pqueue *Q)
{
  *Q=(seq_pqueue)malloc(sizeof(seq_queue));
  if((*Q)==NULL)
  {
    perror("malloc");
    exit(-1);
  }
  (*Q)->front=(*Q)->rear=MAXSIZE-1;
  
  return;
}
 
//判断队列是否满
bool is_full_seqqueue(seq_pqueue q)
{
  if((q->rear+1)%MAXSIZE == q->front)
    return true;
  else
    return false;
}
 
//入队
bool in_seqqueue(datatype data,seq_pqueue q)
{
  //判断队列是否满
  if(is_full_seqqueue(q)){
    printf("队列已满!\n");
    return false;
  }
 
  //入队
  q->rear=(q->rear+1)%MAXSIZE;
  q->data[q->rear]=data;
  return true;
}
 
//判断队列是否空
bool is_empty_seqqueue(seq_pqueue q)
{
  if(q->rear == q->front)
    return true;
  else
    return false;
}
 
//出队
bool out_seqqueue(seq_pqueue q,datatype *D)
{
  //判断队列是否空
  if(is_empty_seqqueue(q)){
    printf("队列已空!\n");
    return false;
  }
 
  //出队
  q->front=(q->front+1)%MAXSIZE;
  *D=q->data[q->front];
 
  return true;
}
 
void show_seqqueue(seq_pqueue q)
{
  int i;
  if(is_empty_seqqueue(q))
    return;
  //非空时,从对头打印到队尾
  for(i=(q->front+1)%MAXSIZE;i!=(q->rear+1)%MAXSIZE;i=(i+1)%MAXSIZE)
  {
    printf("%d\t",q->data[i]);
  }
  printf("\n");
}


test.c

#include "seqqueue.h"
/* 用循环队列实现如下功能:
 * 用户从键盘输入整数,程序将其入队;
 * 用户从键盘输入字母,程序将队头元素出队;
 * 并在每一次出队和入队之后打印队列元素。
 */
int main(int argc, const char *argv[])
{
  seq_pqueue q;
  datatype data,t,ret;
  
  init_seqqueue(&q);
 
  while(1)
  {
    printf("请输入一个整数或字符:");
    ret=scanf("%d",&data);
    
    //输入整数时,入队
    if(ret == 1)
    {
      if(in_seqqueue(data,q))
        show_seqqueue(q);
    }
    else
    {
      //输入为字符时
      if(out_seqqueue(q,&t))
      {
        printf("out:%d\n",t);
        show_seqqueue(q);
      }
      //清空输入缓冲区
      while(getchar()!='\n');
    }
  }
  return 0;
}


Makefile

CC = gcc
CFLAGS = -o0 -g -Wall
 
SRC=seqqueue.c test.c
OBJS=test
 
$(OBJS):$(SRC)
  $(CC) $(CFLAGS) -o $@ $^
 
.PHONY:clean
clean:
  rm -rf $(OBJS) *.o
  • "-o0"表示优化级别为0,即关闭优化。这将导致生成的可执行文件较大,但是可以方便地进行调试。
  • "-g"表示生成调试信息,以便在调试程序时可以查看变量的值、函数的调用栈等信息。
  • "-Wall"表示启用所有警告,编译器将会显示所有可能的警告信息,帮助开发人员发现潜在的问题。


编译结果测试:


5b637949016014d18b1a1a44c6464e4b_886a20dd8a924d75a7c5bdd8bc211f59.png


四、队列的链表实现

1、数据结构定义

对于链表,在进行 队列的定义 之前,我们需要考虑以下几个点:

 1)队列数据的存储方式,以及队列数据的数据类型;

 2)队列的大小;

 3)队首指针;

 4)队尾指针;


我们可以定义一个 队列结构体,C语言实现如下所示:

typedef int datatype;
 
typedef struct linkqueuenode{ 
  datatype data;                    /* 数据域 */
  struct linkqueuenode *next;       /* 指针域 */
}linkqueue_node,*linkqueue_pnode;
 
typedef struct linkqueue{
  linkqueue_pnode front,rear;       /* 链队列指针 */
}link_queue,*link_pqueue;


2、初始化创造队列

C语言实现如下所示:

void init_linkqueue(link_pqueue *Q)
{
  //申请front和rear的空间
  *Q=(link_pqueue)malloc(sizeof(link_queue));
  if((*Q)==NULL)
  {
    perror("malloc");
    exit(-1);
  }
  //申请头结点空间
  (*Q)->front=(linkqueue_pnode)malloc(sizeof(linkqueue_node));
  if((*Q)->front==NULL)
  {
    perror("malloc");
    exit(-1) ;
  }
 
  (*Q)->front->next=NULL;
  (*Q)->rear=(*Q)->front;
 
  return;
}


3、判断队列是否空

C语言实现如下所示:

bool is_empty_linkqueue(link_pqueue q)
{
  if(q->rear == q->front)
    return true;
  else
    return false;
}


4、入队

C语言实现如下所示:

bool in_linkqueue(datatype data,link_pqueue q)
{
  linkqueue_pnode  new;
 
  //申请数据结点空间
  new=(linkqueue_pnode)malloc(sizeof(linkqueue_node));
  if(new==NULL)
  {
    puts("入队失败!");
    return false;
  }
  //将数据存储在申请的空间
  new->data=data;
  
  //将new指向的结点插入到链式队列中
  new->next=q->rear->next;
  q->rear->next=new;
  
  //让rear指针指向新的队尾结点
  q->rear=q->rear->next;
 
  return true;
}


5、出队

C语言实现如下所示:

bool out_linkqueue(link_pqueue q,datatype *D)
{
  linkqueue_pnode t;
  //判断队列是否空
  if(is_empty_linkqueue(q)){
    printf("队列已空!\n");
    return false;
  }
 
  //出队
  t=q->front;
  q->front =q->front->next;
  *D=q->front->data;
  free(t);
 
  return true;
}


6、打印队列

C语言实现如下所示:

void show_linkqueue(link_pqueue q)
{
  linkqueue_pnode p;
  if(is_empty_linkqueue(q))
    return;
  //非空时,从对头打印到队尾
  for(p=q->front->next;p!=NULL;p=p->next)
  {
    printf("%d\t",p->data);
  }
  printf("\n");
}


7、队列的链表实现源码

linkqueue.h

#ifndef __LINKQUEUE_H__
#define __LINKQUEUE_H__
 
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
typedef int datatype;
 
typedef struct linkqueuenode{
  datatype data;
  struct linkqueuenode *next;
}linkqueue_node,*linkqueue_pnode;
 
typedef struct linkqueue{
  linkqueue_pnode front,rear;
}link_queue,*link_pqueue;
 
extern void init_linkqueue(link_pqueue *Q);
extern bool is_empty_linkqueue(link_pqueue q);
extern bool in_linkqueue(datatype data,link_pqueue q);
extern bool out_linkqueue(link_pqueue q,datatype *D);
extern void show_linkqueue(link_pqueue q);
 
#endif


linkqueue.c      

#include "linkqueue.h"
 
void init_linkqueue(link_pqueue *Q)
{
  //申请front和rear的空间
  *Q=(link_pqueue)malloc(sizeof(link_queue));
  if((*Q)==NULL)
  {
    perror("malloc");
    exit(-1);
  }
  //申请头结点空间
  (*Q)->front=(linkqueue_pnode)malloc(sizeof(linkqueue_node));
  if((*Q)->front==NULL)
  {
    perror("malloc");
    exit(-1) ;
  }
 
  (*Q)->front->next=NULL;
  (*Q)->rear=(*Q)->front;
 
  return;
}
 
//入队
bool in_linkqueue(datatype data,link_pqueue q)
{
  linkqueue_pnode  new;
 
  //申请数据结点空间
  new=(linkqueue_pnode)malloc(sizeof(linkqueue_node));
  if(new==NULL)
  {
    puts("入队失败!");
    return false;
  }
  //将数据存储在申请的空间
  new->data=data;
  
  //将new指向的结点插入到链式队列中
  new->next=q->rear->next;
  q->rear->next=new;
  
  //让rear指针指向新的队尾结点
  q->rear=q->rear->next;
 
  return true;
}
 
bool is_empty_linkqueue(link_pqueue q)
{
  if(q->rear == q->front)
    return true;
  else
    return false;
}
 
//出队
bool out_linkqueue(link_pqueue q,datatype *D)
{
  linkqueue_pnode t;
  //判断队列是否空
  if(is_empty_linkqueue(q)){
    printf("队列已空!\n");
    return false;
  }
 
  //出队
  t=q->front;
  q->front =q->front->next;
  *D=q->front->data;
  free(t);
 
  return true;
}
 
void show_linkqueue(link_pqueue q)
{
  linkqueue_pnode p;
  if(is_empty_linkqueue(q))
    return;
  //非空时,从对头打印到队尾
  for(p=q->front->next;p!=NULL;p=p->next)
  {
    printf("%d\t",p->data);
  }
  printf("\n");
}


test.c

#include "linkqueue.h"
/* 用链式队列实现如下功能:
 * 用户从键盘输入整数,程序将其入对;
 * 用户从键盘输入字母,程序将队头元素出队;
 * 并在每一次出队和入队之后打印队列元素。
 */
int main(int argc, const char *argv[])
{
  link_pqueue q;
  datatype data,t,ret;
  
  init_linkqueue(&q);
 
  while(1)
  {
    printf("请输入一个整数或字符:");
    ret=scanf("%d",&data);
    
    //输入整数时,入对
    if(ret == 1)
    {
      if(in_linkqueue(data,q))
        show_linkqueue(q);
    }
    else
    {
      //输入为字符时
      if(out_linkqueue(q,&t))
      {
        printf("out:%d\n",t);
        show_linkqueue(q);
      }
      //清空输入缓冲区
      while(getchar()!='\n');
    }
  }
  return 0;
}
 


Makefile

CC = gcc
CFLAGS = -o0 -g -Wall
 
SRC=linkqueue.c test.c
OBJS=test
 
$(OBJS):$(SRC)
  $(CC) $(CFLAGS) -o $@ $^
 
.PHONY:clean
clean:
  rm -rf $(OBJS) *.o
  • "-o0"表示优化级别为0,即关闭优化。这将导致生成的可执行文件较大,但是可以方便地进行调试。
  • "-g"表示生成调试信息,以便在调试程序时可以查看变量的值、函数的调用栈等信息。
  • "-Wall"表示启用所有警告,编译器将会显示所有可能的警告信息,帮助开发人员发现潜在的问题。

编译结果测试:

相关文章
|
28天前
|
存储 Java 容器
深入浅出 栈和队列(附加循环队列、双端队列)
深入浅出 栈和队列(附加循环队列、双端队列)
|
11天前
数据结构——栈和队列
数据结构——栈和队列
13 1
|
22天前
|
存储 缓存 算法
【数据结构】栈和队列的模拟实现(两个方式实现)
【数据结构】栈和队列的模拟实现(两个方式实现)
|
5天前
|
Python
数据结构===队列
数据结构===队列
|
1天前
|
算法
【C/数据结构和算法】:栈和队列
【C/数据结构和算法】:栈和队列
6 1
|
7天前
|
算法
$停车场管理系统 栈与队列
$停车场管理系统 栈与队列
8 1
|
11天前
|
存储 算法 程序员
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
18 4
|
11天前
数据结构 栈 / 队列(第9天)
数据结构 栈 / 队列(第9天)
|
14天前
|
算法 调度 Python
数据结构与算法-队列篇
数据结构与算法-队列篇
13 3
|
19天前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
16 2