• 3.3 栈(Stack)ADT
  • 3.3.1 栈模型
  • 3.3.2 栈的实现
    • 栈的链表实现
    • 栈的数组实现
  • 3.3.3 应用

3.3 栈(Stack)ADT

3.3.1 栈模型

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫作栈的顶(top)。对栈的基本操作又Push（进栈）和Pop（出栈），前者相当于插入，后者相当于删除最后插入的元素。
栈模型中只有栈顶元素是可访问的/可见的。
栈又叫做LIFO(Last In First Out)。

3.3.2 栈的实现

下面给出两种流行的实现方法：使用指针/使用数组

栈的链表实现

栈ADT链表实现的类型声明：

#ifndef _Stack_h

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode 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 );

#endif /* _Stack_h */

/* Place in implementation file */
/* Stack implementation is a linked list with a header */
struct Node
{
	ElementType Element;
	PtrToNode Next;
}

具体函数实现：

/* Return true if S is empty */
int
IsEmpty( Stack S )
{
	return S->Next == NULL;
}

/* Create an empty stack */
Stack
CreateStack( void )
{
	Stack S;
	S = malloc( sizeof( struct Node ) );
	if( S == NULL )
		FatalError( "Out of space!!!" );
	S->Next == NULL;
	MakeEmpty( S );
	return S;
}

/* Dispose S */
void
DisposeStack( Stack S )
{
	MakeEmpty( S );
	free( S );
}

/* Make S empty*/
void
MakeEmpty( Stack S )
{
	if( S == NULL )
		Error( "Must use CreateStack first" );
	else
		while( !IsEmpty( S ) )
			Pop( S );
}

/* Push */
void
Push( ElementType X, Stack S )
{
	PtrToNode TmpCell;
	TmpCell = malloc( sizeof( struct Node ) );
	if( TmpCell == NULL)
		FatalError( "Out of space!!!" );
	else
	{
		TmpCell->Element = X;
		TmpCell->Next = S->Next;
		S->Next = TmpCell;
	}
}

/* Return the top element */
ElementType
Top( Stack S )
{
	if( !IsEmpty( S ) )
		return S->Next->Element;
	Error( "Empty stack");
	return 0;
}

/* Pop */
void
Pop( Stack S )
{
	PtrToNode FirstCell;
	if( IsEmpty( S ) )
		Error( "Empty stack" );
	else
	{
		FirstCell = S->Next;
		S->Next = S->Next->Next;
		free( FirstCell );
	}
}

缺点：对malloc和free的调用的开销是昂贵的。
经常性的使用第二个栈，当一个单元从第一个栈弹出时，被推入第二个栈中，此后当第一个栈需要新的单元时，它首先去检查第二个栈。

栈的数组实现

潜在危害：需要提前声明一个数组的大小
优点：实现简单，所有ADT操作以非常快的常数时间运行。（在带有自增和自减寻址功能的寄存器上操作，整数的Push和Pop都可以写成一条机器指令）
注意：（在错误处理极其重要的场合）应该随时编写错误检测的代码防止越界。（这将导致效率大大降低，所以一般通过声明一个栈大到不至于使得操作溢出，来省去错误检测）

栈ADT数组实现的类型声明：

#ifndef _Stack_h

struct StackRecord;
typedef struct StackRecord *Stack;

int IsEmpty( Stack S );
int IsFull( 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 );
ElementType TopAndPop( Stack S );

#endif /* _Stack_h */

/* Place in implementation file */
/* Stack implementation is a dynamically allocated array */
#define EmptyTOS ( -1 )
#define MinStackSize ( 5 )

struct StackRecord
{
	int Capacity;
	int TopOfStack;
	ElementType *Array;
}

具体函数实现：

/* Return true if S is empty */
int
IsEmpty( Stack S )
{
	return S->TopOfStack == EmptyTOS;
}

/* Return true if S is full */
int
IsFull( Stack S )
{
	return S->TopOfStack == S->Capacity - 1;
}

/* Create an empty stack */
Stack
CreateStack( int MaxElements )
{
	Stack S;
	if( MaxElements < MinStackSize )
		Error( "Stack size is too small" );
	S = malloc( sizeof( struct StackRecord ) );
	if( S == NULL )
		FatalError( "Out of space!!!" );
	S->Array == malloc( sizeof( ElementType ) * MaxElements );
	if( S->Array == NULL)
		FatalError( "Out of space!!!" );
	S->Capacity = MaxElements;
	MakeEmpty( S );
	return S;
}

/* Dispose S */
void
DisposeStack( Stack S )
{
	if( S!= NULL )
	{
		free( S->Array );
		free( S );
	}
}

/* Make S empty */
void
MakeEmpty( Stack S )
{
	S->TopOfStack = EmptyTOS;
}

/* Push */
void
Push( ElementType X, Stack S)
{
	if( IsFull( S ) )
		Error( "Full stack" );
	else
		S->Array[ ++S->TopOfStack ] = X;
}

/* Return the top element */
ElementType
Top( Stack S )
{
	if( !IsEmpty( S ) )
		return S->Array[ S->TopOfStack ];
	Error( "Empty stack ");
	return 0;
}

/* Pop */
void
Pop( Stack S )
{
	if( IsEmpty( S ) )
		Error( "Empty stack" );
	else
		S->TopOfStack--;
}

/* Return the top element and Pop */
ElementType
TopAndPop( Stack S )
{
	if( !IsEmpty( S ) )
		return S->Array[ S->TopOfStack-- ];
	Error( "Empty stack ");
	return 0;
}

3.3.3 应用

• 平衡符号
• 后缀(postfix)/逆波兰(reverse Polish)表达式
• 中缀(infix)到后缀的转换
• 函数调用

尾递归(tail recursion)，是使用递归极端不当的例子，尽量避免使用。