分享内容

  1. 栈的概念
  2. 栈的实现
  3. 栈的应用

什么是数据结构

在计算机世界里,数据结构是一种组织和存储数据的方法,帮助我们更高效地管理数据,就像用不同的工具(比如数组、链表、树、图等)把数据安排得井井有条,这样我们就能更快地找到需要的信息,或者对数据进行各种操作,比如添加、删除、排序等。简单来说,数据结构就是让数据变得有条理,方便我们更好地使用它们。

栈的概念

我们将这里的圆盘和盘子替换为各种类型的元素(如整数、字符、对象等),就得到了栈这种数据结构。
汉诺塔中依次插入圆盘1、2、3,取出的时候,只能先取出3,再取出2,最后取出1。

类似情况是桌面上的一摞盘子,最后放上去的盘子必须是第一个被取走的。
● 这种“叠盘子”状态的数据结构就是栈。

● 栈(stack)是一种常用的线性数据结构。

● 栈的修改与访问遵循“先进后出”的原则。

●即,最后进入栈的元素最先被取出。
这种独特的方式让栈在编程中有很多重要的应用。
在这里插入图片描述
栈中堆叠元素的顶部称为“栈顶”,底部称为“栈底”。
当栈中没有数据元素时,称为“空栈”。
● 把指定元素添加到栈顶的操作叫作“入栈”。
● 删除栈顶元素的操作叫作“出栈”。
在这里插入图片描述

栈的操作

1)4、9、5、2依次“入栈”后,请问栈底的元素值是?栈顶的元素值是?
在这里插入图片描述
2)做两次“出栈”操作,依次得到哪两个值?
出栈序列:2、5
3)再做两次“出栈”操作,出栈序列是?
出栈序列:

2

5

9

4
倒序
3)已知有如下元素:9、5、3、2,按以下步骤进行操作后,出栈序列是?

出栈序列:5 9 3 2

操作:

  1. 数值9入栈
  2. 数值5入栈
  3. 出栈
  4. 出栈
  5. 数值3入栈,马上出栈
  6. 数值2入栈,马上出栈
    栈的操作是可以出栈、入栈交替进行的,所以出栈序列并不一定都是倒序!

栈的典型应用

浏览器中的后退与前进、软件中的撤销与反撤销

  1. 栈可以用来存储浏览器的浏览历史,按后退按键,可以回到前一次的浏览位置。
  2. 在实现一个简单的文本编辑器的撤销功能时,栈可以用来存储用户的操作历史,因为最新的操作需要最先被撤销。

程序内存管理
每次调用函数时,系统都会在栈顶添加一个栈帧,用于记录函数的上下文信息。在递归函数中,向下递推阶段会不断执行入栈操作,而向上回溯阶段则会不断执行出栈操作。

栈的实现

为了深入了解栈的运行机制,我们来尝试自己实现一个栈

● 一般使用数组存储栈的数据
●同时需要一个变量记录栈顶元素的位置
● 在数组上实现栈的常用操作
· push(x):将x压入栈
·pop():把栈顶的元素出栈
· top():查询栈顶的元素(不出栈)
· 其他常用的功能…
例如,实现一个最多可以存放6个整型元素的栈

● 定义一个数组

所以数组长度定义为6+1

int stack[7] = {0};

想象成是一个横向放置的栈
在这里插入图片描述
● 定义一个变量记录栈顶元素的位置

初始时,栈顶没有元素,p指向无效位置0
● 在数组上实现栈的常用操作

①入栈操作:void push(int x)
在这里插入图片描述

把2入栈:
p++;
stack[p]=2;

把4入栈:
p++;
stack[p]=4;

新入栈元素总放在栈顶
x的数据类型与栈元素类型一致

void push (int x) {
	if(p<6){//还没满
		p++;
		stack[p] = x;

	}

}

②出栈操作(把栈顶元素出栈):int pop()
在这里插入图片描述
进行两次出栈:
非空(p>0)时:
p --;
p == 0时:
p不变;

返回值类型与栈元素类型一致

int pop() {
	if(p>0){
		int x = stack [p] ;
		p --;
		return x;
	}
	cout << "Stack is empty";
	return -1;
}
x=pop ();// x得到2
x=pop();// x得到-1(无效值)

③查询栈顶元素:int top()
在这里插入图片描述
非空(p>0)时:stack[p]就是栈顶

