數據結構與算法之七 棧

視頻課堂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小時內刪除侵權內容。