栈和队列是两种最重要的数据结构，也是两种最典型的的抽象数据类型，应用非常广泛。从逻辑结构上看，栈和队列都属于线性结构。它们与线性表的主要区别在于它们的操作，或者说它们是两个不同的抽象数据类型的实现。对于栈和队列上的插入、删除操作时受某种特殊限制的。因此，栈和队列也称为操作受限的表，或者限制存取点的表
4.1 栈及其抽象数据类型
4.1.1 基本概念
栈是一种特殊的线性表，对于它所有的插入和删除都限制在表的同一端进行。允许插入、删除操作的一端叫做栈顶，另一端则叫做栈底。当栈中没有元素时，称为空栈。
栈的插入运算通常称为进栈或入栈，栈的删除运算通常称为退栈或出栈。
栈又称为后进先出表(Last In First Out表或 LIFO表)或下推表。
4.1.2 抽象数据类型
ADT Stack is
operations
// 创建一个空栈
Stack createEmptyStack(void)
// 判断栈st是否为空栈
int isEmptyStack(Stack st)
// 往栈st插入一个值为x的元素
void push(Stack st, DataType x)
// 从栈顶删除元素
void pop(Stack st)
// 获取栈顶元素的值
DataType top(Stack st)
end ADT Stack
4.2 栈的实现
4.2.1 顺序表示
存储结构
用顺序的方式表示栈时，要分配一块连续的存储区域存放占栈中的元素，并用一个变量来表示当前栈顶的位置
typedef struct SeqStack {
int MAXNUM; // 栈中最大元素个数
int t; // t < MAXNUM 指示栈顶位置，而不是元素个数
DataType *s;
} SeqStack;
当栈已经有MAXNUM个元素时，如果再做进栈运算，则会产生移除，通常称上溢(Overflow)，而对空栈进行出栈运算时也会产生溢出，通常称下溢(Underflow)。
进栈
void push_seq(SeqStack *pstack, DataType) {
if (pstack->t >= pstack->MAXNUM - 1) {
printf("overflow!\n");
} else {
pstack->t = pstack->t+1;
pstack->s[pstack->t] = x;
}
}
出栈
void pop_seq(SeqStack *pstack) {
if (pstack->t == -1) {
printf("Underflow!\n");
} else {
pstack->t = pstack->t - 1;
}
}
取出栈顶元素
DataType top_seq(SeqStack *pstack) {
if (pstack->t == -1) {
printf("It is empty!\n");
} else {
return pstack->s[pstack->t];
}
}
4.2.2 链接表示
typedef struct Node {
DataType info;
struct Node * link;
} Node;
// 链接栈类型定义
typedef struct LinkStack {
Node *top; // 栈顶结点
} LinkStack;
创建一个空链栈
LinkStack *createEmptyStack_link(void) {
LinkStack *plstack;
plstack = (LinkStack *) malloc(sizeof(struct LinkStack));
if (plstack != NULL) {
plstack->top = NULL;
} else {
printf("Out of space!\n");
}
return plstack;
}
判断单链形式栈是否为空栈
int isEmptyStack_Link(LinkStack *plstack) {
return plstack->top == NULL;
}
进栈
void push_link(LinkStack *plstack, DataType x) {
Node *p;
p = (Node *) malloc(sizeof(Node));
if (p == NULL) {
printf("Out of space!\n");
} else {
p->info = x;
p->link = plstack->top;
plstack->top = p;
}
}
出栈
void pop_link(LinkStack *plstack) {
Node *p;
if (isEmptyStack_link(plstack)) {
printf("Empty stack pop.\n");
} else {
p = plstack->top;
plstack->top = plstack->top->link;
free(p);
}
}
取出栈顶元素
DataType top_link(LinkStack *plstack) {
if (plstack->top == NULL) {
printf("Stack is empty!\n");
} else {
return plstack->top->info;
}
}
4.3 栈的应用
4.3.1 栈与递归
递归时程序设计中最有力的表达方法之一。许多程序设计语言都提供了递归的功能，使许多问题能够采用递归的方式来描述，编出的程序简洁、清晰。
函数自己调用自己的做法称谓递归调用
递归函数到非递归函数的转换
函数调用的实现可以分解成一下三步：
- 调用函数发送调用信息
- 分配被调函数需要的数据区，并接收调用函数传来的调用信息。
- 把控制转移到被调函数的入口
被调调函数运行结束，需要返回到调用函数时，返回处理也可以分解成三步： - 传送返回信息
- 接收被调函数送来的返回信息并释放被调函数的数据区
- 把控制按返回地址转移到调用函数中
4.4 队列及其抽象数据类型
4.4.1 基本概念
队列是一种特殊的线性表，是一种只允许在表的一端进行插入操作，而在另一端进行删除操作的线性表。允许进行删除的一端称为队头，允许进行插入的一端叫做队尾。当队列中没有任何元素时，称为空队。
队列的插入操作通常称为入队，队列的删除操作通常称为出队。
队列时一个先进先出表(First In First Out表，简称FIFO表)
4.4.2 抽象数据类型
ADT Queue is
operations
// 创建空队列
Queue createEmptyQueue(void)
// 判断队列是否为空
int isEmptyQueue(Queue q)
// 入队
void enQueue(Queue q, DataType x)
// 出队
void deQueue(Queue q)
// 取出队列的头元素
DataType frontQueue(Queue q)
end ADT Queue
4.5 队列的实现
4.5.1 顺序表示
typedef struct SeqQueue {
int MAXNUM;
int f, r;
DataType *q;
} SeqQueue;
当队列满时，再做入队操作，这种现象称为上溢。当队列空时，做出队操作，这种现象称为下溢。
入队
void enQueue_seq(SeqQueue *pque, DataType x) {
if ((pque->r + 1) % MAXNUM == pque->f) {
printf("Full queue.\n");
} else {
pque->q[pque->r] = x;
pque->r = (pque->r + 1) % MAXNUM;
}
}
出队
void deQueue_seq(SeqQueue pque) {
if (pque->f == pque->r) {
printf("Empty Queue.\n");
} else {
pque->f = (pque->f + 1) % MAXNUM;
}
}
取出队列头元素
DataType frontQueue_seq(SeqQueue pque) {
if (pque->f == pque->r) {
printf("Empty Queue.\n");
} else {
return pque->q[pque->f];
}
}
4.5.2 链接表示
typedef struct Node {
DataType info;
struct Node *link;
} Node;
typedef LinkQueue {
Node *f;
Node *r;
} LinkQueue;
创建一个空队
LinkQueue *createEmptyQueue_link(void) {
LinkQueue *plque;
plque = (LinkQueue*) malloc(sizeof(LinkQueue));
if (plque != NULL) {
plque->f = NULL;
plque->r = NULL;
} else {
printf("Out of space!\n");
}
return plque;
}
判断链接表示的队列是否为空队
int isEmptyQueue_link(LinkQueue *plque) {
return plque->f == NULL;
}
入队
void enQueue_link(LinkQueue *plque, DataType x) {
Node *p;
p = (Node *) malloc(sizeof(Node));
if (p == NULL) {
printf("Out of space!\n");
} else {
p->info = x;
if (plque->f == NULL) {
plque->f = p;
} else {
plque->r->link = p;
plque->r = p;
}
}
}
出队
void deQueue_link(LinkQueue *plque) {
Node *p;
if (plque->f == NULL) {
printf("Empty queue.\n");
} else {
p = plque->f;
plque->f = p->link;
free(p);
}
}
取队列头部结点的值
DataType frontQueue_link(LinkQueue *plque) {
if (plque->f == NULL) {
printf("Empty queue.\n");
} else {
plque->f->info;
}
return NULL;
}
网友评论