C语言栈与队列如何定义
今天小编给大家分享一下C语言栈与队列如何定义的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。
栈
栈的定义
栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作
假设栈 【s = (a1,a2,……,an) 】，a1为栈底元素，an为栈顶元素。由于栈只能在栈顶进行插入和删除操作，所以进栈次序依次为【a1,a2,……,an】，出栈次序为【an,……,a2,a1】
由此可见：栈的操作特性可以明显地概括为后进先出
栈类似于线性表，它也有两种对应的存储方式分别为顺序栈和链栈。
顺序栈
顺序栈的定义
Q：什么是顺序栈？
A：采用顺序存储的栈成为顺序栈。它利用一组地址连续的存储单位存放自栈底到栈顶的数据元素，同时附设一个指针（top）来指示当前栈顶的位置。
栈的顺序存储类型可描述为
#define MaxSize 100 //定义栈中元素的最大个数
typedef struct
{
SElemtype *base; //栈底指针
SElemtype *top; //栈顶指针
int stacksize //栈可用的最大容量
}SqStack;顺序栈的初始化
Q：什么是顺序栈的初始化？
A：顺序栈的初始化操作就是为顺序栈动态分配一个最大容量为 MaxSize 的数组空间。
实现原理
为顺序栈动态分配一个最大容量为MAXSIZE的数组
栈顶指针top初始为base，表示栈为空
stacksize置为栈的最大容量MaxSize
代码演示
Status InitStack(SqStack &S)
{//构造一个空栈S
S. base=new SElemType[MaxSize]; //为顺序栈动态分配一个最大容量为MAxsini
if(!S. base) exit(OVERFLOW); //存储分配失败
S. top=S. base; //top初始为base，空栈
S. stacksize=MaxSize; //stacksize置为栈的最大容量MaxSize
return OK;
}顺序栈的入栈
Q：什么是顺序栈的入栈？
A：入栈操作是将新元素进入栈
实现原理
判断栈是否满了，若满了返回ERROR
将新元素压入栈，栈顶指针加1
代码演示
Status Push(SqStack &S,SElemType e)
{//插入元素e为新的栈顶元素
if(S.top-S.base==S:stacksize) return ERROR;//栈满
*S. top++=e; //元素e压入栈顶，栈顶指针加1
return OK;
}顺序栈的出栈
Q：什么是顺序栈的出栈？
A：出栈操作是将栈顶元素删除
实现原理
判断栈是否空，若空则返回ERROR
栈顶指针减1，栈顶元素出栈
代码演示
Status Pop(SqStack &S,SElemType &e) (//删除S的栈顶元素，用e返回其值 if(S.top==S.base) return ERROR;//栈顶 指针减1，将栈顶元素赋给e //栈顶指针减1，将栈顶元素赋给e e=*--S.top; return OK; )
取顺序栈的栈顶元素
Q：如何取顺序栈的栈顶元素？
A：当栈非空时，此操作返回当前栈顶元素的值，栈顶指针保持不变。
实现原理
判断栈是否空
返回栈顶元素的值，栈顶指针不变
代码演示
SElemType GetTop (SqStack S)
{//返回s的栈顶元素，不修改栈顶指针
if(S.top!=S.base) //栈非空
return*(S.top-1); //返回栈顶元素的值，栈顶指针不变
)链栈
采用链式存储的栈称为链栈。链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现。
栈的顺序存储类型可描述为
typedef struct Linknode
{
ElemType data; //数据域
struct Linknode *next; //指针域
} *LiStack;采用链式存储，便于结点的插入与删除。链栈的操作与链表类似，入栈和出栈的操作都在链表的表头进行。
队列
队列的定义
队列是一种线性表，但限定这种线性表只能在表的一端进行插入，在另一端进行删除。允许删除的一端为队头，又称为队首，允许插入的一端为队尾
队列与生活中的排队一样，最早排队的最先离开，队列的操作特性可以明显地概括为先进先出
队列有两种存储表示，分别为顺序表示与链式表示
队列的顺序表达与实现
队列顺序存储结构
和顺序栈相类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次列头到队列尾的元素之外。还需附设两个整型变量【front】和【rear】分别指示队列头元素及队间的位置（后面分别称为头指针和尾指针）。
队列的顺序存储结构表示如下：
#define MAXSIZE 100 //队列容量
typedef struct
{
ElemType *base; //存储空间
int front,rear; //队首，队尾
}SqQueue ;假溢出
图（1）所示为队列的初始状况。此时有【front == rear == 0】 成立。该条件可以作为队列判空的条件。
但是【rear == MAXSIZE】不能作为队列满的条件。为什么呢？
图（4）队列中只有一个元素，仍满足该条件。这时入队出现上溢出。但是这种溢出并不是真正的溢出，在队列中依然存在可以存放元素的空位置，所以是一种假溢出。
如何解决循环链表的这一缺点呢？
循环队列
Q：什么是循环队列？
A：将顺序队列臆造成一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。
循环队列的初始化
Q：什么是循环队列的初始化？
A：循环队列的初始化就是动态分配一个预定义大小为 MAXSIZE 的数组空间
????实现原理
为队列动态分配一个最大容量为MAXSIZE的数组空间
base指向数组空间的首地址
头指针与尾指针置为零，表示队列为空
???? 代码演示
Status InitQueue ( SqQueue &Q )
{
Q.base=new ElemType[MAXSIZE];
if(!Q.base) return OVERFLOW;
Q.front=Q.rear=0;
return OK;
}循环队列的入队
Q：什么是循环队列的入队？
A：入队操作是指在队尾插入一个新的元素
????实现原理
判断队列是否满
满了返回ERROR
将新元素插入队尾
队尾指针加一
???? 代码演示
Status EnQueue(SqQueue &Q,ElemType e)
{
if((Q.rear+1)%MAXSIZE==Q.front) //判满
return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXSIZE;
return OK;
}循环队列的出队
Q：什么是循环队列的出队？
A：出队操作是删除队头元素
????实现原理
判断队列是否为空
为空返回ERROR
保留队头元素
队头指针加一
???? 代码演示
Status DeQueue(SqQueue &Q, ElemType &e)
{
if( Q.rear==Q.front )
return ERROR; //判空
e = Q.base[Q.front];
Q.front = (Q.front+1)%MAXSIZE;
return OK;
}链队列
Q：什么是链队列？
A：队列的链式表示称为链队列。它实际上是一个同时带有队头指针和队尾指针的单链表，头指针指向对头结点，尾指针指向队尾结点。
队列的链式存储如图：
队列的链式存储类型可描述为：
typedef struct Qnode
{
ElemType data;
struct QNode * next;
}Qnode,*QueuePtr; //结点
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue; //链队链栈的初始化
Q：什么是链队列的初始化？
A：链栈的初始化操作就是构建一个只有头结点的空队。
实现原理
生成新结点作为头结点
队头指针和队尾指针指向该结点
头指针的指针域置空
代码演示
Status InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=new QNode;
p->next=NULL;
return OK;
}链栈的入队
实现原理
为入队元素分配结点空间，用指针p指向
将新结点数据域置为e
将新结点插入到队尾
修改队尾指针为p
???? 代码演示
Status EnQueue(LinkQueue &Q,ElemType e)
{
p=new QNode; //为入队元素分配结点空间，用指针p指向
p->data=e; //将新结点数据域置为e
p->next=NULL;
Q.rear->next=p; //将新结点插入到队尾
Q.rear=p; //修改队尾指针为p
return OK;
}链栈的出队
实现原理
判断是否为空，为空返回ERROR
保留头元素空间，以备释放
修改头指针的指针域，指向下一结点
判断出队元素是否是最后一个元素，若是，将队尾指针重新赋值，指向头结点
释放原队头元素的空间
代码演示
Status DeQueue(LinkQueue &Q,ElemType &e)
{
if(Q.front==Q.rear) //若队列为空，返回ERROR
return ERROR;
QNode *p=Q.front->next; //保留头元素空间，以备释放
Q.front->next=p->next; //修改头指针的指针域，指向下一结点
if(Q.rear==p) //判断出队元素是否是最后一个元素，若是，将队尾指针重新赋值，指向头结点
Q.rear=Q.front;
delete p; //释放原队头元素的空间
return OK;
}以上就是“C语言栈与队列如何定义”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注蜗牛博客行业资讯频道。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：niceseo99@gmail.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
评论