数据结构-第二章-栈与队列

2023-12-06 11:48:52

栈

基本概念

栈是只允许在一端进行插入或删除操作的线性表。

重要术语：

栈顶、栈底、空栈、后进先出(LIFO)

顺序栈

#define MAXSIZE 20 //定义栈元素个数最大值
typedef struct {
	int data[MAXSIZE];
	int top; //栈顶指针
} SqStack;

顺序栈基本操作

//初始化栈
void initStack(SqStack *s) {
	s->top = -1;
}

//判断栈是否为空
bool isStackEmpty(SqStack *s) {
	if (s->top == -1) {
		return true; //栈空
	}
	return false;
}

//进栈
bool push(SqStack *s, int e) {
	if (s->top == MAXSIZE - 1) {
		return false; //栈满则插入失败
	}
	s->top++;
	s->data[s->top] = e;
	printf("%d进栈成功\n", s->data[s->top]);
	return true;
}

//出栈
bool pop(SqStack *s, int *e) {
	if (s->top == -1) {
		return false;
	}
	*e = s->data[s->top];
	s->top--;
	printf("%d出栈成功\n", *e);
	return true;
}

//栈置空
void emptyStack(SqStack *s) {
	s->top = -1;
}

//栈的销毁
void destroyStack(SqStack *s) {
	free(s);
}

int main() {
	SqStack s;
	initStack(&s);
	isStackEmpty(&s);
	int a = 10;
	int b = 13;
	int c = 15;
	int d;
	push(&s, a);
	push(&s, b);
	push(&s, c);
	pop(&s, &d);
	emptyStack(&s);
	destroyStack(&s);
	return 0;
}

链式栈

typedef struct Linknode {
	int data;//数据域
	struct Linknode *next;//指针域
}*LiStack;

共享栈

两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=MaxSize时1号栈为空。

仅当两个栈顶指针相邻（top1-top0=1）时，判断为栈满。

当0号栈进栈时top0先加1再赋值，1号栈进栈时topl先减1再赋值；出栈时则刚好相反。

共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。

其存取数据的时间复杂度均为O（1），所以对存取效率没有什么影响。

卡特兰式

n 个元素进栈序列为：1，2，3，4，…，n，则有多少种出栈序列。

队列

基本概念

队列（Queue）：队列简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队；删除元素称为出队或离队。

其操作的特性是先进先出（First In First Out，FIFO），故又称为先进先出的线性表。

队头（Front）：允许删除的一端，又称为队首。

队尾（Rear）：允许插入的一端。

空队列：不含任何元素的空表。

队列的顺序存储（假溢出）

结构类型

#define MaxSize 50
typedef struct {
	int data[MaxSize];
	int front;//队头
	int rear;//队尾
} SqQueue;

初始状态（队空条件）：Q.frontQ.rear0。

进队操作：队不满时，先送值到队尾元素，再将队尾指针加1。

出队操作：队不空时，先取队头元素值，再将队头指针加1。

如图a所示为队列的初始状态，有Q.frontQ.rear=0成立，该条件可以作为队列判空的条件。但不能用Q.rearMaxSize作为队列满的条件。图d中队列中仅有1个元素，但仍满足该条件。这时入队出现“上溢出”，但这种溢出并不是真正的溢出，在data数组中依然存在可以存放元素的空位置，所以是一种**“假溢出”**。

循环队列

结构类型

为解决队列的假溢出现象，可以使用除法取余运算，将线性数组逻辑上变成环型的循环队列。

初始时：Q.front=Q.rear=0

队首指针进1：Q.front=(Q.front+1)%MaxSize

队尾指针进1：Q.rear=(Q.rear+1)%MaxSize

队列长度：(Q.rear+MaxSize-Q.front)%MaxSize

为解决当队空和队满的状态都是Q.front=Q.rear条件，有以下三种方式：

1、牺牲一个单元。（用的比较多）队满情况：(Q.rear+1)%MaxSize=Q.front

2、在结构类型中增加一个计数的Q.size，Q.size=0时为空，Q.size=MaxSize时为满。

3、在结构类型中增加一个标志位tag，以区分是队满还是队空。tag等于0的情况下，若因删除导致Q.front=Q.rear则为队空；tag等于1的情况下，若因插入导致Q.front=Q.rear则为队满。

常见操作

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 50
typedef struct {
	int data[MaxSize];
	int front;
	int rear;
} SqQueue;

//初始化队列
void initQueue(SqQueue *s) {
	s->front = s->rear = 0;
}

//判断队列是否为空
bool isQueueEmpty(SqQueue *s) {
	if ((s->rear + MaxSize - s->front) % MaxSize == 0) {
		printf("队列空！！！\n");
		return true;
	}
	printf("队列不空！！！\n");
	return false;
}

//入队
bool enQueue(SqQueue *s, int e) {
	if ((s->rear + 1) % MaxSize == s->front) {
		return false; //队满则入队失败
	}
	s->data[s->rear] = e;
	s->rear = (s->rear + 1) % MaxSize;
	printf("%d入队成功\n", e);
	return true;
}

//出队
bool deQueue(SqQueue *s, int *e) {
	if (s->rear == s->front) {
		return false; //队空则出队失败
	}
	*e = s->data[s->front];
	s->front = (s->front + 1) % MaxSize;
	printf("%d出队成功\n", *e);
	return true;
}

//队列置空
void emptyQueue(SqQueue *s) {
	s->front = s->rear = 0;
}

