大话数据结构-4.6 栈的链式存储结构及实现 - 高飞网

4.6 栈的链式存储结构及实现

2016-12-21 14:32:21.0

4.6 栈的链式存储结构及实现

4.6.1 栈的链式存储结构

    栈只是在栈顶来做插入和删除操作,栈顶放在链表的头部还是尾部呢?由于单链表有头指针,而栈顶也是必须的,可以让它们合二为一。比较好的办法是把栈顶放在单链表的头部。

    链栈的结构代码如下:

/* 栈的链式存储结构--链栈 */

typedef int LElemType;
#define OK 1
#define ERROR 0
typedef int Status;

typedef struct LinkedStackNode
{
	LElemType data;
	struct LinkedStackNode *next;
}LinkedStackNode,*LinkedStackPtr;

typedef struct LinkedStack
{
	LinkedStackPtr top;
	int count;
}LinkedStack;

4.6.2 栈的链式存储结构——进栈操作

    如下图,将s结点追加到栈顶(链头),只要把s的next指针指向原来的top,将top指向现在的s即可


Status Push(LinkedStack *S,LElemType e)	//若栈S存在,将新元素e插入栈S中并成为栈顶元素
{
	LinkedStackPtr p = (LinkedStackPtr)malloc(sizeof(LinkedStackNode));
	p->data = e;
	p->next = S->top;
	S->top = p;
	S->count ++;
	return OK;
}

4.6.3 栈的链式存储结构——出栈操作

    栈顶上删除结点,只要把top指向当面top的next,然后将原来的top释放掉即可


Status Pop(LinkedStack *S,LElemType *e)	//删除栈S中栈顶元素,并用e返回其值
{
	if(StackEmpty(*S))
	{
		return ERROR;//为空
	}
	LinkedStackPtr p = S->top;
	*e = p->data;
	S->top = p->next;
	free(p);
	S->count --;

	return OK;
}

    链栈的插入和删除,没有任何循环操作,时间复杂度为O(1)。

    顺序栈与链栈的比较


顺序栈链栈
时间复杂度O(1)O(1)
长度固定
耗用空间大(额外内存保存指定)

4.7 栈的作用

    栈的引入简化了程序设计的问题,划分了关注层次,舍不得思考范围缩小,更加聚焦于要解决的问题核心。反之,像数组等,因为要分散精力去考虑数组的下标增减等细节问题,反而掩盖了问题的本质。