(注意】top()操作后栈内容不变
返回值类型与栈元素类型一致

int top() {
	if(p >0)
		return stack [p];
	cout << "Stack is empty";
	return -1;

}

x=top(); //x得到2

也可以添加一些其他功能函数,比如询问栈是否为空,一次性清空栈, ...

● 询问栈是否为空:

bool empty(){//询问栈是否为空
	return p == 0 ? true: false;

}

●一次性清空栈:

void clear(){// 清空栈
	p=0;//只需要设p为0

}

栈基本操作

输入5个整数,将这5个整数依次进行入栈,接下来做三次出栈操作,并按
照出栈顺序输出出栈元素。以上操作完成后输出此时的栈顶元素。
【输入格式】输入5个整数,用空格隔开。(1≤整数≤1000)
【输出格式】输出2行,第1行输出出栈元素,按照出栈顺序输出,用空格
隔开。第2行输出完成出栈操作后的栈顶元素。
【输入样例】4 912 6 7
【输出样例】7 6 12
9

1.完成栈的实现

1 栈的初始化(数组、栈顶下标)
2 入栈函数 push()
3 出栈函数 pop()
4 查询栈顶元素 top()

2.完成主程序功能

1输入5个整数并依次入栈
2做三次出栈操作,并输出出栈元素
3输出此时的栈顶元素

定义模拟栈结构的数组和变量 (整数类型,数据长度是5)

#define MAXN
int stack[MAXN+1]={0};//栈数据存储在下标1~MAXN
int p=0;//栈顶元素的下标。初始为0

②.push函数



void push (int x) {
	if( 还没满 ){
		p++;
		stack[p] = x;
	}
}

在这里插入图片描述
③pop函数

int pop() {
	if不是空的{
	
		int x = stack [p] ;
		
		p --;
		
		return x;
		}
		cout << "Stack is empty";
		return -1;
}

④查询栈顶元素top函数

int top() {
	if不是空的
		return stack [p];
	cout << "Stack is empty";
	return -1;
}

完整代码

#include<iostream>
using namespace std;

#define MAXN 5
int stack[MAXN+1]={0};//栈数据存储在下标1~MAXN
int p=0;//栈顶元素的下标。初始(栈空的时候)为0

bool isEmpty(){//询问栈是否为空
	return p == 0 ? true: false;
}
	void push (int x) { // xt
		if(p<MAXN){//还没满
			p++;
			stack [p] = x;
	}
}
int pop(){//出栈
	if(!isEmpty ()) {
		int x = stack [p] ;
		p --;
		return x;
	}
	cout << "Stack is empty";
	return -1;
}	
int top(){//查看栈顶元素
	if(!isEmpty())
		return stack [p] ;
	cout << "Stack is empty";
	return -1;
}
int main() {
	int x;
	for(int i = 1;i <= 5;i++) {
		cin >> x;
		push (x) ;
	}
	for(int i = 1;i <= 3;i++) {
		cout << pop() << '';
	}
	cout << endl;
	cout << top() << '';
	return 0;
}

【思考】如果栈的数据从数组下标0开始放,代码如何调整?

小括号匹配

输入一个由左右小括号’(’、')‘构成的字符串。要求小括号需要成对出现,且必须是先左括号后右括号,即)(不是正确的格式。即(())或(()())等为正确的格式,(()或())或(((均为不正确的格式。给定一串括号输入(换行作为结束符),检测格式是否正确,若正确输出YES,错误输出NO。(字符串长度≤100)
【输入样例1】
(()())
【输出样例1】
YES
【输入样例2】
（))
【输出样例2】
NO
在这里插入图片描述
在这里插入图片描述

