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 的数组空间。

实现原理

1. 为顺序栈动态分配一个最大容量为MAXSIZE的数组
2. 栈顶指针top初始为base，表示栈为空
3. 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：入栈操作是将新元素进入栈

实现原理

1. 判断栈是否满了，若满了返回ERROR
2. 将新元素压入栈，栈顶指针加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：出栈操作是将栈顶元素删除

实现原理

1. 判断栈是否空，若空则返回ERROR
2. 栈顶指针减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：当栈非空时，此操作返回当前栈顶元素的值，栈顶指针保持不变。

实现原理

1. 判断栈是否空
2. 返回栈顶元素的值，栈顶指针不变

代码演示

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 的数组空间

实现原理

1. 为队列动态分配一个最大容量为MAXSIZE的数组空间
2. base指向数组空间的首地址
3. 头指针与尾指针置为零，表示队列为空

代码演示

Status InitQueue ( SqQueue  &Q )
{
	Q.base=new  ElemType[MAXSIZE];
	if(!Q.base)	return OVERFLOW;
	Q.front=Q.rear=0;
	return OK;
} 

循环队列的入队

Q：什么是循环队列的入队？

A：入队操作是指在队尾插入一个新的元素

实现原理

1. 判断队列是否满
2. 满了返回ERROR
3. 将新元素插入队尾
4. 队尾指针加一

代码演示

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：出队操作是删除队头元素

实现原理

1. 判断队列是否为空
2. 为空返回ERROR
3. 保留队头元素
4. 队头指针加一

代码演示

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：链栈的初始化操作就是构建一个只有头结点的空队。

实现原理

1. 生成新结点作为头结点
2. 队头指针和队尾指针指向该结点
3. 头指针的指针域置空

代码演示

Status InitQueue(LinkQueue &Q)
{
	Q.front=Q.rear=new QNode;
	p->next=NULL;
	return OK;
} 

链栈的入队

实现原理

1. 为入队元素分配结点空间，用指针p指向
2. 将新结点数据域置为e
3. 将新结点插入到队尾
4. 修改队尾指针为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;
}

链栈的出队

实现原理

1. 判断是否为空，为空返回ERROR
2. 保留头元素空间，以备释放
3. 修改头指针的指针域，指向下一结点
4. 判断出队元素是否是最后一个元素，若是，将队尾指针重新赋值，指向头结点
5. 释放原队头元素的空间

代码演示

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语言示例代码讲解栈与队列的文章就介绍到这了,更多相关C语言栈与队列内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！