(2)数据结构复习之栈和队列

àì夳堔傛蜴生んèń 2022-10-22 02:52 138阅读 0赞

## 2.1栈 ##

#### 2.1.1栈的基本概念 ####

> 只允许在**一端**进行插入和删除操作的**线性表**

*  栈顶：允许进行插入和删除的那一端
 *  栈底：不允许插入和删除的一端
 *  空栈：不含任何元素  
    n个不同元素进栈，出栈可能的结果为（2n)!/n!*(2n-n)!*(n+1)，此公式称为卡特兰数

#### 2.1.2栈的顺序存储结构 ####

栈是一种操作受限的线性表，类似于线性表，它有两种对应的存储方式。

##### 1.顺序栈的实现 #####

采用顺序存储的栈成为顺序栈

typedef int ElemType;
    
    typedef struct{ // 栈 
    	ElemType data[MAXSIZE];
    	int top;
    }Stack;

通常将初始的栈顶指针设为-1

*  栈空：S.top=-1;
 *  栈满 S.top=MAXSIZE-1
 *  栈长：S.top+1

##### 2.栈的基本实现 #####

1.初始化  
将栈顶指针置为-1

void InitSatck(Stack *stack){ //初始化栈，将栈顶指针置为-1 
    	stack->top=-1;
    }

2.判断空  
top指针为-1则代表是空的

int isEmpty(Stack *stack){ 
    	if(stack->top==-1)
    		return -1;//空
    	return 0;	//非空
    }

3.进栈

int push(Stack *stack,int e){ 
    	if(stack->top>=MAXSIZE-1)//若栈已满 
    		return 0;
    	stack->data[++(stack->top)]=e;
    	return 1;	
    }

4.出栈

int pop(Stack *stack){ 
    	if(stack->top==-1)//若栈为空 
    		return 0;
    	return stack->data[stack->top--];	
    }

**完整代码**

#include<stdio.h>
    #include<malloc.h>
    #define MAXSIZE 50
    
    typedef int ElemType;
    
    typedef struct{ // 栈 
    	ElemType data[MAXSIZE];
    	int top;
    }Stack;
    
    void InitSatck(Stack *stack){ //初始化栈，将栈顶指针置为-1 
    	stack->top=-1;
    }
    
    int isEmpty(Stack *stack){ 
    	if(stack->top==-1)
    		return -1;
    	return 0;	
    }
    
    int push(Stack *stack,int e){ 
    	if(stack->top>=MAXSIZE-1)//若栈已满 
    		return 0;
    	stack->data[++(stack->top)]=e;
    	return 1;	
    }
    
    int pop(Stack *stack){ 
    	if(stack->top==-1)//若栈为空 
    		return 0;
    	return stack->data[stack->top--];	
    }
    
    int main(){ 
    	Stack stack;
    	InitSatck(&stack);
    	return 0;
    }

##### 3.共享栈 #####

利用栈底位置相对不变的特点，可以让两个顺序栈共享一个一维数组，将两个栈的栈底分别设置在共享空间的两端，然后向中间延伸

*  top0=-1时，1号栈为空
 *  top1=MAXSIZE时，2号栈为空
 *  当两栈顶指针相邻时，即top0-top1=1，栈满

#### 2.1.3栈的链式存储结构 ####

采用链式存储的栈成为链栈，链栈的优点是便于多个栈共享存储空间，提高效率，且不存在栈满的情况

## 2.2队列 ##

#### 2.2.1队列的基本概念 ####

也是一种操作受限的线性表，只允许在一端插入，在另一端删除。  
从队尾进入，称为入队  
从队头出，称为出队

#### 2.2.2队列的顺序存储结构 ####

##### 1.队列的顺序存储 #####

队列的顺序实现是指分配一块连续的存储空间存放队列中的元素，并设队头front和队尾rear指针

队列的存储类型可描述为：

typedef int ElemType;
    
    typedef struct{ 
    	ElemType data[MAXSIZE];
    	int front,rear;
    }Queue;

缺点：可能出现上溢出的情况，但并不是真正的溢出，若栈满时，进行多次出栈操作，直到剩下一个元素，此时队头和队尾指向同一个节点，然而队尾指针为MAXSIZE-1，但是其他地方确是空的，没有存储数据

##### 2.循环队列 #####

将顺序队列臆造为一个环状的空间，逻辑上成为了一个环，当队头指针为MAXSIZE-1时，再向前移动一个单位，就自动到0。

有三种方法区分队满还是队空：

1.  牺牲一个单元，约定队尾指针的下一个位置为队头指针

> 满队条件:（Q.rear+1)%MAXSIZE== Q.front  
> 队空条件: Q.front== Q.rear  
> 队列中元素个数：(Q.rear-Q.front+MAXSIZE)%MAXSIZE

