栈和队列及其应用（第五章栈和队列）
栈和队列及其应用（第五章栈和队列）③ S(TOP)=X，结束（X为新进栈的元素）；② 置TOP=TOP 1（栈指针加1，指向进栈地址）；计算机系统中，栈是一个具有以上属性的动态内存区域。程序可以将数据压入栈中，也可以将数据从栈顶弹出。压栈操作使得栈增长变大，而弹出操作使栈减短缩小。进栈（PUSH）算法：① 若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；
第五章 栈和队列5.1 栈5.1.2 栈概述栈（stack）又名堆栈，它是一种运算受限的线性表。在计算机中栈被定义为一个特殊的容器。其限制是仅允许在表的一端进行插入和删除操作。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈（Push），它是把新元素存放到栈顶元素的上面，使之成为新的栈顶元素；也可以将已经压入到栈中的元素弹出，即从一个栈删除元素又称作出栈或退栈（pop），它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
【栈结构图】
栈按照先进后出 （First In Last Out，FILO）的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。
栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（push），删除则称为退栈（pop）。栈也称为后进先出表。
计算机系统中，栈是一个具有以上属性的动态内存区域。程序可以将数据压入栈中，也可以将数据从栈顶弹出。压栈操作使得栈增长变大，而弹出操作使栈减短缩小。
5.1.2 栈的表示和实现进栈（PUSH）算法：
① 若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；
② 置TOP=TOP 1（栈指针加1，指向进栈地址）；
③ S(TOP)=X，结束（X为新进栈的元素）；
退栈（POP）算法：
① 若TOP≤0，则给出下溢信息，作出错处理（退栈前先检查是否已为空栈， 空则下溢；不空则作②）；
② X=S(TOP)，（退栈后的元素赋给X）；
③ TOP=TOP-1，结束（栈指针减1，指向栈顶）。
定义stack的简单代码：
stack<int> myStack;
入栈：myStack.push(x);
出栈：myStack.pop();
栈顶元素：myStack.top();
判断栈的大小： myStack.size();
判断栈是否为空：myStack.empty();
【程序实现】
#include <stdlib.h>
#include <stdio.h>
#define N 10
typedef struct
{
int data[N];
int top;
} SqStack; //顺序栈类型别名
//初始化栈
SqStack* initStack()
{
SqStack* s = (SqStack * )malloc(sizeof(SqStack));
s->top = -1;
return s;
}
//取栈顶元素
int getTop(SqStack * s int* e)
{
if (s->top == -1) {
return -1;
}
*e = s->data[s->top];
return *e;
}
//进栈
int Push(SqStack * s int e)
{
if (s->top == N - 1) {
return -1;
}
s->top ;
s->data[s->top] = e;
return 1;
}
//出栈
int Pop(SqStack * s int* e)
{
if (s->top == -1) {
return -1;
}
*e = s->data[s->top];
s->top--;
return 1;
}
//销毁栈
void destroyStack(SqStack * s)
{
free(s);
}
//测试栈的初始化、入栈、出栈、获取栈顶元素等功能
int main()
{
printf("初始化栈...\n");
SqStack* s = initStack();
printf("入栈中...\n");
Push(s 1);
Push(s 2);
Push(s 3);
printf("入栈完成...\n");
printf("获取栈顶元素:\n");
int y;
getTop(s &y);
printf("y: %d\n" y);
printf("出栈:\n");
int x;
Pop(s &x);
printf("x:%d\n" x);
Pop(s &x);
printf("x:%d\n" x);
Pop(s &x);
printf("x:%d\n" x);
printf("销毁栈...\n");
destroyStack(s);
return 0;
}5.2 队列5.2.1 队列概述
与栈相反，队列（queue）是一种先进先出（first in first out，缩写为FIFO）的线性表。它只允许在表的一端进行插入元素，而在另一端删除元素。
在队列中，允许插入的一端叫做队尾（rear），允许删除的一端则称为队头（front）。
队列拥有两种表示和实现方式：
1、队列的链式表示和实现--链队列
2、队列的顺序表示和实现--循环队列
5.2.2 链队列—队列的链式表示和实现用链表表示的队列简称为链队列。一个链队列需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。为操作方便，给链队列添加一个头结点，并令头指针指向头结点。由此，空的链队列的判断条件为头指针和尾指针均指向头结点。
【链队列结构图】
【链队列操作示意图】
【程序实现】
#include <stdio.h>
#include <stdlib.h>
#define OVERFLOW -2
#define ERROR 0
#define OK 1
typedef int Status;
typedef int QElemType;
typedef struct QNode {
QElemType data;
struct QNode *next;
}QNode *QueuePtr;
typedef struct {
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
/*********** 初始化队列 ***********/
Status InitQueue(LinkQueue * Q)
{
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
if (!Q->front)
exit(OVERFLOW);
Q->front->next=NULL;
return OK;
}
/*********** 入队列 ***********/
Status EnQueue(LinkQueue *Q QElemType e)
{
//插入元素e为Q的新的队尾元素
QueuePtr p;
p = (QueuePtr)malloc(sizeof(QNode));
if(!p)
exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
return OK;
}
/*********** 出队列 ***********/
Status DeQueue(LinkQueue *Q QElemType *e)
{
//若队列不空 则删除Q的头元素，用e返回其值，并返回OK。
QueuePtr p;
if(Q->front==Q->rear)
exit(ERROR);
p=Q->front->next;
*e=p->data; // 一定是*e
Q->front->next=p->next;
if(Q->rear==p)
Q->rear=Q->front;
free(p);
return OK;
}
/*********** 销毁队列Q ***********/
Status DestroyQueue(LinkQueue * Q){
while (Q->front) {
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
return OK;
}
int main()
{
LinkQueue *Q;
QElemType e;
/*********** 初始化队列 ***********/
InitQueue(Q);
printf("请输入5个整数：");
for(int i=0; i<5; i )
{
/*********** 入队列 ***********/
scanf("%d" &e);
EnQueue(Q e);
}
printf("输出结果为：\n");
while (Q->front!=Q->rear)
{
/*********** 出队列 ***********/
DeQueue(Q &e);
printf("%d " e);
}
printf("\n");
/*********** 销毁队列Q ***********/
DestroyQueue(Q);
return 0;
}5.2.3 循环队列—队列的顺序表示和实现
为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。
循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。
在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时front=（rear 1）%MaxSize。
【循环队列结构图】
【循环队列操作示意图】**
【程序实现】**
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
#define MAXQSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define False 0
#define True 1
typedef int Status;
typedef int QElemType;
typedef struct
{
QElemType *base; //存储空间的基地址
int front; //头指针
int rear; //尾指针
}SqQueue;
//循环队列的初始化
Status InitQueue(SqQueue &q)
{
q.base = new QElemType[MAXQSIZE]; //为队列分配一个最大容量为 MAXQSIZE 的数组空间
if(!q.base)
exit(OVERFLOW); //存储分配失败
q.front = q.rear = 0; //头指针和尾指针置为零，队列为空
return OK;
}
//求循环队列的长度
int QueueLength(SqQueue q)
{
return (q.rear - q.front MAXQSIZE) % MAXQSIZE; //返回Q的元素个数，即队列长度
}
//入队
Status EnQueue(SqQueue &q QElemType e)//插入元素 e 为Q的新的队尾元素
{
if((q.rear 1) % MAXQSIZE == q.front) //尾指针在循环意义上加1后等于头指针，表明队满
return ERROR;
q.base[q.rear] = e; //新元素插入队尾
q.rear = (q.rear 1) % MAXQSIZE; //队尾指针加1
return OK;
}
//出队
Status DeQueue(SqQueue &q QElemType &e)//删除 q 的队头元素，用 e 返回其值
{
if(q.front==q.rear)
return ERROR; //队空
e = q.base[q.front]; //保存队头元素
q.front = (q.front 1) % MAXQSIZE;//队头指针加1
return OK;
}
//取队头元素
QElemType GetHead(SqQueue q)//返回 的队头元素，不修改队头指针
{
if(q.front != q.rear) //队列非空
return q.base[q.front];//返回队头元素的值，队头指针不变
return ERROR;
}
//队列判满
bool FullQueue(SqQueue &q)
{
if(q.rear == (q.front 1) % MAXQSIZE)
return 1;
else
return 0;
}
//队列判空
bool EmptyQueue(SqQueue &q)
{
if(q.front==q.rear)
return 1;
else
return 0;
}
int main()
{
QElemType e;
SqQueue q;
InitQueue(q);
int count = 0;
printf("请输入要入队的元素个数:\n");
scanf("%d" &count);
for (int i = 0; i < count; i ) {
printf("请输入第%d个数: " i 1);
int iNum = 0;
scanf("%d" &iNum);
EnQueue(q iNum);
}
printf("队列长度： %d\n" QueueLength(q));
printf("获取队列头元素: %d\n" GetHead(q));
printf("输出结果为：\n");
while (q.front != q.rear)
{
/*********** 出队列 ***********/
DeQueue(q e);
printf("%d " e);
}
printf("\n");
if(FullQueue(q))
printf("队列已满\n");
if(EmptyQueue(q))
printf("队列为空\n");
return 0;
}
