数据结构与算法之七 栈
【摘要】
视频课堂https://edu.csdn.net/course/play/7621
目标
在本章中
,
你将学到
:
识别栈的特性
实施栈
运用栈来解决编程问题
...
在本章中 , 你将学到 :
识别栈的特性
实施栈
运用栈来解决编程问题
什么是栈？
栈就是一个只能访问其末尾数据的数据结构，这一端也叫做顶部。
数据仅能在顶部进行插入和删除操作。
最新插入的数据将被最先删除。
因此，栈也被称为后进先出数据结构（ Last-In-First-Out ）。
下列两个基本操作可用于栈上：
PUSH （推） : 入栈
POP （出） : 出栈
PUSH ：它是在栈顶部插入新元素的过程。
POP ：它是从栈顶部删除元素的过程。
现实生活中一些基于 LIFO 原则的实例。
答案：
一堆书籍 ：假设有一堆叠在一起的书籍。当你想取出一本书籍时，必须先取出 上面的其他书籍。类似地，当你放入另一本书时，将会放在这堆书籍的顶部。
一堆盘子 ：第一个盘子放在最底部，然后第二个盘子放在第一个盘子上边，第 三个盘子则放在第二个盘子上边，依此类推。一般来说，如果你想在这堆盘子 上再添加新的盘子，你必须得把新盘子放在顶部。类似地，如果你要移走一个 盘子，也必须先移走顶部的盘子。
手上的手镯 ：当一个人戴着手镯时，只能先取下最后戴上的手镯。
实施栈
你需要开发一个方法以检查算术表达式中的圆括号是否正确被嵌套。
你如何解决此问题？
你可以通过使用栈很容易地解决此问题。
考虑一个示例。
假定表达式为：
{(a + b) × (c + d) + (c × d)]}
从左到右检查此表达式。
第一个检查到的条目是 ‘ { ’ ，它是一个左括号。
将它添加到栈中。
栈与只允许在一端进行添加或删除操作的列表类似。
因此，类似与列表，栈可以使用数组和链接列表来实现。
要使用数组来实现栈：
声明一个数组：
int Stack[5]; // 需要预先定义最大大小
声明一个变量来容纳栈中顶部数据的索引：
int top;
最初，当栈为空时，设置：
top = – 1
要避免栈溢出，你需要在向栈中添加元素前检查栈是否已满。
让我们修改此算法以检查此状况。
问题描述：
编写一个程序来通过使用数组实现一个栈，要求这个栈能容纳 5 个元素 。
-
using System;
-
using System.Collections.Generic;
-
using System.ComponentModel;
-
using System.Data;
-
using System.Drawing;
-
using System.Text;
-
using System.Windows.Forms;
-
-
namespace 检查括号是否匹配
-
{
-
public partial class Form1 : Form
-
{
-
public Form1()
-
{
-
InitializeComponent();
-
}
-
-
private void button1_Click(object sender, EventArgs e)
-
{
-
string expression;
-
Stack<char> leftStack = new Stack<char>();
-
-
expression = txtExpression.Text.Trim();
-
-
//bool isRight = true;
-
char c;
-
for (int i = 0; i < expression.Length; i++)
-
{
-
c = expression[i];
-
-
//如果是左括号
-
if (IsLeft(c))
-
{
-
leftStack.Push(c);
-
}
-
else if (IsRight(c))//如果是右括号
-
{
-
//如果栈为空，表明有多余的右括号
-
if (leftStack.Count == 0)
-
{
-
txtResult.Text = "表达式错误：有多余的右括号" + c.ToString();
-
//isRight = false;
-
//break;
-
return;
-
}
-
else if (IsPiPei(leftStack.Peek(), c))
-
//判断取出的右括号是否与栈顶的左括号匹配
-
{
-
leftStack.Pop();
-
}
-
else
-
{
-
txtResult.Text = "表达式错误：右括号"
-
+ c.ToString() + "与左括号"
-
+ leftStack.Peek().ToString()
-
+ "不匹配";
-
//isRight = false;
-
//break;
-
return;
-
}
-
}
-
}
-
-
if (leftStack.Count == 0) //&& isRight==true)
-
{
-
txtResult.Text = "表达式正确";
-
}
-
else
-
{
-
txtResult.Text = "表达式错误：有多余的左括号";
-
}
-
-
}
-
-
//判断传入的字符是否是左括号
-
bool IsLeft(char c)
-
{
-
if (c == '(' || c == '{' || c == '[')
-
{
-
return true;
-
}
-
else
-
{
-
return false;
-
}
-
}
-
-
//判断传入的字符是否是右括号
-
bool IsRight(char c)
-
{
-
if (c == ')' || c == '}' || c == ']')
-
{
-
return true;
-
}
-
else
-
{
-
return false;
-
}
-
}
-
-
//判断传入的左右括号是否匹配
-
bool IsPiPei(char left, char right)
-
{
-
//首先需要验证left为左括号，right为右括号
-
if (IsLeft(left) && IsRight(right))
-
{
-
if (left == '(' && right == ')' ||
-
left == '{' && right == '}' ||
-
left == '[' && right == ']'
-
)
-
{
-
return true;
-
}
-
else
-
{
-
return false;
-
}
-
-
}
-
else
-
{
-
throw new Exception("left应该为左括号，right应该为右括号");
-
}
-
}
-
}
-
}
-
using System;
-
using System.Collections.Generic;
-
using System.ComponentModel;
-
using System.Data;
-
using System.Drawing;
-
using System.Text;
-
using System.Windows.Forms;
-
-
namespace 多进制转换
-
{
-
public partial class Form1 : Form
-
{
-
public Form1()
-
{
-
InitializeComponent();
-
}
-
-
private void btnTransform_Click(object sender, EventArgs e)
-
{
-
string digitChar = "0123456789ABCDEF";
-
int number;//存放10进制的数
-
int d;//存放进制数
-
Stack<char> stack = new Stack<char>();
-
string result = null; //存放转换后的结果
-
-
number = Int32.Parse(txtNumber.Text);
-
d = Int32.Parse(txtD.Text);
-
-
//第一步：将转换结果的每一位数放入栈中
-
do
-
{
-
stack.Push(digitChar[number % d]);
-
number = number / d;
-
-
} while (number != 0);
-
-
//第二步：将栈中存放的每一位数出栈，并添加到结果字符串末尾
-
while (stack.Count != 0)
-
{
-
result = result + stack.Pop();
-
}
-
-
txtResult.Text = result;
-
}
-
}
-
}
-
using System;
-
using System.Collections.Generic;
-
using System.ComponentModel;
-
using System.Data;
-
using System.Drawing;
-
using System.Text;
-
using System.Windows.Forms;
-
-
namespace 移除火车车厢
-
{
-
public partial class Form1 : Form
-
{
-
Stack<char> resultStack;
-
public Form1()
-
{
-
InitializeComponent();
-
}
-
-
private void btnRemove_Click(object sender, EventArgs e)
-
{
-
char removeChar;
-
Stack<char> middleStack = new Stack<char>();
-
if (resultStack == null)
-
{
-
resultStack = new Stack<char>();
-
resultStack.Push('A');
-
resultStack.Push('B');
-
resultStack.Push('C');
-
resultStack.Push('D');
-
resultStack.Push('E');
-
}
-
-
removeChar = txtRemove.Text[0];
-
-
while (resultStack.Count != 0)
-
{
-
//如果要移除的编号等于栈顶元素的编号
-
if (removeChar == resultStack.Peek())
-
{
-
resultStack.Pop();
-
break;
-
}
-
else//如果要移除的编号不等于栈顶元素的编号
-
{
-
//将结果栈的栈顶元素出栈，并且将此元素放入中间栈中
-
middleStack.Push(resultStack.Pop());
-
}
-
}
-
-
while (middleStack.Count != 0)
-
{
-
resultStack.Push(middleStack.Pop());
-
}
-
-
txtTrain.Text = "";
-
foreach (char c in resultStack)
-
{
-
txtTrain.Text = txtTrain.Text + c.ToString();
-
}
-
-
//将结果字符串倒转
-
}
-
}
-
}
文章来源: aaaedu.blog.csdn.net，作者：tea_year，版权归原作者所有，如需转载，请联系作者。
原文链接：aaaedu.blog.csdn.net/article/details/51637559
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）