数据结构:栈的基本概念、顺序栈、共享栈以及链栈

相关概念

栈(Stack)是只允许在一端进行插入或删除操作的线性表。
栈顶(Top):线性表允许插入删除的那一端。
栈底(Bottom):固定的,不允许进行插入和删除的另一端。

栈的基本操作

  • InitStack(&S):初始化一个空栈S。
  • StackEmpty(S):判断一个栈是否为空,若栈S为空则返回true,否则返回false。
  • Push(&S,x):进栈,若栈S未满,则将x加入使之成为新栈顶。
  • Pop(&S,&x):出栈,若栈S非空,则弹出栈顶元素,并用x返回。
  • GetTop(S,&x):读栈顶元素,但不出栈,若栈S非空,则用X返回栈顶元素。
  • DestoryStack(&S):销毁栈,并释放栈S所占用的存储空间。

栈的数学性质:当\(n\)个不同元素进栈时,出栈元素的不同排列的个数为\(C^n_{2n}/(n+1)\)。该公式称为卡特兰数(Catalan)公式,可采用数学归纳法证明。

顺序栈

采用顺序存储的栈称为顺序栈,它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时附设一个指针(top)指示当前栈顶元素的位置。

栈和队列的判空、判满条件,会因实际给的条件不同而变化;具体来说,有时候将空栈时栈顶指针初始化为-1,有时候将空栈时栈顶指针初始化为0.

#define MaxSize 50
typedef int Elemtype;

typedef struct {
	Elemtype data[MaxSize];
	int top;
} SqStack;


void InitStack(SqStack& S) {
	S.top = -1;
}

bool StackEmpty(SqStack S) {
	if (S.top = -1)
		return true;
	else
		return false;
}

bool Push(SqStack& S, Elemtype x) {
	if (S.top == MaxSize - 1)
		return false;
	S.data[++S.top] = x;
	return true;
}

bool Pop(SqStack& S, Elemtype& x) {
	if (S.top == -1)
		return false;
	x = S.data[S.top--];
	return true;
}

bool GetTop(SqStack& S, Elemtype& x) {
	if (S.top == -1)
		return false;
	x = S.data[S.top];
	return true;
}

共享栈

利用栈底位置相对不变的特性,可让两个顺序栈共享一个一维数组空间,将两个栈的栈底分别设置在共享空间的两端,两个栈底向共享空间的中间延伸。
两个栈的栈顶指针都指向栈顶元素,top=-1时0号栈为空,top=MaxSize时1号栈为空;仅当两个栈顶指针相邻(top1-top0=1)时,判断为栈满。

#define MaxSize 50
typedef int Elemtype;

typedef struct {
	Elemtype data[MaxSize];
	int top1;
	int top2;
} SqStack;


void InitStack(SqStack& S) {
	S.top1 = -1;
	S.top2 = MaxSize;
}

链栈

采用链式存储的栈称为链栈,链栈的优点是便于多个栈共享存储空间和提高其效率,且不存在栈满上溢的情况。通常采用单链表实现,并规定所有的操作都是在单链表的表头进行的。一般规定链栈没有头结点,Lhead指向栈顶元素。

添加头结点对链栈的实现没有帮助,因此一般不设置头结点。

#include <cstdlib>

typedef int Elemtype;

typedef struct LNode {
	Elemtype data;
	struct LNode* next;
} LNode, *LiStack;

void InitStack(LiStack& L) {
	L = (LNode*)malloc(sizeof(LNode));	// 创建头节点
	L->next = NULL;						// 头节点指向空
	return;
}

bool StackEmpty(LiStack L) {
	return L->next == NULL;
}

void Push(LiStack L, Elemtype x) {
	LNode* node = (LNode*)malloc(sizeof(LNode));
	node->data = x;
	node->next = L->next;
	L->next = node;
}

bool Pop(LiStack L, Elemtype& x) {
	if (L->next = NULL)
		return false;
	LNode* node = L->next;
	x = node->data;
	L->next = node->next;
	free(node);
	return true;
}

bool GetTop(LiStack L, Elemtype& x) {
	if (L->next = NULL)
		return false;
	x = L->next->data;
	return true;
}

热门相关:你是我生命的四分之三   呆萌配腹黑:倒追男神1000次   呆萌配腹黑:绝宠小冤家   呆萌小青梅:妖孽竹马太腹黑   我的全世界就是你