文档介绍：第三章栈和队列
栈
队列
栈与队列的比较
第三章栈和队列
栈
栈的定义及运算
栈(Stack)是运算受限的线性表,限制它的插入和删除操作仅在表的一端进行。
栈顶(Top),栈顶元素,栈底(Bottom),空栈,进栈或入栈,出栈或退栈。
后进先出的线性表(Last In First Out),简称 LIFO表
栈的基本运算有五种:
(1)初始化栈 initStack(s):构造了一个空栈s。
(2)判栈空empty(s):若栈s为空栈,返回值为“真”
(1),否则返回值为“假”(0)。
(3)入栈push(s,x):在栈s的顶部插入一个新元素x ,
x成为新的栈顶元素。
(4)出栈pop(s):删除栈s的栈顶元素。
(5)读栈顶元素top(s):栈顶元素作为结果返回,
不改变栈的状态。
顺序栈及运算的实现
采用顺序方式存储的栈称为顺序栈(Sequential Stack)。
顺序栈用C语言描述如下:
#define MAXSIZE 1024 /*栈可能达到的最大容量*/
typedef int DataType;
typedef struct
{ DataType data[MAXSIZE];
int top;
}SeqStack ;
SeqStack *s; /*定义s是一个指向顺序栈的指针*/
栈的操作及栈顶指针变化情况
在顺序栈上实现五种基本运算的C函数
(1)初始化栈首先建立栈空间,然后初始化栈顶指针。
SeqStack *initSeqStack()
{ SeqStack *s;
s=(SeqStack*)malloc(sizeof(SeqStack));
s->top= -1;
return s;
}
(2)判栈空
int empty (SeqStack *s)
{ if (s->top== -1)
return 1;
else
return 0;
}
在顺序栈上实现五种基本运算的C函数
(3)入栈
int push (SeqStack *s, DataType x)
{ if (s->top==MAXSIZE-1) /*栈满不能入栈*/
{ printf("overflow");
return 0;
}
s->top++;
s->data[s->top]=x;
return 1;
}
在顺序栈上实现五种基本运算的C函数
(4)出栈
void pop (SeqStack *s) /*设栈不空*/
{ s->top--;
}
(5)读栈顶元素
DataType top (SeqStack *s) /*设栈不空*/
{ return (s->data[s->top] );
}
链栈及运算的实现
采用链接方式存储的栈称为链栈(Linked Stack)
链栈用C语言描述如下:
typedef struct Node
{ DataType data;
struct Node *next;
} LinkStack;
LinkStack *top ; /*说明top为栈顶指针*/
栈的应用
将一个十进制正整数N转换成r进制的数
N N / 8 (整除) N % 8(求余)
1835 229 3 低
229 28 5
28 3 4
3 0 3 高