数据结构——顺序队列与链式队列的实现-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"表示启用所有警告,编译器将会显示所有可能的警告信息,帮助开发人员发现潜在的问题。

编译结果测试:

目录
打赏
0
2
2
1
45
分享
相关文章
|
3月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
332 9
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
4月前
|
数据结构之 - 双端队列数据结构详解: 从基础到实现
数据结构之 - 双端队列数据结构详解: 从基础到实现
173 5
|
1月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
43 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
46 9
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
38 7
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
99 5
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
4月前
初步认识栈和队列
初步认识栈和队列
73 10

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等