1.  类型中增设表示元素个数的数据成员

> 队空条件为:Q.size==0  
> 队满条件为:Q.size=MAXSIZE

1.  增设tag数据成员，区分队满还是队空。tag为0时，因删除导致Q.front== Q.rear，则为队空；tag为1 ，若因插入导致Q.front==Q.rear，则为队满

##### 3.循环队列的操作 #####

（1）初始化  
将队列头尾指针置为0

void initQueue(Queue *queue){ //初始化 
    	queue->rear=queue->front=0;
    }

（2）判断空  
队空条件为队列头尾指针相等

int isEmpty(Queue *queue){ //判断是否为空 
    	if(queue->rear==queue->front)
    		return 1;//已满
    	return 0;//未满 
    }

（3）入队

int enQueue(Queue *queue,int e){ //入队 
    	if((queue->rear+1)%MAXSIZE==queue->front)
    		return 0;//队列已满
    	queue->data[queue->rear]=e;
    	queue->rear=(queue->rear+1)%MAXSIZE;
    	return 1;	 
    }

（4）出队

int deQueue(Queue *queue){ //出队 
    	if(queue->front==queue->rear)
    		return 0;//队列已空
    	queue->front=(queue->front+1)%MAXSIZE;
    	return 1;	 
    }

**完整代码**

#include<stdio.h>
    #define MAXSIZE 50
    
    typedef int ElemType;
    
    typedef struct{ 
    	ElemType data[MAXSIZE];
    	int front,rear;
    }Queue;
    
    void initQueue(Queue *queue){ //初始化 
    	queue->rear=queue->front=0;
    }
    
    int isEmpty(Queue *queue){ //判断是否为空 
    	if(queue->rear==queue->front)
    		return 1;//已满
    	return 0;//未满 
    } 
    
    int enQueue(Queue *queue,int e){ //入队 
    	if((queue->rear+1)%MAXSIZE==queue->front)
    		return 0;//队列已满
    	queue->data[queue->rear]=e;
    	queue->rear=(queue->rear+1)%MAXSIZE;
    	return 1;	 
    } 
    
    int deQueue(Queue *queue){ //出队 
    	if(queue->front==queue->rear)
    		return 0;//队列已空
    	queue->front=(queue->front+1)%MAXSIZE;
    	return 1;	 
    }
    
    
    
    int main(){ 
    	Queue queue;
    	initQueue(&queue);
    	int i=0;
    	for(;i<10;i++)
    		enQueue(&queue,i);
    		
    	while(!isEmpty(&queue)){ 
    		printf("%d ",queue.data[queue.front]);
    		deQueue(&queue);
    	}	
    	return 0;
    }

#### 2.2.3队列的链式存储结构 ####

1.队列的链式存储  
队列的链式表示称为链队列，实际上就是一个同时带有队头指针和队尾指针的单链表，头指针指向队头节点，尾指针指向队尾节点。

其链式存储类型可描述为：

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

当Q.front== NULL且Q.rear== NULL时，链式队列为空

> 单链表特别适合数据元素变动比较大的情形，且不存在队列满而溢出的问题

2.链式队列的基本操作  
（1）初始化

void initQueue(LinkQueue *Q){ 
    	Q->front=Q->rear=(LinkNode*)malloc(sizeof(LinkNode));
    	Q->front->next=NULL;
    }

（2）判断空

int isEmpty(LinkQueue *Q){ 
    	if(Q->front==Q->rear)
    		return 1;//为空 
    	return 0;	
    }

（3）入队

void enQueue(LinkQueue *Q,int e){ 
    	LinkNode *p=(LinkNode*)malloc(sizeof(LinkNode));
    	p->data=e;
    	p->next=NULL;
    	Q->rear->next=p;
    	Q->rear=p;
    }

（4）出队

int deQueue(LinkQueue *Q){ 
    	if(isEmpty)
    		return 0;//队列为空
    	
    	LinkNode *p=Q->front->next;	
    	Q->rear->next=p->next;
    	if(Q->rear==p)
    		Q->front=Q->rear;//如果队列只剩下一个节点，删除之后，队列为空 
    	free(p); 
    	return 1;
    }

#### 2.2.4双端队列 ####

允许两端都可以进行入队和出队操作的队列

## 2.3栈和队列的应用 ##

#### 2.3.1栈在括号匹配中的应用 ####

#### 2.3.2栈在表达式求值中的应用 ####

#### 2.3.3栈在递归中的应用 ####

#### 2.3.4栈在层次遍历中的应用 ####

#### 2.3.5队列在计算机中的应用 ####