格式验证的步骤总结

  1. 遍历字符串
    ①当前为左括号,入栈;
    ②当前为右括号:
    · 如果栈空,输出NO;比如)(())这种情况
    · 如果非空(栈中必定有一个左括号),可匹配,栈顶出栈;
    只有左括号会入栈,所以栈或者为空,或者都是左括号。
    · 当遍历到右括号时,只要栈不为空,说明必然有一个左括号可以和当前右括号匹配。
  2. 当所有括号都处理完了,最后再次判断
    · 如果栈空:输出YES;
    · 如果非空:输出NO;比如((())这种情况

实现栈的数据结构

①定义模拟栈结构的数组和变量

1.本题栈需要保存的数值是字符类型
2. 栈的长度为100

#define MAXN
char stack[MAXN+1]={0};//栈数据存储在下标1~MAXN
int p=0;//栈顶元素的下标。初始为0

②push函数



void push (char x) {
	if (p < MAXN) {
		p++;
		stack[p] = x;
	}
}

实现栈的数据结构

③ pop函数

char pop () {
	if( p>0){
	int x = stack[p];
	p --;
	return x;
	}
	cout << "Stack is empty";
	return -1;

}

④ top函数

char top() {
	if( p>0)
		return stack [p];
	
	cout << "Stack is empty";
	return -1;
	
}

实现主程序的流程



1定义数组和变量
char a[MAXN]={0};// 存放字符串,默认从下标0开始放
int len;// 有效长度

2读入字符串,获取长度

cin >> a;
len = strlen (a) ;

调用strlen()需要 include<cstring>

在这里插入图片描述

4 遍历完成后,如果栈空,输出YES,否则输出NO

if (p == 0) // 栈为空
	cout << "YES";
else
	cout << "NO";

例如,((())这种情况

  1. 前三个左括号依次入栈
  2. 出现一个右括号匹配栈顶,出栈一个左括号
  3. 还有一个右括号匹配栈顶,出栈一个左括号
  4. 最后栈还没清空,说明字符串是不正确的格式

完整代码

#include<iostream>
#include<cstring>
using namespace std;

#define MAXN 100
char stack[MAXN+1]={0};//栈数据存储在下标1~MAXN
int p=0;//栈顶元素的下标。初始(栈空的时候)为0

bool isEmpty(){//询问栈是否为空
	return p == 0 ? true:false;
}
void push (char x) { // xAtl
	if(p<MAXN){//还没满
		p++;
		stack [p] = x;
	}
}
char pop(){ // Ht€
	if(!isEmpty()) {
		int x = stack [p];
		p --;
		return x;
	}
	cout << "Stack is empty";
	return -1;
}
char top(){//查看栈顶元素
	if(!isEmpty())
		return stack [p];
	cout << "Stack is empty";
	return -1;
}
int main () {
	char a[MAXN]={0};// 字符串
	int len;
	
	cin >> a;
	len = strlen (a) ;
	
	// 遍历字符串,进行小括号匹配
	for(int i=0; i <len; i++) {
		if (a[i] == '('){//左括号入栈
		push (a[i]) ;
		}else{// 右括号进行匹配
		//栈不为空,说明必然有一个左括号可以和当前右括号匹配,栈顶可以出栈
		// 栈空,则无法匹配
		if (!isEmpty ()) {
			pop();
		} else {
			cout << "NO";
			return 0;
			}
		}
	}
	if (isEmpty ())
		cout << "YES";
	else//((()这种情况,遍历完成后栈还没清空
		cout << "NO";
	return 0;
}

在这里插入图片描述

合法出栈序列

给定一个由不同小写字母构成的长度不超过8的字符串x,现在要将该字符串的每个字符依次压入栈中,然后再全部弹出。要求左边的字符一定比右边的字符先入栈,出栈顺序无要求。再给定若干字符串,对每个字符串,判断其是否是可能的x中的字符的出栈序列。
【输入描述】第一行是原始字符串x和整数n(0<n<10),后面有n行,每行一个字符串,字符串长度与x长度相同。
【输出描述】对除第一行以外的每个字符串,判断其是否是可能的出栈序列。如果是,输出“YES",否则,输出"NO"。（用栈结构判断序列的合法性）
在这里插入图片描述

首先需要实现栈的数据结构

栈的实现类似前面的两个练习,举一反三即可
1.本题栈需要保存的数值是字符类型
2. 需要的栈的最大长度为8
3. 本题需要实现的栈函数有:
①入栈函数push()
② 出栈函数pop()
③ 查询栈顶元素top()
④ 清空函数clear()
⑤ 查询栈是否为空的函数empty()

实现主程序的流程

1定义数组和变量

char in[MAXN]={0},out[MAXN]={0};// in数组:原始序列,out数组:出栈序列
int n, len;// n:出栈序列个数 len:序列长度

2读入原始序列和n,获取序列长度

cin >> in >> n;
len = strlen (in) ;



调用 strlen()需要 include<cstring>

3读入并判断n个出栈序列是否合法

for(int i=1;i <= n; i++) {
	cin >>out;// 1、读入一个出栈序列
	clear();// 2、先做一次栈清空,避免前一个序列的数据影响这一次的验证
	3、验证out序列是否合法
}

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
###验证out序列是否合法:代码示例

int out_index = 0;// out[]中当前要匹配的元素下标
for(int in index = 0; in index < len; in index++) {
	push (in[in index]);
	while(! empty () && out [out index] == top() ) {//好习惯:在调用top()或pop()之前务必通过empty()检测,确保栈是非空的。除非题目保证不会有非法操作。
		pop ();
		out index++;// 当前位置已匹配,移动到下一个
	}
}
// out_index指向最后一个元素的下一个,说明out的所有值都完成了匹配,
// 这是一个合法的出栈序列,否则是一个非法的序列
if (out index == len)
	cout << "YES" << endl;

else

	cout << "NO" << endl;

完整代码

#include<iostream>
#include<cstring>
using namespace std;

#define MAXN 8
char stack[MAXN+1]={0};//栈数据存储在下标1~MAXN
int p=0;//栈顶元素的下标。初始(栈空的时候)为0

bool empty(){//询问栈是否为空
	return p == 0 ? true: false;
}
void clear(){ // 清空栈
	p = 0;
}	
void push (char x) { // xAtl
	if(p<MAXN){//还没满
		p++;
		stack [p] = x;
	}
}
char pop () // tt
	if(!empty ()) {
		int x = stack [p] ;
		p --;
		return x;
	}
	cout << "Stack is empty";
	return -1;
}
char top(){//查看栈顶元素
	if(!empty ())
		return stack [p] ;
	cout << "Stack is empty";
	return -1;
}
int main(){
	char in[MAXN]={0},out[MAXN]={0};//in数组:原始序列,out数组:出栈序列
	int n, len;// len:序列长度(字符个数)
	cin >> in >> n;
	len = strlen (in) ;
	
	//判断个出栈序列是否合法
	for(int i=1;i <= n;i++) {
		cin >>out;//读入出栈序列
		clear();//先做一次栈清空
		//模拟入栈和出栈操作来验证给定的出栈序列是否合理
		int out index = 0;
		for(int in_index=0;in_index<len; in_index++) {
			push (in[in_index]) ;
			while(!empty () && out [out_index] == top()) {
				pop();
				out_index++;//当前位置已匹配,移动到下一个
		}
	}
	// out_index指向最后一个元素的下一个,说明out的所有值都完成了匹配,
	// 这是一个合法的出栈序列,否则是一个非法的序列
	if (out_index == len)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
	}
	return 0;
}

本次课程的知识点

  1. 栈的现实场景和概念
  2. 栈的操作
  3. 栈的实现
  4. 栈的应用
    1、今有一空栈S,对下列待进栈的数据a、b、c、d、e、f依次进行:进栈、
    进栈、出栈、进栈、进栈、出栈的操作,则此操作完成后,栈顶元素为?D

A、e

B、d

C、a

D、c
2、对于入栈顺序为a,b,c,d,e的序列,下列哪个不是合法的出栈序列?D

A, a,b,c,d,e

C, b,a,c,d,e

B, e,d,c,b,a

D. c,d,a,e,b
在这里插入图片描述

逆序数字游戏

某小鱼最近被要求参加一个数字游戏,要求它把看到的一串数字a1、a2、a3…an-1、an,
反着念出来。如:1、2、3,反着念为:3、2、1。这对鱼的记忆力来说实在是太难了,
所以请你帮小鱼编程解决这个问题。(此题请用栈来实现)
【输入格式】第一行输入一个整数n(1<n<10)。第二行输入n个数字,以空格间隔。
【输出格式】一行内倒序输出n个数字,以空格间隔。
【输入样例】

7

3 65 23 5 34 1 30

【输出样例】
30 1 34 5 23 65 3

#include<iostream>
using namespace std;

#define MAXN 10
int stack[MAXN+1]={0};//栈数据存储在下标1~MAXN
int p=0;//栈顶元素的下标。初始(栈空的时候)为0

bool empty(){//询问栈是否为空
	return p == 0 ? true: false;
}	
void push (int x) { // xAtl
	if(p<MAXN){//还没满
		p++;
		stack [p] = x;
	}
}
int pop() // tte
	if(!empty ()) {
		int x = stack [p];
		p --;
		return x;
	}
	cout << "Stack is empty";
	return -1;
}
lint top(){// 查看栈顶元素
	if(!empty())
		return stack [p];
	cout << "Stack is empty";
	return -1;
}
int main() {
	int n=0, num=0;
	cin >> n;
	//输入并入栈
	for (int i=0;i<n;i++) {
		cin >> num;
		push (num) ; //0
	}
	//出栈并输出
	while(!empty()){//判断栈不为空
		cout << pop() << " ";
	}
	return 0;
}
# c++ # 算法
Logo
亚马逊云科技技术品牌专区

更多推荐

cover

别再只聊大模型！AI的下一场革命，藏在“身体”里

avatar 亚马逊云科技技术品牌专区
cover

别再只聊大模型！人工智能的下一场革命，藏在“身体”里

avatar 亚马逊云科技技术品牌专区
cover

别再只聊大模型！AI的下一场革命，藏在“身体”里

avatar 亚马逊云科技技术品牌专区