栈与队列的区别:
栈——先入后出,后入先出;
队列——先入先出,后入后出;
应用举例:
栈:函数调用时会将临时数据压栈;函数返回时再弹出来。
队列:一般,系统中的任务和消息经常使用队列。可以按任务或消息到来的先后顺序执行。
代码实现:
背景:使用C语言,在VS2008环境下,按栈与队列的原理,采用最简单易懂的方式,针对正整型(int)元素实现栈与队列。
原理:栈的存储空间使用数组构造,队列的空间又使用栈来构造,即,使用两个栈实现队列的功能。
文件:libStack.h/c;libQueue.h/c;
一、栈的源代码
libStack.h
#ifndef _LIBSTACK_H
#define _LIBSTACK_H
#ifdef __cplusplus
extern "C" {
#endif
#define STACK_MAX_LEN 2048
typedef struct tagstStack
{
int udwPc; /* 栈顶所在位置,指向空闲位置 */
int a[STACK_MAX_LEN];
}stStack;
/* 创建新的栈 */
extern stStack *stack_new();
/* 栈复位 */
extern void stack_reset(stStack *pstStack);
/* 入栈,栈满时忽略此次操作 */
extern void stack_push(stStack *pstStack,int udwTmp);
/* 出栈,栈空时返回-1 */
extern int stack_pop(stStack *pstStack);
/* 栈判空 1-空 0-非空 */
extern int stack_is_empty(stStack *pstStack);
/* 删除栈 */
extern void stack_delete(stStack *pstStack);
#ifdef __cplusplus
}
#endif
#endif
由于是C语言实现,所以必须添加extern "C"{};
libStack.c
#ifdef __cplusplus
extern "C" {
#endif
#include <malloc.h>
#include <stddef.h>
#include "libStack.h"
/* 创建新的栈 */
stStack *stack_new()
{
stStack *p;
p = (stStack *)malloc(sizeof(stStack));
p->udwPc = 0;
return p;
}
/* 栈复位 */
void stack_reset(stStack *pstStack)
{
if (NULL == pstStack)
{
return;
}
pstStack->udwPc = 0;
}
/* 入栈,栈满时忽略此次操作 */
void stack_push(stStack *pstStack, int udwTmp)
{
if (NULL == pstStack)
{
return;
}
if (STACK_MAX_LEN > pstStack->udwPc)
{
pstStack->a[pstStack->udwPc] = udwTmp;
pstStack->udwPc++;
}
}
/* 出栈,栈空时返回-1 */
int stack_pop(stStack *pstStack)
{
if (NULL == pstStack)
{
return -1;
}
if (0 == pstStack->udwPc)
{
return -1;
}
return pstStack->a[--pstStack->udwPc];
}
/* 栈判空 1-空 0-非空 */
int stack_is_empty(stStack *pstStack)
{
if (NULL == pstStack)
{
/* 空指针默认为空栈 */
return 1;
}
return (0 < pstStack->udwPc)?0:1;
}
/* 删除栈 */
void stack_delete(stStack *pstStack)
{
if (NULL != pstStack)
{
free(pstStack);
}
}
#ifdef __cplusplus
}
#endif
本套实现只支持正整型数,负数被作为异常值处理。
二、队列的实现
这里队列完全是用上述栈实现的,目的只是练习。
libQueue.h
#ifndef _LIBQUEUE_H
#define _LIBQUEUE_H
#ifdef __cplusplus
extern "C" {
#endif
#include "libStack.h"
#define QUEUE_MAX_LEN STACK_MAX_LEN /* 队列大小取决与栈的大小 */
typedef struct tagstQueue
{
int udwCnt;
stStack *pstStack1;
stStack *pstStack2;
}stQueue;
/* 创建新队列 */
extern stQueue *queue_new();
/* 入队,队列已满时忽略此次操作 */
extern void in_queue(stQueue *pstQueue, int udwTmp);
/* 出队,队列为空时返回-1 */
extern int out_queue(stQueue *pstQueue);
/* 删除队列 */
extern void queue_delete(stQueue *pstQueue);
/* 队列判空 1-空 0-非空 */
extern int queue_is_empty(stQueue *pstQueue);
#ifdef __cplusplus
}
#endif
#endif
libQueue.c
#ifdef __cplusplus
extern "C" {
#endif
#include <malloc.h>
#include <stddef.h>
#include "libQueue.h"
/* 创建新队列 */
stQueue *queue_new()
{
stQueue *p;
p = (stQueue *)malloc(sizeof(stQueue));
if (NULL == p)
{
return NULL;
}
p->pstStack1 = stack_new();
if (NULL == p->pstStack1)
{
free(p);
return NULL;
}
p->pstStack2 = stack_new();
if (NULL == p->pstStack2)
{
free(p);
free(p->pstStack1);
return NULL;
}
p->udwCnt = 0;
return p;
}
/* 入队,队列已满时忽略此次操作 */
void in_queue(stQueue *pstQueue, int udwTmp)
{
if (NULL == pstQueue)
{
return;
}
if (QUEUE_MAX_LEN <= pstQueue->udwCnt)
{
return;
}
stack_push(pstQueue->pstStack1, udwTmp);
pstQueue->udwCnt++;
}
/* 出队,队列为空时返回-1 */
int out_queue(stQueue *pstQueue)
{
int ret = -1;
int tmp = 0;
if (NULL == pstQueue)
{
return -1;
}
/* 队列为空 */
if (stack_is_empty(pstQueue->pstStack1))
{
return -1;
}
/* 将栈1内容弹出并压入栈2 */
while(0 != pstQueue->pstStack1->udwPc)
{
tmp = stack_pop(pstQueue->pstStack1);
stack_push(pstQueue->pstStack2, tmp);
}
/* 取栈2顶元素出队 */
ret = stack_pop(pstQueue->pstStack2);
/* 将栈2内容压回栈1 */
while(0 != pstQueue->pstStack2->udwPc)
{
tmp = stack_pop(pstQueue->pstStack2);
stack_push(pstQueue->pstStack1, tmp);
}
pstQueue->udwCnt--;
return ret;
}
/* 删除队列 */
void queue_delete(stQueue *pstQueue)
{
if (NULL == pstQueue)
{
return;
}
if (NULL != pstQueue->pstStack2)
{
free(pstQueue->pstStack2);
}
if (NULL != pstQueue->pstStack1)
{
free(pstQueue->pstStack1);
}
free(pstQueue);
}
/* 队列判空 1-空 0-非空 */
int queue_is_empty(stQueue *pstQueue)
{
return (0 < pstQueue->udwCnt)?0:1;
}
#ifdef __cplusplus
}
#endif
三、简单的测试函数
这里我只写了队列的测试:
// ListStackQueue.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "libStack.h"
#include "libQueue.h"
int _tmain(int argc, _TCHAR* argv[])
{
int i,tmp;
stQueue *pstQ1 = queue_new();
stQueue *pstQ2 = queue_new();
for (i = 0; i < 20; i++)
{
in_queue(pstQ1,i);
}
for (i = 0; i < 20; i++)
{
tmp = out_queue(pstQ1);
printf("%d ",tmp);
}
printf("OK");
getchar();
return 0;
}
输出为:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 OK;实现了队列的先入先出功能。
如果试着将栈的大小调整为5,输出为:0 1 2 3 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 OK。满足超出空间上限不压栈不入队,出栈出队时若栈队为空则返回-1。
分享到:
相关推荐
51单片机串口接收使用队列C语言实现
嵌入式开发中常用的队列实现方式,采用C语言实现队列的入队,出队及打印队列元素
4. 队列与广度优先搜索 5. 环形队列 13. 本阶段总结 II. C语言本质 14. 计算机中数的表示 1. 为什么计算机用二进制计数 2. 不同进制之间的换算 3. 整数的加减运算 3.1. Sign and Magnitude表示法 3.2. 1's ...
应用在嵌入式系统中,C语言实现的循环队列,可直接使用
Linux操作系统使用 · Linux下的文件管理 · VI编辑器 ...· C语言的实现 · 树 嵌入式Linux项目开发流程 · Linux开发环境搭建 · 项目开发流程 · 产品需求分析和选型 · 硬件平台 · 驱动开发 · 系统部署
其次,消息队列能够使得任务与任务、或者任务与中断之间进行通信。在单片机软件系统中,先存入的消息先被执行,实现了抢占式多任务操作系统的功能,使编写的代码结构简洁,层次分明和容易维护,软件运行效率显著提高...
第6章 嵌入式linux c语言基础——数组、指针与结构 168 6.1 数组 169 6.1.1 一维数组 169 6.1.2 字符串 172 6.1.3 二维数组 174 6.2 指针 175 6.2.1 指针的概念 175 6.2.2 指针变量的操作 ...
嵌入式单片机可以用的queue,基于数组实现,简单易用,很好理解,带main测试程序,可以直接加到vs运行测试
优先队列 优先队列(Priority Queue)是一...在C语言中,没有内建的优先队列数据结构,但我们可以使用其他数据结构(如数组或链表)和适当的排序算法来实现。下面是一个简单的基于数组和插入排序的优先队列实现示例:
使用阿里云 消息中间件 稳定强大 paho c 接口 回调函数 十万条数据并发 阿里云消息队列稳定安全 接口使用可以实现任何嵌入式设备,采用qt c++ 的方式 ,调用 paho c 接口
通过大量编程实例重点学习C语言的高级编程知识,包括函数与程序结构、指针、数组、常用算法、库函数的使用等知识,另外,还要学习数据结构的基础内容,包括链表、队列、栈、树、哈希表、图等内容。 第三阶段嵌入式...
基于查表的简易状态机的一种C语言实现,用在嵌入式系统中,不支持多线程消息处理,也就没有消息队列和优先级了。
嵌入式内核M3-飞鸟:ROCHILI内核是一个全新的适用于嵌入式领域的实时内核,它完全由C语言开发,支持多任务、多优先级、抢占式调度。 TROCHILI的含义,取蜂鸟之意,意味着体积小巧、动作灵敏。 内核目前处于测试阶段...
嵌入式系统开发基础——基于ARM微处理器和Linux操作系统[滕英岩][习题解答] 目录第1章 嵌入式系统基础知识 1.1 嵌入式系统的特点及分类 1.1.1 嵌入式系统的特点 1.1.2 嵌入式系统的分类 1.2 嵌入式系统的软硬件...
完整的队列模块,包括队列QInit,QReset,QIsEmpty,QIsHigh,QIsFull,QFreeLen,QDataLen,QInBlock,QOutBlock等函数,已应用到多个项目中,成熟稳定
一个循环队列框架,包括读队列、写队列、清空队列、获取当前队列内数据数量等函数。 描述详见https://blog.csdn.net/ylc0919/article/details/121418999
华清远见嵌入式linux应用程序开发技术详解(内部资料) 第1章 Linux快速入门 1.1 嵌入式Linux基础 1.2 Linux安装 1.3 Linux文件及文件系统 1.4 实验内容——安装Linux操作系统 本章小结 ...
一:嵌入式c语言 C语言是嵌入式领域重要也是主要的编程语言,通过大量编程实例重点理解C语言的基础编程以及编程知识。包括:基本数据类型、数组、指针、结构体、链表、文件操作、队列、栈等。 二:Linux基础 ...
接着系统地讲解了嵌入式Linux的环境搭建,以及嵌入式Linux的I/O与文件系统的开发、进程控制开发、进程间通信开发、网络应用开发、基于中断的开发、设备驱动程序的开发以及嵌入式图形界面的开发等,并且还安排了丰富...
本篇资源分享一个很实用的嵌入式代码库。...它可灵活应用到有无RTOS的程序中,采用C语言面向对象的思路实现各个功能,尽可能最大化的复用代码,目前为止工具包包含:循环队列、软件定时器、事件集。