当前位置：首页 > 百科大全 > 正文内容

栈的概念与基本操作（详解）（c语言）

admin2周前 (05-26)百科大全20

栈的概念与基本操作（详解）（c语言）

[id_[id_1951212200]041599946]id_1428770756]

栈是一种受约束的线性表，即特殊的线性表。

栈又称为堆栈。

具体而言，栈是一种具有特定性质的线性数据结构在带链的栈中,栈顶指针的动态变化，它仅允许在序列的一端进行元素的插入和移除操作。

栈是一种先入后出，后入先出的结构。

为了详细的表示栈，我找了个图。

在图中展示的序列中，各个元素按照a1、a2、……、an的顺序逐一被加入，而在进行出栈操作时栈的概念与基本操作（详解）（c语言），an元素将首先被移除，而a1元素则最后被取出，从而实现了先进后出、后进先出的操作原则。

栈的基本操作

栈只能在一段（即栈顶，top）进行插入和删除操作。

表的另一端叫做栈底。

当栈中没有元素叫做空栈。

插入数据叫入栈（push）。

栈的插入操作称为进栈或入栈。

删除数据叫出栈（pop）。

栈的删除操作称为出栈或退栈。

一个简单直观的方法是将栈通过数组来构建。这种方法引出了我们接下来要介绍的栈的第一种基本结构——顺序栈。

## 顺序栈

顺序栈的定义涉及一种存储方式，即通过连续的存储空间来按顺序存放数据元素，从栈底至栈顶依次排列。鉴于栈的运作机制要求在栈顶进行元素的添加与移除，因此在带链的栈中,栈顶指针的动态变化，在顺序栈中必须设立一个位置指针，即栈顶指针top在带链的栈中,栈顶指针的动态变化，以实时反映栈顶元素在顺序栈中的具体位置。

栈的存储结构通常包括一个一维数组以及一个用于标识栈顶元素所在位置的变量。

顺序栈的结构

# define maxsize 100
typedef struct stack
{
	element data[maxsize];
	int top;
}stack,*pstack;

顺序栈的基本操作

1.初始化

void initstack(pstack s)
{
	s->top=-1;
}

数组下标是从0开始的，top最初要指向-1.

2.入栈

void push(pstack s,element x)
{
	if(s->top==maxsize-1)\\进栈要判断栈满
	{
		printf("栈满\n");
		return;
	}
	else
	{
		s->data[++(s->top)]=x;
		return;
	}
}

3.出栈

element pop(pstack s)
{
	if(s->top==-1)\\出栈要判断是否栈空
	{
		printf("栈空\n")；
		return ERROR; 
	 } 
	else
	{
		return s->data[(s->top)--];
	}
}

双端栈

双端栈技术涉及将数组一分为二栈的概念与基本操作（详解）（c语言），分别作为两个栈的底部，通过从数组的两端向中间添加元素来最大化地使用数组空间。这一方法巧妙地运用了栈的基本属性，即栈底位置保持不变，而栈顶位置则会随着元素的进出而动态调整。

在两端各设置一个栈顶指针，分别标记为top1和top2，它们分别指向左右两侧填充内容的末尾元素。

若左右两侧的栈中元素数量存在差异，那么判定栈是否已满的标准是（以左栈的栈顶指针为top1，右栈的栈顶指针为top2为例），即top2与top1之间的差值为1。（这表示两个栈顶指针已相遇。）

双端栈的结构

# define maxsize 100
typedef struct stack
{
	element data[maxsize];
	int top1;
	int top2;
}stack,*pstack;

1.初始化

void initstack(pstack s)
{
	s->top1=-1;
	s->top2=maxsize;
}

若数组索引范围从0至maxsize，那么最初两个栈顶指针分别指向-1和maxsize，以此表明栈处于空状态。

2.进栈

void push(pstack s,element x,int a)
{
	if(s->top2-s->top1==1)\\两位置指针相遇则栈满
	{
		printf("栈满\n");
		return; 
	}
	if(a==1)
	{
		s->data[++(s->top1)]=x;
	}
	else if(a==2)
	{
		s->data[--(s->top2)]=x;
	}
}

3.出栈

element pop(pstack s,int a)
{
	if(a==1)\\确定是对左边进行出栈
	{
		if(s->top1==-1)
		{
			printf("栈空");
			return ERROE;
		}
		else
		{
			return s->data[(s->top1)--];
		}
	}
	else if(a==2)\\确定是对右边进行出栈
	{
		if(s->top2==maxsize)
		{
			printf("栈空");
			return ERROE;
		}
		else
		{
			return s->data[(s->top2)++];
		}
	}	
}

栈的结构可以通过数组来实现存储，与此类似，我们也可以采用单向链表的方式来对栈进行存储。

##链栈

链栈实质上是一种基于单链表的存储方式，其结构特征与单链表相似。在链栈中，所有的插入与删除动作均需在栈顶进行。

单项链表具有两个端点，若以链表头部作为栈顶进行插入和删除操作较为便捷，而以链表尾部作为栈顶进行插入同样方便，然而一旦进行删除操作，整个链表便会消失，此时便无法通过当前节点访问到前一个节点。

因此对于链栈，链表的头作为链栈的栈顶。

链栈的结构

typedef struct stack
{
	element data;
	struct stack *next;
}stack,*pstack;

1.构建一个栈的头结点（不带元素）

pstack creatstack()
{
	pstack s;
	s=(pstack)malloc(sizeof(stack));
	s->next=NULL;
	return s;
}

2.入栈（单链表的头插法）

void push(element x,pstack s)
{由于栈与数组不同，它并没有固定的内存容量，因此在进行入栈操作时，无需对内存是否已满进行判断，即可直接调用可用内存空间。
	pstack p=(pstack)malloc(sizeof(stack));
	p->data=x;
	p->next=s->next;
	s->next=p;
}

3.出栈（删除并返回栈顶元素）

element pop(pstack s)
{
	pstack p;
	element a;
	if(s->next==NULL)
	{
		printf("栈空");
		return NULL; 
	}
	else
	{
		p=s->next;
		s->next=p->next;
		a=p->data;
		free(p);
		return a;
	}
}