数据结构与算法之七 栈

视频课堂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 leftStack = new Stack();

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 stack = new Stack();

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 resultStack;

public Form1()

{

InitializeComponent();

}

private void btnRemove_Click(object sender, EventArgs e)

{

char removeChar;

Stack middleStack = new Stack();

if (resultStack == null)

{

resultStack = new Stack();

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();

}

//将结果字符串倒转

}

}

}

数据结构

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。