视频课堂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 个元素 。
so-kinsoku-overflow:1'>
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(); } //将结果字符串倒转 } } }