//队列销毁
void destroyQueue(SqQueue *s) {
	free(s->data);
	free(s);
}

int main() {
	SqQueue s;
	initQueue(&s);
	isQueueEmpty(&s);
	int a = 10;
	int b = 13;
	int c = 15;
	int d;
	enQueue(&s, a);
	enQueue(&s, b);
	enQueue(&s, c);
	deQueue(&s, &d);
	deQueue(&s, &d);
	emptyQueue(&s);
	destroyQueue(&s);
	return 0;
}

链式队列

结构类型

typedef struct LinkNode {
	int data;
	LinkNode *next;
} LinkNode;
typedef struct {
	LinkNode *front, *rear;
} LinkQueue;

常见操作

#include <stdio.h>
#include <stdlib.h>

typedef struct LinkNode {
	int data;
	LinkNode *next;
} LinkNode;
typedef struct {
	LinkNode *front, *rear;
} LinkQueue;

//初始化队列
void initQueue(LinkQueue *Q) {
	Q->front = Q->rear = (LinkNode *)malloc(sizeof(LinkNode));
	Q->front->next = NULL;
}

//判断队列是否为空
bool isQueueEmpty(LinkQueue *Q) {
	if (Q->rear == Q->front) {
		printf("队列空！！！\n");
		return true;
	}
	printf("队列不空！！！\n");
	return false;
}

//入队
bool enQueue(LinkQueue *Q, int e) {
	LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
	s->data = e;
	s->next = NULL;
	Q->rear->next = s;
	Q->rear = s;
	printf("%d入队成功\n", e);
	return true;
}

//出队
bool deQueue(LinkQueue *Q, int *e) {
	if (Q->front == Q->rear) {
		return false; //队空则出队失败
	}
	LinkNode *s = Q->front->next;
	*e = s->data;
	Q->front->next = s->next;
	if (s == Q->rear) {
		Q->rear = Q->front; //若原队列就剩一个元素，需要改变rear指针位置
	}
	free(s);
	printf("%d出队成功\n", *e);
	return true;
}

//队列置空
void emptyQueue(LinkQueue *Q) {
	if (Q->front == Q->rear) {
		return;
	}
	LinkNode *p = Q->front->next;
	LinkNode *temp;
	while (p != Q->rear) {
		temp = p;
		p = p->next;
		free(temp);
	}
	free(p);
	Q->rear = Q->front;
}

//队列销毁
void destroyQueue(LinkQueue *Q) {
	free(Q);
}

int main() {
	LinkQueue s;
	initQueue(&s);
	isQueueEmpty(&s);
	int a = 10;
	int b = 13;
	int c = 15;
	int d;
	enQueue(&s, a);
	enQueue(&s, b);
	enQueue(&s, c);
	deQueue(&s, &d);
	emptyQueue(&s);
	destroyQueue(&s);
	return 0;
}

双端队列

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

输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列称为输出受限的双端队列。

输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列称为输入受限的双端队列。

而如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈了。

栈与队列的应用

栈的应用：括号匹配、表达式求值（中缀表达式与前后缀表达式的互转）、递归（汉诺塔和斐波那契额数列）、树的先序中序后序遍历等。

队列的应用：二叉树的层次遍历、计算机系统的等待队列等。

括号匹配

主要是匹配{ },[ ],( )是否成对。

表达式求值

有三种式子：中缀表达式、前缀表达式（波兰式）、后缀表达式（逆波兰式），其中中缀表达式就是对人类友好的正常的式子。前后缀表达式是对机器存储和运算友好的，因此程序编译或解释为机器指令时会涉及到中缀表达式与前后缀表达式的互转。方法是确定好运算优先级后，将运算符号分别移到操作数前或后。

35,15,+,80,70,-,*,20,/                      //后缀表达方式
(((35+15)*(80-70))/20）=25                 //中缀表达方式  
/,*,+,35,15,-,80,70, 20                   //前缀表达方式

递归-汉诺塔

#include <stdio.h>
void HanNuo(int n, char a, char b, char c) {
	if (n == 1) { //这也是递归的终止条件
		printf("将盘子%d从 %c -----> %c\n", n, a, c); //控制台输出每次操作盘子的动向
	} else {
		HanNuo(n - 1, a, c, b);      //将a柱子上的从上到下n-1个盘移到b柱子上
		printf("将盘子%d从 %c -----> %c\n", n, a, c);
		HanNuo(n - 1, b, a, c);      //将b柱子上的n-1个盘子移到c柱子上
	}
}
int main() {
	HanNuo(10,'a','b','c');
	return 0;
}

递归-斐波那契额数列

这个数列从第3项开始，每一项都等于前两项之和。

#include <stdio.h>
int main()
{
    long i, n, t1 = 0, t2 = 1, nextTerm;
    printf("输出几项(n>0): ");
    scanf("%d", &n);
    printf("斐波那契数列: ");
    for (i = 1; i <= n; ++i)
    {
        printf("%d, ", t1);
        nextTerm = t1 + t2;
        t1 = t2;
        t2 = nextTerm;
    }
    return 0;
}

码农公寓

栈

基本概念

顺序栈

顺序栈基本操作

链式栈

共享栈

卡特兰式

队列

基本概念

队列的顺序存储（假溢出）

结构类型

循环队列

结构类型

常见操作

链式队列

结构类型

常见操作

双端队列

栈与队列的应用

括号匹配

表达式求值

递归-汉诺塔

递归-斐波那契额数列

相关文章