首页 > 编程学习 > 数据结构第二部分——栈和队列(C语言版)

数据结构第二部分——栈和队列(C语言版)

发布时间:2022/11/7 21:24:13

数据结构第二部分——栈和队列(C语言版)

1、基本概念

  • 栈:只能在一端进行插入或删除的线性表,这一端称为栈顶,另一端称为栈底。栈的特点是 先进后出(FILO),就像一个车队开进了一个死胡同,最先开进的车只有等后边的车全部出去,它才能出去。

  • 队列:它是一种操作受限的线性表,限制为仅允许在一端插入,另一端删除,插入的一端称为队尾,删除的一端称为队头。他的特点为 先进先出(FIFO)

2、存储结构

  • 顺序栈定义
typedef struct
{
	int data[maxSize];
	int top;
}SqStack;
  • 链栈结点定义
typedef struct LNode
{
	int data;//数据域
	struct LNode *next;//指针域
}LNode;
  • 顺序队列定义
typedef struct
{
	int data[maxSize];
	int front;
	int rear;
}SqQueue;
  • 链队定义
//队结点类型
typedef struct QNode
{
	int data;
	struct QNode *next;
}QNode;
//链队类型
typedef struct
{
	QNode *front;
	QNode *rear;
}LiQueue;

3、顺序栈操作

//初始化栈
void initStack(SqStack &st)
{
	st.top = -1;
}
//判断栈空
int isEmpty(SqStack st)
{
	if(st.top == -1)
		return 1;
	else
		return 0;
}
//进栈
int push(SqStack &st,int x)
{
	if(st.top == maxSize-1)//栈满了,不能进栈
		return 0;
	++(st.top);
	st.data[st.top] = x;
	return 1;
}
//出栈
int pop(SqStack &st,int &x)
{
	if(st.top == -1)//栈空不能出栈
		return 0;
	x = st.data[st.top];
	--(st.top);
	return 1;
}

//实际使用时的简单写法
int stack[maxSize];
int top = -1;
stack[++top] = x;
x = stack[top--];

4、链栈操作

//初始化
void initStack(LNode *&lst)
{
	lst = (LNode*)malloc(sizeof(LNode));//制造一个头结点
	lst->next = NULL;
}
//判断栈空
int isEmpty(LNode *lst)
{
	if(lst -> next == NULL)
		return 1;
	else
		return 0;
}
//进栈
void push(LNode *lst,int x)
{
	LNode *p;
	p = (LNode*)malloc(sizeof(LNode));
	p -> next = NULL;

	p->data=x;
	p->next = lst->next;
	lst->next=p;
}
//出栈
int pop(LNode *lst,int &x)
{
	LNode *p;
	if(lst->next == NULL)
		return 0;
	
	p=lst->next;
	x=p->data;
	lst->next=p->next;
	free(p);
	return 1;
}

5、循环队列

  • 在顺序队中,通常让队尾指针rear指向刚进队的元素位置,让队首指针font指向刚出队的元素位置。因此,元素进队的时候,rear要向后移动;元素出队的时候,front也要向后移动。经过一系列的出队和进队操作以后,两个指针最终会达到数组末端maxSize-1处。虽然队中已经没有元素,但仍然无法让元素进队,这就是所谓的“假溢出”。
  • 要解决这个问题,可以把数组弄成一个环,让rear和front沿着环走,这样就永远不会出现两者来到数组尽头无法继续往下走的情况,这样就产生了循环队列。
    在这里插入图片描述
    一般情况下,front=(front+1)%maxSize,可以看出,循环队列必须损失一个存储空间,如果下图中的空白处也存入元素,则队满的条件也成了 front==rear,和队空条件相同了。
    在这里插入图片描述
//初始化队列
void initQueue(SqQueue &qu)
{
	qu.front = qu.rear = 0;
}
//判断队空
int isQueueEmpty(SqQueue qu)
{
	if(qu.front == qu.rear)
		return 1;
	else
		return 0;
}
//进队
int enQueue(SqQueue &qu,int x)
{
	if((qu.rear+1)%maxSize == qu.front)
		return 0;
	qu.rear = (qu.rear+1)%maxSize;
	qu.data[qu.rear] = x;
	return 1;
}
//出队
int deQueue(SqQueue &qu,int &x)
{
	if(qu.front == qu.rear)
		return 0;
	qu.front = (qu.front+1) % maxSize;
	x = qu.data[qu.front];
	return 1;
}

6、链队

  • 链队就是采用链式存储结构存储队列,链队的特点是不存在队满,除非内存满了。
  • 链队队空状态:lqu->rear == NULL 或者 lqu->front == NULL.
  • 入队操作:lqu->rear->next = p;lqu->rear = p
  • 出队操作:p=lqu->front;lqu->front = p->next;x = p->data;free§
    在这里插入图片描述

7、共享栈和双端队列

  • 共享栈:相比于普通的顺序栈,共享栈主要是为了提高内存的利用率和减少溢出的可能性而设计
  • 双端队列:是一种插入和删除操作在两端均可进行的线性表。
  • 可以把双端队列看成栈底连在一起的两个栈。双端队列与共享栈的不同之处是,两个栈的栈顶指针是向两端延伸的。由于双端队列允许在两端插入和删除元素,因此需设立两个指针:end1和end2,分别指向双端队列中两端的元素。
    在这里插入图片描述
Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式