Java教程

数据结构——栈

本文主要是介绍数据结构——栈,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

数据结构——栈

    • 1.栈的概念:
    • 2.栈的基本运算:
    • 3.基本操作的代码:
  • 栈的顺序存储结构
    • 顺序栈基本操作
      • 置空栈
      • 判空栈
      • 入栈
      • 出栈
      • 取栈顶元素
      • 注意事项
    • 多栈共享邻接空间
      • 共享栈的基本操作

1.栈的概念:

栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针。

栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为退栈(POP)。栈也称为后进先出表。

2.栈的基本运算:

1.InitStack(S)初始化:初始化一个新的栈。
2.Empty(S)栈的非空判断:若栈S不空,则返回TRUE;否则,返回FALSE。
3.Push(S,x)入栈:在栈S的顶部插入元素x,若栈满,则返回FALSE;否则,返回TRUE。
4.Pop(S)出栈: 若栈S不空,则返回栈顶元素,并从栈顶中删除该元素;否则,返回空元素NULL。
5.GetTop(S)取栈顶元素:若栈S不空,则返回栈顶元素;否则返回空元素NULL。
6.SetEmpty(S)置栈空操作:置栈S为空栈。
栈是一种特殊的线性表,因此栈可采用顺序存储结构存储,也可以使用链式存储结构存储。

3.基本操作的代码:

1.置空栈
首先建立栈的空间,然后初始化栈顶指针。

SeqStack * Linklist()
{
	SeqStack * s;
	s = (SeqStack *)malloc(sizeof(SeqStack));
	s -> top = -1;
	return s;
}

2.判空栈

int Empty(SeqStack *s)
{
	if (s -> top == -1)
	{
		return -1;
	}
	else
	return 0;
}

3.入栈

int  Push(SeqStack *s, ElemType x)
{
	if (s -> top == MAXSIZE - 1)
	{
		return 0; //栈满不能入栈 
	}
	else
	{
		s -> top++;
		s -> elem[s -> top] = x;
		return 1;
	}
}

4.出栈

int Pop(SeqStack  *s, ElemType *x)
{
	if (Empty(s))
	{
		return 0;//栈空不能出栈
	}
	else
	{
		* x = s -> elem[s -> top];//栈顶元素存入 *x,返回
		s -> top--;
		return 1;
	}
}

5.取栈顶元素

ElemType GetTop(SeqStack *s)
{
	if (Empty(s))
	{
		return 0;//栈空
	}
	else
	return (s -> elem[s - top]);
}

栈的顺序存储结构

利用顺序存储方式实现的栈称为顺序栈。类似于顺序表的定义,栈中的数据元素用一个预设的足够长度的一维数组来实现:datatype data[MAXSIZE],栈底位置可以设置在数组的任何一个端点,而栈顶是随着插入和删除而变化的,用一个int top来作为栈顶的指针,指明当前栈顶的位置,同样将data和top封装在一个结构中,顺序栈的类型描述如下:

#define MAXSIZE
typedef struct{
	datatype data[MAXSIZE];
	int top;
}SeaStack;

定义一个指向顺序栈的指针:

SeqStack* s;

通常0下标端设为栈底,这样空栈时栈顶指针top = -1;入栈时,栈顶指针加1,即s ->top++;出栈时,栈顶指针减1,即s ->top–。

顺序栈基本操作

置空栈

首先建立栈空间,然后初始化栈顶指针。

SeqStack* Init_SeqStack(){
	SeqStack* s;
	s = malloc(sizeof(SeqStack));
	s -> top = -1;
	return s;
}

判空栈

int Empty_SeqStack(SeqStack* s){
	if (s -> top == -1){
		return 1;
	}
	else
	return 0;
}

入栈

首先我们现需要判断栈是否满了,如果满了则无法进行入栈,如果没满则就入栈。

nt Push_SeqStack (SeqStack* s , datatype x){
	if (s->top = MAXSIZE - 1){
		return 0;
	}
	else
	s->top++;
	s->data[s->top] = x;
	return 1;
}

出栈

先进行判断,如果栈空就不能出栈,否则就进行出栈操作

int Pop_SeqStack (SeqStack* s , datatype x){
	if (Empty_SeqStack(s)){
		return ;
	}
	else{
		*x = s->data[s->top];
		s->top--;
		return 1;
	}
}

取栈顶元素

取栈顶元素和出栈操作一样,先判断栈是不是空栈,如果不是才能返回栈顶元素。

datatype Top_SeqStack(SeqStack* s){
	if (Empty_SeqStack(s)){
		return 0;
	}
	else
	return (s->data[s->top]);
}

注意事项

  1. 对于顺序栈,入栈时,首先判断栈是否满了,栈满的条件为:s->top == MAXSIZE - 1,栈满时,不能入栈;否则出现空间溢出,引起错误,这种现象称为上溢。
  2. 出栈和读栈顶元素操作,先判栈是否为空,为空时不能操作,否则引起错误。通常栈空时常作为一种控制转移的条件。
  3. 取栈顶元素与出栈的不同之处在于出栈操作改变栈顶指针top的位置(栈顶指针下移一个位置),而栈顶元素操作只是读出栈顶元素的值,栈顶指针top的位置不变。

多栈共享邻接空间

通常我们在创建一个程序的时候,常要用的多个栈,若采用顺序栈,会因为所需的栈空间的大小很难估计,产生有的栈溢出,有的栈还很空闲,若让多个栈共用一个足够大的连续存储空间,则可利用栈的动态特性使它们的存储空间互补,这就是栈的共享邻接空间。

栈的共享中最常见的是两栈的共享。假设两个栈共享一维数组stack[MAXNUM],则可以利用栈的“栈底位置不变,栈顶位置动态变化”的特性,两个栈底分别为-1和MAXNUM,而它们的栈顶都往中间方向延伸。因此,只要整个数组stack[MAXNUM]未被占满,无论哪个栈的入栈都不会发生上移。两栈共享的数据结构定义为:

typedef struct{
	Elemtype stack[MAXNUM];
	int lefttop;/*左栈栈顶位置指示器*/
	int righttop;/*右栈栈顶指示器*/
}dupsqstack;

在这里插入图片描述

共享栈的基本操作

1.初始化操作

int initDupStack(duosqstack* s){
	/*创建两个共享邻接空间的空栈由指针s指出*/
	if ((s == (dupsqstack*)malloc(sizeof(dupsqstack))) == NULL){
		return FALSE;	
	} 
	s->lefttop = -1;
	s->righttop = MAXNUM;
	return TRUE;
}

2.入栈操作

	if (s->lefttop + 1 == s->righttop){
		return FALSE;
	}
	if (status == 'L'){
		s->stack[++s->lefttop] == x;
	}
	else if (status == 'R'){
		s->stack[--s->lefttop] = x;
	}
	else{
		return FALSE;
	}
	return TRUE;
}

3.出栈操作

Elemtype popDupStack(dupsqstack* s , char status){
	/*从左栈(status = 'L')或右栈(status = 'R')退出栈顶元素*/
	if (status = 'L'){
		if (s->lefttop < 0){
			return NULL;
		}
		else
		return (s->stack[s->lefttop--]);
	} 
	else if (status == 'R'){
		if (s->righttop > MAXNUM - 1){
			return NULL;
		}
		else 
		return (s->stack[s->righttop++]);
	}
	else
	return NULL;
}

这篇关于数据结构——栈的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!