c语言--栈和队列_栈和队列c语言

一、栈

1、栈的概念

1. 栈（stack）是一种只允许在一端进行插入和删除操作的线性表。它是一种操作受限的线性表。在表中允许进行插入和删除的一端称为“栈顶”（top），另一端称为“栈底”（bottom）。
2. 栈的插入操作通常称为“入栈”或“进栈”（push），而栈的删除操作则称为“出栈”或“退栈”（pop）。当栈中无数据元素时称为“空栈”。
3. 栈具有“后进先出”的特性。

栈的入栈和出栈操作

通常用指针top指向栈顶的位置，用指针bottom指向栈底，栈顶指针top动态反映栈的当前位置。

2、栈的实现

栈是一种特殊的线性表，因此栈可采用顺序存储结构存储，也可以使用链式存储结构存储。

<1>顺序栈

栈中的数据元素用一个预设的足够长的一维数组来实现：ElemType elem[MAXSIZE]。栈底位置可以设置在数组的任意端点，用int top来作为栈顶指针。

#define MAXSIZE<栈最大元素数>
typedef int ElemType;   //ElemType的类型根据实际情况而定，这里假定为int
typedef struct {
ElemType elem[MAXSIZE];
int top; //栈顶指针
} SeqStack
1
2
3
4
5
6

SeqStack* s; //定义一个指向顺序栈的指针
1

---

若现在有一个栈，StackSize是5，则栈的普通情况、空栈、满栈的情况分别如下图所示：

通常将0下标端设为栈底，这样空栈时栈顶指针s->top = -1；入栈时，栈顶指针s->top++；出栈时，s->top- -。

---

顺序栈的基本操作 ❤️

（1）初始化

void InitStack(SqStack *S){
    S->top = -1;    //初始化栈顶指针
}
1
2
3

（2）判栈空

int Empty(SqStack* s){
    if（s.top == -1){    
        return 1;    //栈空
    }else{  
        return 0;   //不空
    }
}
1
2
3
4
5
6
7

（3）进栈

/*插入元素e为新的栈顶元素*/
int Push(SqStack *s, ElemType x){
    //栈满不能入栈
    if(S->top == MAXSIZE-1){
        return 0;
    }
    S->top++;   //栈顶指针增加一
    S->elem[S->top] = x;    //将新插入元素赋值给栈顶空间
    return 1;
}
1
2
3
4
5
6
7
8
9
10

（4）出栈

