栈是限定仅在表尾进行插入和删除操作的线性表。表尾端称为栈顶，表头端称为栈底。不含元素的空表称为空栈。
栈是后进先出的线性表。
队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表。队列是先进先出的线性表。
1. 栈
(1) 顺序栈的表示和实现
顺序栈是指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。另设指针base指示栈底元素在顺序栈中的位置。
当top和base的值相等时，表示空栈。
1. 顺序栈的存储结构
#define MAXSIZE 100 /* 存储空间初始分配量 */
typedef int Status;
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */
/* 顺序栈结构 */
typedef struct{
SElemType *base;//栈底指针
SElemType *top;//栈顶指针
int stacksize;//栈可用的最大容量
}
base指针的值为NULL，则表明栈结构不存在。
栈非空时，top始终指向栈顶元素的上一个位置。
2. 顺序栈的初始化
- 为顺序栈动态分配一个最大容量为MAXSIZE的数组空间，使base指向这段空间的基地址，即栈底。
- 栈顶指针top初始值为base。
- stacksize置为栈的最大容量MAXSIZE。
Status InitStack(SqStack &S)
{
S.base = new SElemType[MAXSIZE]; //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
if(!S.base) exit(OVERFLOW);//存储分配失败
S.top = S.base;//top初始为base，空栈
S.stacksize = MAXSIZE;// stacksize置为栈的最大容量MAXSIZE
return OK;
}
3. 顺序栈的入栈
- 判断栈是否为满，若满则返回ERROR。
- 将新的元素压入栈顶，栈顶指针加1。
Status Push(SqStack &S,SElemType e)
{
// 插入元素e为新的栈顶元素
if(S.top - S.base == S.stacksize) return ERROR;//栈满
＊S.top ++ = e; //元素e压入栈顶，栈顶指针加1
return OK;
}
4.出栈
- 判断栈是否为空，若空则返回ERROR。
- 栈顶指针减1，栈顶元素出栈。
Status Pop(SqStack &S,SElemType &e)
{
//删除S的栈顶元素，用e 返回其值
if(S.top == S.base) return ERROR ; // 栈空
e = *--S.top; //栈顶指针减1，将栈顶元素赋值给e
return OK;
}
5. 取栈顶元素
当栈非空时，此操作返回当前栈顶元素的值，栈顶保持不变。
Status GetTop(SqStack S)
{
if (S.top ! = S.base) //栈非空
return *(S.top -1);//返回栈顶元素的值，栈顶指针不变。
}
(2) 链栈的表示和实现
链栈是指采用链式存储结构实现的栈。
1. 链栈的存储结构
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStackPtr;
2. 链栈的初始化
链栈的初始化操作就是构造一个空栈，因为没必要设头结点，所以直接将栈顶指针置空即可。
Status InitStack(LinkStack &S)
{//构建一个空栈S，栈顶指针置空
S = NULL:
return OK;
}
3. 链栈的入栈
- 为栈元素e分配空间，用指针p指向。
- 将新结点数据域置为e。
- 将新结点插入栈顶
- 修改栈顶指针为p。
Status Push(LinkStack &S,SElemType e)
{
p = new StackNode; //生成新结点
p->data = e;//将新结点数据域置为e
p->next = S;//将新结点插入栈顶
S = p;//修改栈顶指针为p
return OK;
}
4. 链栈的出栈
- 判断栈是否为空，若空则返回ERROR。
- 将栈顶元素赋值给e。
- 临时保存栈顶元素的空间，以备释放。
- 修改栈顶指针，指向新的栈顶元素。
- 释放元栈顶元素
Status Pop(LinkStack &S,SElemType &e)
{
//删除S的栈顶元素，用e返回其值。
if(S==NULL) return ERROR;
e = S -> data;
p = S;
S = S->next;
delete p;
return OK;
}
5. 取栈顶元素
SElemType GetTop (LinkStack S)
{
if(S != NULL) //栈非空
return S->data;//返回栈顶元素，栈指针不变。
}
(3) 栈与递归
Hanoi塔问题
- 每次只能移动一个圆盘。
2.圆盘可以插在A、B和C中的任一塔座上。 -
任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。
Hanoi塔问题的递归算法
- 如果 n＝1,则直接将编号为1的圆盘从A移到C，递归结束。
- 否则：
1.递归，将A上编号为1至n-1的圆盘移到B，C做辅助塔。
- 直接将编号为n的圆盘从A移到C。
- 递归，将B上编号为1至n-1的圆盘移动到C，A做辅助塔。
void Hanoi(int n,char A,,char B,char C)
{
if (n == 1) move(A,1,C); //将编号为1的圆盘从A移到C
else
{
Hanoi(n-1,A,C,B); //将A上编号为1至n-1的圆盘移到B，C做辅助
move(A,n,C);//将编号为 n的圆盘从A移到C
Hanoi(n-1,B,A,C);//将B上编号为1至n-1的圆盘移到C，A做辅助
}
}
/* 将搬动操作定义为move(A,n,C)，是指将编号为n的圆盘从A移动到C，同时设置一个初始值为0的全局变量m,对搬动进行计数。*/
int m;
void move(char A,int n,char C)
{
count<<++m<<","<<n<<","<<A<<","<<C<<endl;
}
2. 队列
(1) 循环队列-队列的顺序表示和实现
1. 队列的顺序存储结构
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */
typedef int Status;
typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */
/* 循环队列的顺序存储结构 */
typedef struct{
QElemType *base /*存储空间的基地址*/
int front; /* 头指针 */
int rear; /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
- 附设两个整型变量front和rear指针分别指示队列头元素及队列尾元素的位置。
- 初始化创建空队列时，令front ＝ rear = 0
- 每当插入新的队列尾元素时，尾指针rear增1，每当删除队列头元素时，头指针front增1.
- 在非空栈中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。
循环队列，解决假溢出问题
队空队满的判断：
- 少用一个元素空间。即队列空间大小为m时，由m－1个元素就认为是队满。
- 当头、尾指针相等时，队空。当尾指针在循环意义上加1后是等于头指针，则认为队满。
队空条件：Q.front == Q.rear
队满条件：(Q.rear+1)%MAXQSIZE == Q.front
2. 循环队列的初始化
- 为队列分配一个最大容量的MAXSIZE的数组空间，base指向数组空间的首地址。
- 头指针和尾指针为零，表示队列为空。
/* 初始化一个空队列Q */
Status InitQueue(SqQueue *Q)
{
Q.base = new QElemType[MAXQSIZE]; //为队列分配一个最大容量为MAXQSIZE的数组空间
if (!Q.base) exit(OVERFLOW);
Q->front =Q->rear=0;
return OK;
}
3. 求循环队列的长度
/* 返回Q的元素个数，也就是队列的当前长度 */
int QueueLength(SqQueue Q)
{
return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}
4. 循环队列的入队
- 判断队列是否满，若满则返回ERROR。
- 将新元素插入队尾。
- 队尾指针加1。
Status EnQueue(SqQueue &Q,QElemType e){
if ((Q.rear+1)%MAXSIZE == Q.front) /* 队列满的判断 */
return ERROR;
Q.base[Q.rear]=e; /* 将元素e赋值给队尾 */
Q->rear=(Q.rear+1)%MAXSIZE;/* rear指针向后移一位置， */
return OK;
}
5. 循环队列的出队
- 判断队列是否为空，若为空则返回ERROR。
- 保存队列头元素。
- 对头指针加1。
Status DeQueue(SqQueue &Q,QElemType &e){
if (Q.front == Q.rear) /* 队列空的判断 */
return ERROR;
e=Q.base[Q.front]; /* 将队头元素赋值给e */
Q.front=(Q.front+1)%MAXSIZE; /* front指针向后移一位置，若到最后则转到数组头部 */
return OK;
}
6. 取循环队列的对头元素
SElemType GetHead(SqQueue Q)
{
if(Q.front != Q.rear)//队列非空
return Q.base[Q.front];//返回队头元素的值，队头指针不变。
}
(2) 链队-队列的链式表示和实现
链队采用链式存储结构实现的队列。为了方便操作，给链队添加一个头结点，并令头指针始终指向头结点。
1. 队列的链式存储结构
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */
typedef int Status;
typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */
typedef struct QNode /* 结点结构 */
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct /* 队列的链表结构 */
{
QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;
2. 链队的初始化
- 生成一个新结点作为头结点，对头和队尾指针指向此结点。
- 头结点的指针域置空。
Status InitQueue(LinkQueue &Q)
{
//构造一个空队
Q.front = Q.rear = new QNode;
Q.front->next = NULL;
return OK;
}
3. 链队的入队
- 为元素分配新的结点空间，用指针p指向。
- 将新结点数据域设置为e。
- 将新结点插入到队尾。
- 修改队尾指针为p。
Status EnQueue(LinkQueue &Q,QElemType e)
{
p = new QNode;
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear = p
return OK;
}
4. 链队的出队
- 判断队列是否为空，若空则返回ERROR。
- 临时保存队列的头元素，以备释放空间。
- 修改队头指针，指向下一个结点。
- 判断出队元素是否为最后一个元素，若是，则将队尾指针重新赋值，指向队头结点。
- 释放元队头元素空间。
Status DeQueue(LinkQueue &Q,QElemType &e)
{
QueuePtr p;
if(Q.front==Q.rear)
return ERROR;
p=Q.front->next; //p指向队头元素
e=p->data; //e保存队头元素的值
Q.front->next=p.next; //修改头指针
if(Q.rear==p) //最后一个元素被删，队尾指针指向队头指针
Q.rear=Q.front;
delete p;
return OK;
}
4. 取链队的队头元素
SElemType GetHead(LinkQueue Q)
{
if(Q.front != Q.rear)
return Q.front->next->data;
}
(3) 循环队列和链队列的比较
- 时间上，基本操作都是常数时间，即O（1）,不过，循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点会存在一些时间开销，如果入队出队频繁，则两者还是略有差异。
- 空间上，循环队列必须有固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这样的问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。
- 总之，在可以确定队列长度最大值的情况下，建议用循环队列，如果无法预估队列的长度，则用链队列。
插入元素时间复杂度为O（1），删除时是O（n），因为后面的所有元素要向前移;
