栈的定义与部分习题讲解_出栈入栈考题

栈

一、栈的定义

​ 栈是一种只能在一端进行插入和删除操作的线性表，表中只允许进行插入和删除操作的一端称为栈顶。栈顶的当前位置是动态的，栈顶的当前位置是由一个成为栈顶指针的位置指示器来指示。表的另一端称为栈底。当栈中没有元素时，称为空栈，栈的插入操作称为进栈或入栈，栈的删除操作称为出栈或退栈。

如下图时队元素的进栈和出栈操作：

二、栈的特点

​ 栈的主要特点是 “ 后进先出 ”，即后进栈的元素先出栈。栈也被称为后进先出表

三、栈的存储结构

栈有两种主要的存储结构，即顺序栈和链栈。前者采用顺序存储结构表示栈，后者采用链式存储结构表示栈。

1.顺序栈的存储

#define MAXSIZE 100
typedef int ElemType;
typedef struct
{
	ElemType data[MAXSIZE];		//存放栈中元素
	int top;					//栈顶指针
}SqStack;		//声明顺序栈类型
1
2
3
4
5
6
7

1.1顺序栈的结构示意图

1.2构成顺序栈的几个要素

	栈空条件：st.top==-1
	栈满条件：st.top==MAXSIZE-1
	元素进栈操作：st.top++;st.data[st.top]=x;
	出栈操作：x=st.data[st.top];st.top--;
1
2
3
4

2.链栈的存储

typedef int ElemType;
typedef struct linknode
{
	ElemType data;				//数据域
	struct linknode* next;		//指针域
}LiStack,*LST;			//声明链栈节点类型
1
2
3
4
5
6

2.1链栈的结构示意图

2.2构成链栈的几个要素

	栈空条件：lst->next==NULL
	栈满条件：通常不考虑栈满的情况
	节点p进栈操作：p->next=lst->next;lst->next=p
	出栈元素x的操作：p=lst->next;x=p->data;lst->next=p->next;free(p);
1
2
3
4

四、栈的基本运算

//初始化链栈
void InitLiStack(LST& lst);

//判断链栈是否为空
int LiStackEmpty(LiStack lst);

//进栈
void Push(LST& lst, ElemType x);

//出栈
int Pop(LST& lst, ElemType& x);

//取栈顶元素
int GetTop(LST& lst, ElemType& x);

//输入链栈的信息
void printStack(LST lst);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

五、栈的部分习题练习

1.设计一个算法，采用一个顺序栈判断单链表L中所有元素的正、反序是否相同

​ 解题思路：

​ 设置一个顺序栈st，先遍历单链表并将所有元素进栈，然后再次遍历单链表并同步退栈一个元素，若两者值相等，则循环，否则返回0.若单链表遍历结束仍没有返回0，则返回1.

算法入下：

//单链表的结构定义
typedef int ElemType;
typedef struct linknode
{
	ElemType data;				//数据域
	struct linknode* next;		//指针域
}LinkList;			//声明链栈节点类型

//判断单链表L中所有元素的正、反序是否相同
int Same(LinkList*L)
{
	ElemType x;
	struct node		//定义顺序栈
	{
		ElemType data[MaxSize];
		int top;			
	}st;
	st.top=-1;
	LinkList *p=L->next;
	while(p!=NULL)		//遍历单链表，将所有元素进栈
	{
		st.top++;
		st.data[st.top]=p->data;
		p=p->next;
	}
	p=L->next;
	while(p!=NULL)		//栈不空循环
	{
		x=st.data[st.top];		//出栈元素x
		st,top--;
		if(p->data!=x)		//当前单链表元素不等于x，返回0
			return 0;
		p=p->next;	
	}
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

本题类似求一个数组元素是否是一个回文数，如 1 2 3 3 2 1

2.假设表达式中允许包含圆括号，方括号和大括号3种括号，设计一个算法，采用顺序栈判断表达式中的括号是否正确匹配

解题思路：

​ 设置一个栈st，扫描表达式exp，遇到（ 、[ 、 { ,则进栈，遇到），若栈顶是（。则继续处理，否则表示括号不匹配，则返回0；遇到 ] ，若栈顶元素是 [ ，则继续处理，否则表示括号不匹配，则返回0；遇到 }，若栈顶元素是 { ，则继续处理，否则表示括号不匹配，则返回0；

​ 在exp扫描结束后，若栈不为空，表示不匹配，返回0；否则所有的括号匹配，返回1.

对应算法如下：

//判断表达式中的括号是否正确匹配
int Match(char exp[],int n)
{
	char st[MaxSize]；		//括号栈
	int to-1;			//栈顶指针
	int i=0,tag=1;
	while(i<n&&tag==1)
	{
		//遇到‘（’、‘[’或‘{’，则将其入栈
		if(exp[i]=='('||exp[i]=='['||exp[i]=='{')
		{
			top++;
			st[top]=exp[i];
		}
		if(exp[i]==')')		//遇到')',若栈顶是'(',则继续处理，否则不匹配
			if(top!=-1&&st[top]=='(')
				top--;
			else
				tag=0;
		if(exp[i]==']')		//遇到']',若栈顶是'[',则继续处理，否则不匹配
			if(top!=-1&&st[top]=='[')
				top--;
			else
				tag=0;
		if(exp[i]=='}')		//遇到'}',若栈顶是'{',则继续处理，否则不匹配
			if(top!=-1&&st[top]=='{')
				top--;
			else
				tag=0;
		i++;
	}
	if(top!=-1)
		tag=0
	return (tag);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

总结

​ 栈也是逻辑结构也是线性关系， 是一种运算受限的线性表 。他有两种存储结构分别是顺序栈和链栈

顺序栈是利用一组地址连续的存储单元存放自栈底到栈顶的元素，同时附设一个指针（top）指示当前栈顶的位置。

链栈是一种和单链表非常相似的存储结构，他不需要考虑栈满的情况，他在表头出栈，在表尾入栈。