【数据结构与算法】栈的介绍及基本运算（出栈、入栈、销毁栈等）_栈的基本运算

一、栈的介绍
栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。
允许插入和删除运算的一端称作栈顶（top）。
不允许插入和删除的另一端称作栈底（bottom）。
在栈顶进行的插入操作称为入栈或进栈(push)
在栈顶进行的删除操作称为出栈或退栈(pop)
栈的特点：后进先出，即 LIFO(Last In First Out)
如下图：

顺序栈的数据类型
静态分配：

#define MaxSize 100
#define int ElemType 
typedef struct
{ ElemType data[MaxSize]; // 数组存储空间
  int top;   //栈顶下标
} SqStack;  // 顺序栈数据类型
1
2
3
4
5
6

MaxSize为顺序栈的最大容量；
top为栈顶元素的下标，0 <= top <= MaxSize-1
栈空：top = -1;
栈满：top = MaxSize-1

注意栈空和栈满的判断条件，如上图，栈顶top = 0 时，有数据元素a1，所以top = -1时，才能判断栈空。栈满时，由上图看知。

动态分配：

#define int ElemType 
typedef struct
{ 
  ElemType *base;  //栈底的指针
  ElemType *top;   //栈顶的指针
} SqStack;  // 顺序栈数据类型
1
2
3
4
5
6

链式栈的数据型

typedef struct LNode
{
  ElemType data;      //数据域
  struct LNode *next; //后继结点指针
} LinkStNode;         //链栈结点类型
1
2
3
4
5

S：单链表头指针，指向头结点。
栈顶：单链表第一个元素结点的位置，即头结点的后一个位置。

二、顺序栈的基本运算
1、初始化栈
建立一个新的空栈s，实际上是将栈顶指示变量置-1即可。

//初始化空顺序栈
int InitStack(SqStack &S)
{
	S.top = -1;
	return 1;
}
1
2
3
4
5
6

2、入栈：
①判断栈是否已满，若满则产生上溢出错误，退出算法，否则执行第②步；
②栈顶下标增一（top++），指向新的栈顶位置；
③将新元素置于栈顶。

//item是需要入栈的数据元素
bool Push(SqStack &S, ElemType item)
{
  if (S.top == MaxSize - 1)
  {
    cout << "栈满" << endl;
    return false;
  }
  S.top++;
  S.data[S.top] = item;
  return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

3、出栈：
①判断栈是否为空，若空则产生下溢出错误，退出算法，否则执行第②步；
②栈顶元素出栈；
③栈顶下标减一（top++），指向新的栈顶位置；

bool Pop(SqStack &S, ElemType &item)
{
  if (S.top == -1)
  {
    cout << "栈空" << endl;
    return false;
  }
  item = S.data[S.top];
  S.top--;
  return true;
}
1
2
3
4
5
6
7
8
9
10
11

4、判断栈是否为空
栈S为空的条件是s.top==-1。

//判栈空
int StackEmpty(SqStack &S)
{
	if(S.top==-1)
		return 1;
	else
		return 0;
}
1
2
3
4
5
6
7
8

5、取栈顶元素
在栈不为空的条件下，将栈顶元素赋给e。

//取栈顶
int GetTop(SqStack &S, DataType &e)
{
    if(S.top <= -1)
    {
         cout<<"栈空"<<endl;
         return 0;
    }
   item=S.items[S.top];
   return 1;
}
1
2
3
4
5
6
7
8
9
10
11

注意：
取栈顶元素和出栈不同，取栈顶元素只是把栈顶元素复制一份，栈顶指针并没有改变。如下图：

入栈时要判断栈是否满，出栈时要判断是否为空。

三、链式栈的基本运算
1、初始化栈
建立一个空栈s。实际上是创建链栈的头结点，并将其next域置为NULL。

void (SNode *&s)
{      
	s=(SNode *)malloc(sizeof(SNode));//s=new SNode;
    s->next=NULL;
}
1
2
3
4
5

2、入栈：

bool Push(LinkStNode *S, ElemType item)
{ //带头结点单链表的表头插入法
  LinkStNode *t = new LinkStNode; //①生成新结点
  if (t == NULL)
  {
    cout << "内存不足";
    return false;
  }
  t->data = item;
  //②在栈顶插入新结点
  t->next = S->next;
  S->next = t; //③
  return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3、出栈：

bool Pop(LinkStNode *S, ElemType &item)
{ //删除单链表的第一个元素结点
  //①判断栈是否为空
  if (S->next == NULL)
  {
    cout << "栈空";
    return false;
  }
  //②删除栈顶元素
  LinkStNode *t = S->next;
  S->next = t->next;
  item = t->data;
  delete t;
  return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4、销毁栈

//释放链栈
void Destroy(SNode *&s)
{
	SNode *p;
	while(s!=NULL)
	{
		p=s;
		s=s->next;
		delete p;
	}
}
1
2
3
4
5
6
7
8
9
10
11

5、判断栈是否为空
栈S为空的条件是s->next==NULL，即单链表中没有数据结点。

//判栈空
int StackEmpty(SNode *s)
{
	if(s->next==NULL)
		return 1;
	else
		return 0;
}
1
2
3
4
5
6
7
8

6、取栈顶元素

int GetTop(SNode *s，DataType &e)
{      
	if (s->next==NULL)	//栈空的情况
	{
		return 0;
	}
    e=s->next->data;
    return 1;
}
1
2
3
4
5
6
7
8
9