目录

3.1 栈

3.1.1 栈的基本概念

1. 栈的定义

2. 栈的基本操作

3.1.2 栈的顺序存储结构

1. 栈的定义

2. 初始化一个栈

3.进栈操作

4.出栈操作

5.读取栈顶元素

7.共享栈和一些操作

3.1.3 栈的链式存储结构

1.链栈的初始化

2.链栈的入栈操作

3.链栈的出栈操作

3.2 队列

3.2.1 队列的基本定义

3.2.2 队列的顺序存储结构

1. 队列的顺序存储

3.2.3 循环队列

3.2.4 循环队列(顺序队列)的操作

1. 循环队列的初始化

2. 循环队列判空操作

3. 循环队列入队操作

4. 循环队列出队操作

3.3 队列的链式存储结构

3.3.1 队列的链式存储

3.4.2 链式队列的操作

1. 链队初始化

2. 链队判空

3. 链队入队

4. 链队出队

3.1 栈

3.1.1 栈的基本概念

1. 栈的定义

栈(Stack)是只允许在一端进行插入或删除操作的线性表，首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。

2. 栈的基本操作

InitStack(&S) :初始化栈
StackEmpty(S) :判断栈空
Push(&S,x) :元素进栈，若S未满，将x进栈
Pop(&S，&x) :读栈顶元素，若栈S非空，弹出栈顶元素
GetTop(S,&x) :读栈顶元素，若栈S非空，用x返回栈顶元素
DestroyStack(&S) :销毁栈，并释放S的存储空间。
在解答算法题时，若题干未做出限制，则可直接使用这些基本的操作函数。

3.1.2 栈的顺序存储结构 1. 栈的定义

//顺序栈的定义
#define MAX 10			  //定义栈长度
typedef int ElemType;
typedef struct {
	ElemType data[MAX];  //静态数组存放数组元素
	int top;			 //栈顶指针
}SqStack

2. 初始化一个栈

void InitStack(SqStack &S)
{
	S.top=-1;
}

3.进栈操作

bool StackEmpty(SqStack S)
{
	if (S.top = -1)
		return true;
	else
		return false;
}

4.出栈操作

bool Pop(SqStack &S, ElemType &x)
{
	if (S.top = -1) {
		return false;
	}
	x = S.data[S.top--];	//x = S.data[S.top]; S.top--;
	return true;
}

5.读取栈顶元素

bool GetTop(SqStack S, ElemType& x)
{
	if (S.top = -1)
		return false;
	x = S.data[S.top];
	return true;
}

7.共享栈和一些操作

利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间

//共享栈的定义
typedef struct {
	ElemType data[MAX];
	int top1;
	int top2;
}ShStack;

//共享栈的初始化
void InitStack(ShStack S)
{
	S.top1 = MAX;
	S.top2 = -1;
}

共享栈是为了更有效的利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。其存取数据的时间复杂度均为O(1) 。

3.1.3 栈的链式存储结构

链栈的优点是便于多个栈共享存储空间和提高效率。通常采用单链表实现，并规定所有操作都是在但链表的表头进行的。因而规定链栈没有头结点，Lhead指向栈顶元素。

//链的栈式存储结构
typedef struct linknode {
	ElemType data;
	struct linknode* next;
}* LiStack;

1.链栈的初始化

//链栈的初始化
void InitListack(LiStack& S)
{
	S = (linknode*)malloc(sizeof(linknode));
	S->next = NULL;
}

2.链栈的入栈操作

//链栈入栈
LiStack push_listack(LiStack& Head,ElemType e)
{
	linknode* s;
	InitListack(s);
	s->data = e;
	s->next = Head->next;
	Head->next = s;
	return Head;
}

3.链栈的出栈操作

//链栈出栈
LiStack pop_listack(LiStack& Head)
{
	while (Head == NULL)
		return NULL;
	linknode* s;
	InitListack(s);
	s = Head;
	Head = Head->next;
	free(s);
}

3.2 队列

3.2.1 队列的基本定义

队列(Queue)是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。这和我们在日常生活中的排队是一致的。其操作特性是先进先出的(First In First Out，FIFO)。

需要注意的是，站和队列都是操作受限的线性表，因此不是任何对线性表的操作都可以对栈和队列进行。

3.2.2 队列的顺序存储结构

1. 队列的顺序存储

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

