数据结构--第三章 栈和队列

注：根据严蔚敏等人的数据结构（C语言版）（第二版）记录，用于自己的复习记录。

栈

栈是限定仅在表尾进行插入和删除的线性表。表尾端称为栈顶，表头端称为栈底。不含元素的空表称为空栈。栈是后进先出的线性表。

一、顺序栈的表示和实现

顺序栈指的是利用顺序存储结构实现的栈，即利用一组连续的地址存储单元依次存储从栈底到栈顶的数据元素，同时附设指针top表示栈顶元素在顺序栈的位置。另设指针base指使栈底元素在顺序栈中的位置。当top和base的值相等时，表示空栈。

顺序栈的存储结构

#define MAXSIZE 100  //顺序栈存储空间的初始分配量
typedef struct{
sElemType *base;
sElemType *top;
int stacksize;  //栈可用的最大容量
}SqStack;

1.1顺序栈的初始化

1. 为顺序栈动态分配一个最大容量的MAXSIZE的数组空间，使得base指向这段空间的基地址，即栈底。
2. 栈顶指针top初始为base，表示栈为空。
3. stacksize置为栈的最大容量MAXSIZE

Status InitStack(SqStack &S){
S.base = new SElemType[MAXSIZE];
if(!S.base) exit(OVERFLOW);
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}

1.2入栈

1. 判断栈是否满，若满则返回ERROR。
2. 将新的元素压入栈顶，栈顶指针加一。

Status Push(SqStack &S, SElemType e){
if(S.top-S.base == S.stacksize) return ERROR;
*S.top ++= e;
return OK;
}

1.3出栈

1. 判断栈是否为空，为空则返回ERROR；
2. 栈顶指针减一，栈顶元素出栈。

Status Pop(SqStack &S,SElemType &e){
if(S.top == S.base) return ERROR;
e = *--S.top;
return OK;
}

1.4取顺序栈的栈顶元素

当栈非空时，此操作返回当前栈顶元素的值，栈顶指针保持不变。

SElemType GetTop(SqStack S){
if(S.top != S.base)
return *(S.top-1);
}

二、链栈的表示和实现

链栈指的是利用链式存储结构存储的栈。通常链栈用单链表来表示。

链栈的存储结构

typedef struct StackNode{
ElemType data;
struct StackNode *next;
}StackNode, *LinkStack;

2.1链栈初始化

构造一个空栈，直接将栈顶指针置空即可。

Status InitStack(LinkStack &S){
S = NULL;
return OK;
}

2.2链栈的入栈

1. 为新入栈元素分配一个空间，并用指针p指向。
2. 将新结点的数据域置为e。
3. 将新结点插入栈顶。
4. 修改栈顶指针为p。

Status Push(LinkStack &S, ElemType e){
p = new StackNode;
p -> data = e;
p -> next = S;
S = p;
return OK;
}

2.3链栈的出栈

出栈时要判断栈是否为空，同时出栈后记得释放栈元素所在的空间。

1. 判断栈是否为空，若空则反悔ERROR；
2. 将栈顶元素赋值给e；
3. 临时保存栈顶元素的空间，以备释放；
4. 修该栈顶指针，指向新的栈顶元素；
5. 释放原来的栈顶空间。

Status Pop(LinkStack &S, ElemType e){
if(S == NULL) return ERROR
e = S -> data;
p = S;
S = S->next;
delete p;
return OK;
}

2.4取链栈的栈顶元素

当栈非空的时候，返回当前栈顶元素的值，栈顶指针S保持不变。

SElemType GetTop(LinkStack S){
if(S != NULL)
return S->data;
}

队列

队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许插入的一端称为队尾，允许删除的一端称为队头。例如操作系统中的作业排队。

一、循环队列-----队列的顺序表示和实现

队列的顺序表示指用一组地址连续的存储单元依次存放队列中从队头到队尾的元素。同时需要两个整型变量front和rear分别指示队列头和队列尾元素的位置（成为头指针和尾指针）。