int Pop(SeqStack* s,ElemType *x) {
	if(Empty(s)) {
		return 0; //栈空不能出栈
		}
	 *x = s->elem[s->top];   //将要删除的栈顶元素赋值给x
    s->top--;   //栈顶指针减一
    return 1;
1
2
3
4
5
6
7

（5）取栈顶元素

ElemType GetTop(SeqStack* s) {
	if(Empty(s) {
		return 0; //栈空
		} else {
			return (s->elem[s->top]);			
1
2
3
4
5

<2>链栈

在一个链栈中方，栈底就是链表的最后一个结点，而栈顶总是链表的第一个结点。因此新入栈的元素即为链表的第一个新的结点。

采用带头结点的单链表实现栈（也可以用不带头结点的）。因为栈的插入和删除仅限在表头进行操作，所以链表的头指针top就作为栈顶指针，top始终指向当前栈顶元素前的头结点，即top->next为栈顶元素。

typedef stuck Stacknode {
	DataType data;
	struct Stacknode* next;
	} slStacktype;
1
2
3
4

链栈的基本操作 ❤️

（1）入栈

//将元素x压入链栈top中
int PushLstack(slStacktype* top,DataType x) {
	slStacktype* p;
	//申请一个结点
	if（p = (slStacktype* )malloc(sizeof(slStacktype))== NULL）
	return false;
	p->data = x;
	p->next = top->next;
	top->next = p;
	return ture;
	}
1
2
3
4
5
6
7
8
9
10
11

（2）出栈

//从链栈top中删除栈顶元素
DataType PopLstack(slStacktype* top) {
	slStacktype* p;
	DataType x;
	if(top->next == NULL)//空栈 {
		printf("此栈为空！");
		return;
		}
	p = top->next;
	top->next = p->next;
	x = p->data;
	free(p);
	return x;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

<3>共享栈

利用栈底位置相对不变的特征，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，如下图所示：

两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=MaxSize时1号栈为空；仅当两个栈顶指针相邻（top0+1=top1）时，判断为栈满。当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减一再赋值出栈时则刚好相反。

/*两栈共享空间结构*/
#define MAXSIZE 50  //定义栈中元素的最大个数
typedef int ElemType;   //ElemType的类型根据实际情况而定，这里假定为int
/*两栈共享空间结构*/
typedef struct{
	ElemType data[MAXSIZE];
	int top0;	//栈0栈顶指针
	int top1;	//栈1栈顶指针
}SqDoubleStack;
1
2
3
4
5
6
7
8
9

共享栈的基本操作

（1）进栈

对于两栈共享空间的push方法，我们除了要插入元素值参数外，还需要有一个判断是栈0还是栈1的栈号参数stackNumber。
共享栈进栈的代码如下：

/*插入元素e为新的栈顶元素*/
Status Push(SqDoubleStack *S, Elemtype e, int stackNumber){
    if(S->top0+1 == S->top1){   //栈满
        return ERROR;
    }
    if(stackNumber == 0){   //栈0有元素进栈
        S->data[++S->top0] = e; //若栈0则先top0+1后给数组元素赋值
    }else if(satckNumber == 1){ //栈1有元素进栈
        S->data[--S->top1] = e; //若栈1则先top1-1后给数组元素赋值
    }
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12

（2）出栈

/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
Status Pop(SqDoubleStack *S, ElemType *e, int stackNumber){
    if(stackNumber == 0){
        if(S->top0 == -1){
            return ERROR;   //说明栈0已经是空栈，溢出
        }
        *e = S->data[S->top0--]; //将栈0的栈顶元素出栈，随后栈顶指针减1
    }else if(stackNumber == 1){
        if(S->top1 == MAXSIZE){
            return ERROR;   //说明栈1是空栈，溢出
        }
        *e = S->data[S->top1++];    //将栈1的栈顶元素出栈，随后栈顶指针加1
    }
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二、 队列

1、队列的概念

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列是一种先进先出的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。

存取顺序:

队头：出队列进行删除操作的一端称为队头。
队尾：进行插入操作的一端称为队尾。

2、队列的实现

<1>顺序队列

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针 front指向队头元素，队尾指针 rear 指向队尾元素的下一个位置。

1、顺序队列
队列的顺序存储类型可描述为:

#define MAXSIZE 50	//定义队列中元素的最大个数
typedef struct{
	ElemType data[MAXSIZE];	//存放队列元素
	int front,rear;
}SqQueue;
1
2
3
4
5

初始状态（队空条件）：Q->front == Q->rear == 0。
进队操作：队不满时，先送值到队尾元素，再将队尾指针加1。
出队操作：队不空时，先取队头元素值，再将队头指针加1。

如图d，队列出现“上溢出”，然而却又不是真正的溢出，所以是一种“假溢出”。

---

2、循环队列
解决假溢出的方法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

当队首指针Q->front = MAXSIZE-1后，再前进一个位置就自动到0，这可以利用除法取余运算（%）来实现。

初始时：Q->front = Q->rear=0。
队首指针进1：Q->front = (Q->front + 1) % MAXSIZE。
队尾指针进1：Q->rear = (Q->rear + 1) % MAXSIZE。
队列长度：(Q->rear - Q->front + MAXSIZE) % MAXSIZE。

出队入队时，指针都按照顺时针方向前进1，如下图所示：

那么，循环队列队空和队满的判断条件是什么呢？

显然，队空的条件是 Q->front == Q->rear 。若入队元素的速度快于出队元素的速度，则队尾指针很快就会赶上队首指针，如图( d1 ）所示，此时可以看出队满时也有 Q ->front ==Q -> rear 。
为了区分队空还是队满的情况，有三种处理方式：

（1）牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是种较为普遍的做法，约定以“队头指针在队尾指针的下一位置作为队满的标志”，如图 ( d2 ）所示。

队满条件： (Q->rear + 1)%Maxsize== Q->front
队空条件仍： Q->front == Q->rear
队列中元素的个数： (Q->rear - Q ->front + Maxsize)% Maxsize

（2）类型中增设表示元素个数的数据成员。这样，队空的条件为 Q->size == O ；队满的条件为 Q->size==Maxsize 。这两种情况都有 Q->front==Q->rear

（3）类型中增设tag 数据成员，以区分是队满还是队空。tag 等于0时，若因删除导致 Q->front == Q->rear ，则为队空；tag 等于 1 时，若因插入导致 Q ->front == Q->rear ，则为队满。

重点看第一种

循环队列的基本操作

（1）循环队列的顺序存储结构

typedef int ElemType;   //ElemType的类型根据实际情况而定，这里假定为int
#define MAXSIZE 50  //定义元素的最大个数
/*循环队列的顺序存储结构*/
typedef struct{
    ElemType data[MAXSIZE];
    int front;  //头指针
    int rear;   //尾指针,若队列不空，指向队列尾元素的下一个位置
}SqQueue;
1
2
3
4
5
6
7
8

（2）循环队列的初始化

/*初始化一个空队列Q*/
Status InitQueue(SqQueue *Q){
    Q->front = 0;
    Q->rear = 0;
    return OK;
}
1
2
3
4
5
6

（3）循环队列判队空

/*判队空*/
bool isEmpty(SqQueue Q){
    if(Q.rear == Q.front){
        return true;
    }else{
        return false;
    }
}
1
2
3
4
5
6
7
8

（4）求循环队列长度

/*返回Q的元素个数，也就是队列的当前长度*/
int QueueLength(SqQueue Q){
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}
1
2
3
4

（5）循环队列入队

/*若队列未满，则插入元素e为Q新的队尾元素*/
Status EnQueue(SqQueue *Q, ElemType e){
    if((Q->real + 1) % MAXSIZE == Q->front){
        return ERROR;   //队满
    }
    Q->data[Q->rear] = e;   //将元素e赋值给队尾
    Q->rear = (Q->rear + 1) % MAXSIZE;  //rear指针向后移一位置，若到最后则转到数组头部
    return OK;
}
1
2
3
4
5
6
7
8
9

（6）循环队列出队

/*若队列不空，则删除Q中队头元素，用e返回其值*/
Status DeQueue(SqQueue *Q, ElemType *e){
    if(isEmpty(Q)){
        return REEOR;   //队列空的判断
    }
    *e = Q->data[Q->front]; //将队头元素赋值给e
    Q->front = (Q->front + 1) % MAXSIZE;    //front指针向后移一位置，若到最后则转到数组头部
}
1
2
3
4
5
6
7
8

<2>、链队列

队列的链式存储结构表示为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表，只不过它只能尾进头出而已。

空队列时，front和real都指向头结点。

---

链队列的基本操作

（1）链队列存储类型

/*链式队列结点*/
typedef struct {
	ElemType data;
	struct LinkNode *next;
}LinkNode;
/*链式队列*/
typedef struct{
	LinkNode *front, *rear;	//队列的队头和队尾指针
}LinkQueue;
1
2
3
4
5
6
7
8
9

当Q->front == NULL 并且 Q->rear == NULL 时，链队列为空。
（2）链队列初始化

void InitQueue(LinkQueue *Q){
	Q->front = Q->rear = (LinkNode)malloc(sizeof(LinkNode));	//建立头结点
	Q->front->next = NULL;	//初始为空
}
1
2
3
4

（3）链队列入队

Status EnQueue(LinkQueue *Q, ElemType e){
	LinkNode s = (LinkNode)malloc(sizeof(LinkNode));
	s->data = e;
	s->next = NULL;
	Q->rear->next = s;	//把拥有元素e新结点s赋值给原队尾结点的后继
	Q->rear = s;	//把当前的s设置为新的队尾结点
	return OK;
}
1
2
3
4
5
6
7
8

（4）链队列出队
出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点。

/*若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR*/
Status DeQueue(LinkQueue *Q, Elemtype *e){
	LinkNode p;
	if(Q->front == Q->rear){
		return ERROR;
	}
	p = Q->front->next;	//将欲删除的队头结点暂存给p
	*e = p->data;	//将欲删除的队头结点的值赋值给e
	Q->front->next = p->next;	//将原队头结点的后继赋值给头结点后继
	//若删除的队头是队尾，则删除后将rear指向头结点
	if(Q->rear == p){	
		Q->rear = Q->front;
	}
	free(p);
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

<3>双端队列

1、定义

双端队列是指允许两端都可以进行入队和出队操作的队列，如下图所示。其元素的逻辑结构仍是线性结构。将队列的两端分别称为前端和后端，两端都可以入队和出队。

在双端队列进队时，前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面。在双端队列出队时，无论是前端还是后端出队，先出的元素排列在后出的元素的前面。
参考文章：数据结构：栈和队列