//顺序队列的存储类型
#define MAX 50
typedef int ElemType;
typedef struct
{
	ElemType data[MAX];
	int front, rear;
}SqQueue;

初始状态：Q.front==Q.rear=0;该条件可以作为队空的条件，能否用Q.rear==MAX来表示队列满的条件呢？P78可知明显不能，队列中仅有一个元素，仍可满足条件，这是入队出现假溢出，这是需要引进循环队列。

3.2.3 循环队列

1.循环队列的定义

将顺序队列臆造成为一个环状的空间，即把存储队列的元素的表从逻辑上视为一个环，称为循环队列，当队首指针Q.front=MAX-1后，再前进一个位置就自动到0，这可以利用取余运算%来实现。

初始时：Q.front=Q.rear=0;
队首指针前进1：Q.front=(Q.front)+1;
队尾指针前进1：Q.rear=(Q.rear)+1;
队列长度：(Q.rear+MAX-Q.front)%MAX;

2.判断循环队列满

1.牺牲一个单元来区分队空和队满，约定队头指针在队尾指针的下一位置作为队满的标志 。

队满条件：(Q.rear+1)%MAX=Q.front;

队空条件：Q.front=Q.rear;

队列中元素个数：(Q.rear-Q.front+MAX)%MAX;

2.类型中增设表示元素个数的数据单元，这样队空的条件为Q.size==0;队满的条件为Q.seze==MAX;这两种情况下Q.rear=Q.front;

3.类型中增设tag标记，以此区分队满还是队空。tag==0时，若因删除导致Q.front=Q.rear则队空；tag==1时若因插入导致Q.front==Q.rear则队满。

3.2.4 循环队列(顺序队列)的操作

1. 循环队列的初始化

// 循环队列初始化
void InitQueue(SqQueue& Q)
{
	Q.rear = Q.front = 0;
}

2. 循环队列判空操作

//判队空
bool isEmpty(SqQueue& Q)
{
	if (Q.rear == Q.front)
		return true;
	else
		return false;
}

3. 循环队列入队操作

//入队操作
bool EnQueue(SqQueue& Q,ElemType e)
{
	if ((Q.rear + 1) % MAX == Q.front)
		return false;
	Q.data[Q.rear] = e;
	Q.rear = (Q.rear+1)% MAX;
	return true;
}

4. 循环队列出队操作

//出队操作
bool DeQueue(SqQueue& Q, ElemType& x)
{
	if (Q.rear == Q.front)
		return false;
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MAX;
	return true;
}

3.3 队列的链式存储结构

3.3.1 队列的链式存储

队列设置一个队头指针和一个队尾指针，它实际上是一个单链表。头指针指向队头结点，尾指针指向队尾结点。

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

//队列的链式存储类型
typedef struct linkNode {
	ElemType data;
	struct linkNode* next;
}linkNode;
typedef struct {
	linkNode* front, * rear;
}linkQueue;

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

出队时，首先判断队列是否为空；若不空取出队头元素，从链表摘除，并让Q.front指向下一结点。入队时，建立一个新结点，将新结点插入到链表的尾部，并改让Q.rear指向新插入的结点。

若这些操作使用不带头结点的链表进行操作，出队时将不停修改头结点，倘若采用带头结点的链表，则改为修改指针。因此链式队列通常采用带有头结点的链表。

3.4.2 链式队列的操作

1. 链队初始化

//链式队列的初始化
void InitQueue(linkQueue& Q)
{
	Q.front = Q.rear = (linkNode*)malloc(sizeof(linkNode));
	Q.front->next = NULL;
}

2. 链队判空

//判队空
bool IsEmpty(linkQueue& Q)
{
	if (Q.rear == Q.front)
		return true;
	else
		return false;
}

3. 链队入队

//入队操作
void EnQUueue(linkQueue& Q,ElemType e)
{
	linkNode *s = (linkNode*)malloc(sizeof(linkNode));//*s表示新结点
	s->data = e;
	s->next = Q.rear->next;
	Q.rear->next = s;
	Q.rear = s;
}

4. 链队出队

//出队操作
void DeQueuE(linkQueue& Q, ElemType& x)
{
	if (Q.front == Q.rear)
		return;
	linkNode* s = (linkNode*)malloc(sizeof(linkNode));//*s表示新结点
	s = Q.front->next;
	x = s->data;
	Q.front->next = s->next;
	if (Q.rear == s)
		Q.rear = Q.front;
	free(s);
}