队列的顺序存储结构表示：

# define MAXSIZE 100
typedef struct{
QElemType *base;  //存储空间基地址
int front；
int rear;
}SqQueue;

约定：初始创建空队时，令front = rear = 0，每当插入一个元素，rear加一；当删除一个元素，front加一。在非空队列中，头指针指向队列头元素，而尾指针指向队列尾元素的下一个位置。

循环队列如何区分队空以及队满？

1. 少用一个元素空间。即队列空间为m时，有m-1个元素则认为队满。即队空的条件：Q.front = Q.rear；队满的条件：(Q.rear + 1) % MAXSIZE = Q.front。
2. 另外设定一个标志来区分队空还是队满

1.1循环队列初始化

1. 为队列分配一个最大容量为MAXSIZE的数组空间，base指向数组空间的首地址。
2. 头指针和尾指针置为零，表示队列已空。

Status InitQueue(SqQueue &Q){
Q.base = new QElemType[MAXSIZE]
if(!q.base) exit (OVERFLOW);
Q.front = Q.base = 0;
return OK;
}

1.2求循环队列的长度

对于循环队列，差值可能是负数，所以需要在差值加上MAXSIZE再对MAXSIZE取余

int QueueLength(SqQueue Q){
return (Q.base - Q.front + MAXSIZE) % MAXSIZE;
}

1.3循环队列的入队

1. 判断队列是否已经满了，若满了则返回ERROR；
2. 将新元素加入队尾；
3. 队尾指针加一。

Status EnQueue (SqQueue &S, QElemType e){
if((Q.rear+1)%MAXSIZE == Q.front)
return ERROR;
Q.base[Q.rear] = e;
Q.rear = (Q.rear+1)%MAXSIZE; //队尾指针加一
return OK;
}

1.4循环队列的出队

1. 判断队列是否为空，若为空返回ERROR；
2. 保留队头指针；
3. 队头指针加一。

Status DeQueue (SqQueue &Q, QElemType &e){
if (Q.front == Q,rear) return ERROR;
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXSIZE;
return OK;
}

1.5取循环队列的队头元素

SelemType GetHead (SqQueue Q){
if(Q.front != Q.rear)
return Q.base[Q.front];
}

二、链队-----队列的链式表示和实现

链队指的是利用链式存储结构实现的队列，一般采用单链表，需要一个头指针和一个尾指针才能唯一确定一个链队。

链队的存储结构

typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode *QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue

2.1链队的初始化

1. 生成一个新结点作为头结点，队头和队尾指针分别指向这个新结点；
2. 头结点的指针域置为空。

Statue InitQueue(LinkQueue &Q){
Q.front = Q.rear = new QNode;
Q.front ->next = NULL;
return OK;
}

2.2链队的入队

1. 为入队严肃分配结点空间，用指针p指向；
2. 将新结点数据域置为e；
3. 将新结点插入队尾；
4. 修改队尾指针为p。

Statue EnQueue(LinkQueue &Q, ElemType e){
p = new QNode;
p -> data = e;
p -> next = NULL;
Q.rear -> next = p;
Q.rear = p;
return OK;
}

2.3链队的出队

1. 判断链队是否为空，若为空返回ERROR；
2. 临时保存队头元素的空间，以便释放；
3. 修改队头指针指向下一个指针；
4. 判断出队元素是否为最后一个元素，若为最后一个元素，则将队尾指针重新赋值，指向头结点；
5. 释放原队头元素的空间。

Statue DeQueue(LinkQueue &Q,QElemType &e){
if (Q.front == Q.rear) return ERROR;
p = Q.front->next;
e = p -> data;
Q.front -> next = p -> next;
if(Q.rear == p) Q.rear = Q.front;
delete p;
return OK;
}

2.4取链队的队头元素

SElemType GetHead(LinkQueue Q){
if(Q.front != Q.rear)
return Q.front->next->data;
}

小结