【algo&ds】3.栈和队列

1.堆栈

堆栈（Stack）：具有一定操作约束的线性表（只在一端（栈顶，Top）做插入、删除）

• 先进后出特性

1.1堆栈的抽象数据类型描述

类型名称: 堆栈（Stack）
数据对象集：一个有0个或多个元素的有穷线性表。
操作集：长度为MaxSize的堆栈S  Stack，堆栈元素item  ElementType
1、Stack CreateStack( int MaxSize )： 生成空堆栈，其最大长度为MaxSize；
2、int IsFull( Stack S, int MaxSize )：判断堆栈S是否已满；
3、void Push( Stack S, ElementType item )：将元素item压入堆栈；
4、int IsEmpty ( Stack S )：判断堆栈S是否为空；
5、ElementType Pop( Stack S )：删除并返回栈顶元素；

Push 和 Pop 可以穿插交替进行；
按照操作系列
(1)Push(S,A), Push(S,B),Push((S,C),Pop(S),Pop(S),Pop(S)
堆栈输出是？

CBA

(2) 而Push(S,A), Pop(S),Push(S,B),Push((S,C),Pop(S),Pop(S)
堆栈输出是?

ACB

栈分为顺序栈和链式栈。

1.2顺序栈

栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成。

1.顺序栈定义

#define MaxSize <储存数据元素的最大个数>
typedef struct SNode *Stack;
struct SNode {
	ElementType Data[MaxSize];
	int Top;
};

2.入栈

void Push( Stack PtrS, ElementType item ) {
	if ( PtrS->Top == MaxSize-1 ) {
		printf("堆栈满");
		return;
	} else {
		PtrS->Data[++(PtrS->Top)] = item;
		return;
	}
}

3.出栈

ElementType Pop( Stack PtrS ) {
	if ( PtrS->Top == -1 ) {
		printf("堆栈空");
		return ERROR; /* ERROR是ElementType的特殊值，标志错误 */
	} else
		return ( PtrS->Data[(PtrS->Top)--] );
}

1.3链式栈

栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行。

1.链式栈定义

typedef struct SNode *Stack;
struct SNode {
	ElementType Data;
	struct SNode *Next;
} ;

2.堆栈初始化（建立空栈）

Stack CreateStack() {
	/* 构建一个堆栈的头结点，返回指针 */
	Stack S;
	S =(Stack)malloc(sizeof(struct SNode));
	S->Next = NULL;
	return S;
}

3.判断堆栈是否为空

int IsEmpty(Stack S)
{ 
    /*判断堆栈S是否为空，若为空函数返回整数1，否则返回0 */
	return ( S->Next == NULL );
}

这里的S并不是头节点，而是指向头节点

4.入栈

void Push( ElementType item, Stack S) {
	/* 将元素item压入堆栈S */
	struct SNode *TmpCell;
	TmpCell=(struct SNode *)malloc(sizeof(struct SNode));
	TmpCell->Element = item;
	TmpCell->Next = S->Next;
	S->Next = TmpCell;
}

5.出栈

ElementType Pop(Stack S) {
	/* 删除并返回堆栈S的栈顶元素 */
	struct SNode *FirstCell;
	ElementType TopElem;
	if( IsEmpty( S ) ) {
		printf(“堆栈空”);
		return NULL;
	} else {
		FirstCell = S->Next;
		S->Next = FirstCell->Next;
		TopElem = FirstCell ->Element;
		free(FirstCell);
		return TopElem;
	}
}

2.队列

队列(Queue)：具有一定操作约束的线性表

• 插入和删除操作：只能在一端插入，而在另一端删除。
• FIFO:先进先出

2.1队列的抽象数据类型描述

类型名称：队列(Queue)
数据对象集：一个有0个或多个元素的有穷线性表。
操作集：长度为MaxSize的队列Q  Queue，队列元素item  ElementType
1、Queue CreatQueue( int MaxSize )：生成长度为MaxSize的空队列；
2、int IsFullQ( Queue Q, int MaxSize )：判断队列Q是否已满；
3、void AddQ( Queue Q, ElementType item )： 将数据元素item插入队列Q中；
4、int IsEmptyQ( Queue Q )： 判断队列Q是否为空；
5、ElementType DeleteQ( Queue Q )：将队头数据元素从队列中删除并返回。

2.2顺序队列

队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成。

1.顺序队列结构体定义

#define MaxSize <储存数据元素的最大个数>
struct QNode {
	ElementType Data[ MaxSize ];
	int rear;
	int front;
};
typedef struct QNode *Queue;

顺序队列的一个劣势就是，随着数据的入队列和出队列，front和rear指针会一直向右移动，最终可能无法再添加新的元素，但是这个时候数组其实还有很多的空间，为了让队列继续可用，就需要数据搬移。

而为了避免数据搬移，就会把顺序存储结构的队列设计成循环队列。

循环队列的本质就是在入队列的时候，rear指针会回到数组的前面去。

你也可以把它的逻辑图画成这样

队列空：

front==rear

队列满：

(rear+1)%maxsize == front

2.入队列

void AddQ( Queue PtrQ, ElementType item) {
	if ( (PtrQ->rear+1) % MaxSize == PtrQ->front ) {
		printf("队列满");
		return;
	}
    PtrQ->Data[PtrQ->rear] = item;
	PtrQ->rear = (PtrQ->rear+1)% MaxSize;
}

3.出队列

ElementType DeleteQ ( Queue PtrQ ) {
	if ( PtrQ->front == PtrQ->rear ) {
		printf("队列空");
		return ERROR;
	} else {
        ElementType x = PtrQ->Data[PtrQ->front];
        PtrQ->front = (PtrQ->front+1)% MaxSize;
		return x;
	}
}

2.3链式队列

队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行。

1.链式队列结构体定义

struct Node {
	ElementType Data;
	struct Node *Next;
};
struct QNode { /* 链队列结构 */
	struct Node *rear; /* 指向队尾结点 */
	struct Node *front; /* 指向队头结点 */
};
typedef struct QNode *Queue;
Queue PtrQ;

2.出队列

ElementType DeleteQ ( Queue PtrQ ) {
	struct Node *FrontCell;
	ElementType FrontElem;
	if ( PtrQ->front == NULL) {
		printf("队列空");
		return ERROR;
	}
	FrontCell = PtrQ->front;
	if ( PtrQ->front == PtrQ->rear) /* 若队列只有一个元素 */
		PtrQ->front = PtrQ->rear = NULL; /* 删除后队列置为空 */
	else
		PtrQ->front = PtrQ->front->Next;
	FrontElem = FrontCell->Data;
	free( FrontCell ); /* 释放被删除结点空间 */
	return FrontElem;
}

3.入队列

void AddQ( Queue Q, ElementType x)
{
    Node *newnode =(Node*)malloc(sizeof(Node));
    newnode->Data = x;
    newnode->Next = NULL;
 	if ( PtrQ->front == NULL) {
        //空队列
        Q->front = Q ->rear = newnode;
    } else{
        Q->rear->Next = newnode;
        Q->rear = newnode;
    }   
}