数据结构与算法分析
栈模型
- 限制插入和删除只能在表的末端的表
- 表的末端叫做栈顶（top)
- 支持Push进栈和Pop入栈操作
- //LIFO后进先出表
栈的实现
链表实现
类型声明
struct Node ;
typedef struct Node *PtrToNode ;
typedef struct Node Stack
int IsEmpty(Stack S) ;
Stack CreateStack(void) ;
void DisposeStack(Stack S) ;
void MakeEmpty(Stack S) ;
void Push(ElementType X,Stack S) ;
ElementType Top(Stack S) ;
void Pop(Stack s) ;
struct Node
{
ElementType Element ;
PtrToNode Next ;
}
检测是否为空栈
void IsEmpty(Stack S)
{
return S->Next == NULL ;
}
创建空栈
Stack CreateStack(void)
{
Stack S ;
S = malloc(sizeof(struct Node)) ;
if(S == NULL)
{
FatalError("内存不足") ；
}
S->Next = NULL ;
MakeEmpty(S) ;
return S ;
}
void MakeEmpty(Stack S)
{
if(S == NULL)
{
Error("请先创建一个栈") ；
}
else
{
while(!IsEmpty(S)
Pop(S) ;
}
}
Push进栈
void Push(ElementType X, Stack S)
{
PtrToNode TmpCell ;
TmpCell = malloc(sizeof(struct Node)) ;
if(TmpCell == NULL)
FaltalError("内存不足") ；
else
{
TmpCell->Element = X ;
TmpCell->Next = S->Next ;
S->Next = TmpCell ;
}
}
返回top栈顶元素
ElementType Top(Stack S)
{
if(!IsEmpty(S)
return S->Next->ElementType ;
Error("空栈") ；
return 0 ;
}
Pop出栈
void Pop(Stack S)
{
PtrToNode FirstCell ;
FirstCell = S->Next ;
S->Next = FirstCell->Next ;
free(FirstCell) ;
}
数组实现
- 潜在危害：需要提前声明栈的大小
- 实现思路：
- 栈指针TopOfStack //并不是指针，只是指示下标
- 压栈Stack[TopOfStack] = x TopOfStack++ ;
- 出栈，TopOfStack-- ;
栈的声明
struct StackRecord ;
typedef struct StackRecord *Stack ;
int IsEmpty(Stack S) ;
Stack CreateStack(int MaxElements) ;
void DisposeStack(Stack S) ;
void MakeEmpty(Stack S) ;
void Push(ElementType X,Stack S) ;
ElementType Top(Stack S) ;
void Pop(Stack s) ;
define EmptyTOS(-1) ; //空栈标志 加#
define MinStackSize (5) ;
struct Node
{
ElementType *Array ;
int Capacity ;
int TopOfStack ;
}
栈的创建//数组实现
Stack CreateStack(int MaxElements)
{
Stack S ;
if(MaxElements < MinStackSize)
Error("栈过小") ；
S = malloc(sizeof(struct Node) ;
if(S == NULL)
FatalError("内存不足") ；
S->Array = malloc(sizeof(struct Node) * MaxElements) ;
if(S->Array = NULL)
FatalError("内存不足") ;
S->Capacity = MaxElements ;
MakeEmpty(S) ;
}
void MakeEmpty(Stack S)
{
S->TopOfStack = EmptyTOS ;
}
释放栈函数
void DisposeStack(Stack S)
{
if(S != NULL)
{
free(S->Array) ;
free(S) ;
}
}
检测空栈函数
void IsEmpty(Stack S)
{
return S->TopOfStack == EmptyTOS ;
}
释放栈函数
void Dispose(Stack S)
{
if(S != NULL)
{
free(S->Array) ;
free(S) ;
}
}
压栈函数
void Push(ElementType X, Stack S)
{
if(IsFull(S))
Error("栈满了") ;
else
S->Array[++S->TopOfStack] = X ;
}
返回栈顶函数
ElementType Top(Stack S)
{
if(!IsEmpty(S))
return S->Array[S->TopOfStack]
Error("空栈") ；
return 0 ;
}
出栈函数
void Pop(Stack S)
{
if(IsEmpty(S))
Error("空栈") ;
S->TopOfStack-- ;
}
栈的应用
- 平衡符号
- 后缀表达式
- 中缀表达式->后缀表达式
- 函数调用
队列模型
- Enqueue入队 在表的末端插入一个元素
- Dequeue出队 返回或者删除表的开头的元素
- FIFO先进先出
队列的实现
数组实现
注意问题：数组浪费为题
解决：循环数组
队列的类型声明
struct QueueRecord ;
typedef struct QueueRecord *Queue ;
int IsEmpty(Queue Q) ;
int IsFull(Queue Q) ;
Stack CreateQueue(int MaxElements) ;
void DisposeQueue Q(Queue Q) ;
void MakeEmpty(Queue Q) ;
void Enqueue(ElementType X,Queue Q) ;
ElementType Front(Queue Q) ;
void Dequeue(Queue Q) ;
ElementType FrontAndQueue(Queue Q) ;
#define MinQueueSize(5) ;
Struct QueueRecord
{
int capacity ;
int Front ;
int Rear ;
int Size ;
ElementType *Array ;
}
检测队列是否为空和构造空队列
void IsEmpty(Queue Q)
{
return Q->Size == 0 ;
}
void MakeEmpty(Queue Q)
{
Q->Size = 0 ;
Q->Front = 1 ;
Q->Rear = 0 ;
}
Eequeue入队函数
void Enqueue(ElementType X, Queue Q)
{
if(IsFull(Q)
Error("队列已满") ；
Q->Size++ ;
Q->Rear = Succ(Q->Rear,Q) ;
Q->Array[Q->Rear] = X ;
}
int Succ(int Value, Queue Q)
{
if(++Value == Q->Capacity)
Value = 0 ;
return Value ;
}
Dequeue出队函数
ElementType Dequeue(Queue Q)
{
ElementType Tmp ;
if(Q->Rear < Q->Front)
Error("队列为空") ；
Q->Size++ ;
Tmp = Q->Array[Q->Front] ;
Q->Front = Succ(Q->Front,Q) ;
return Tmp ;
}
总结
- 栈和队列都属于表的一种，只是支持更特殊的操作而已
- 且用途广泛