資料結構之棧實作

資料結構棧的實作——運用數組

Ps: 棧用類實作比較好，可以同時管理多種資料結構。不過對于剛剛接觸的我來說，就看着數，按着書上的流程走吧。我會盡力把棧的特點講解清楚，以後有了更深入的了解，我會再來補充的。

引例

逆波蘭表示法 是一種将運算符寫在操作數後面的描述程式（算式）的方法。舉個例子，我們平常用中綴表示法描述的算式（1+2）*（5+4），改為逆波蘭表示法之後則是1 2 + 5 4 - * 。相較于中綴表示法，逆波蘭法的優勢在于不需要括号。

請輸入以逆波蘭表示法輸入的算式的計算結果。

輸入	在一行中輸入1個算式。相鄰的符号（操作數或運算符）用一個空格符隔開
輸出	在1行之中輸出計算結果
限制	2 ≤ 算 式 中 操 作 數 的 總 數 ≤ 100 2\leq算式中操作數的總數\leq100 2≤算式中操作數的總數≤100、 1 ≤ 算 式 中 運 算 符 的 總 數 ≤ 99 1\leq算式中運算符的總數\leq99 1≤算式中運算符的總數≤99 運算符僅包含“+” “-” “ ∗ * ∗”, 操作數為 1 0 6 10^6 106以下的正整數。 − 1 ∗ 1 0 9 ≤ 計 算 過 程 中 的 值 ≤ 1 0 9 -1*10^9\leq計算過程中的值\leq10^9 −1∗109≤計算過程中的值≤109
輸入示例	1 2 + 3 4 - *
輸出示例	-3

用C++實作

#include<iostream>
#include<string>
#include<stdlib.h>
#define MAX 1000

using namespace std;

int a[MAX], top;


int pop();
void push(int x);

int main()
{
	int a, b;
	top = 0;
	char s[100];
	while (cin >> s)
	{
		if (s[0] == '+')
		{
			a = pop();
			b = pop();
			push(a + b);
		}
		else if (s[0] == '-')
		{
			b = pop();
			a = pop();
			push(a - b);
		}
		else if (s[0] == '*')
		{
			a = pop();
			b = pop();
			push(a * b);
		}
		else
		{
			push(atoi(s));
			//atoi函數将字元串形式的數字轉化為整形數字
		}
	}
	printf("%d\n", pop());
	return 0;
}

void push(int x)
{
	S[++top] = x;
}

int pop()
{
	top--;
	return S[top + 1];
}
           

問題分析

該程式用數組實作了棧，資料存在字元數組s中，每次循環将資料壓入“棧”S中，top作為棧頂指針，表示最後一個添加的元素儲存在S中的什麼位置。每一次循環中，如果遇到字元類型數字，将轉化為整形類型數字，top+1向後移位後将數字壓入棧中，如果遇到運算符，top-1将其後面的數字return，取出棧中的兩個元素進行運算。最終棧中剩下的數就是結果。

push（x）送來的元素在top+1後壓入棧中，pop()傳回top所指的元素後減1.

這隻是用數組簡單的實作棧，一個用數組實作的相對完整的棧應該包含如下一些的功能。

//使用數組實作棧的僞代碼
	initialize()   //initialize函數用來清空棧
		top = 0;
	isEmpty()     //isEmpty函數用來檢查top是否為0，判斷棧中是否有元素
		return top == 0;
	isFull()      //isFull函數用判斷棧中是否已滿
		return top >= MAX - 1;
	push(x)       
	/*push函數将top+1後将top所指位置加入元素，
	  并且每次判斷棧是否已滿*/
		if(isFull())
			錯誤(上溢)；
		top++;
		S[top] = x;

	pop()
	/*pop函數傳回top所指的元素，再将top-1
	  并且每次判斷棧是否為空*/
		if(isEmpty())
			錯誤(下溢)
		top--;
		return S[top+1]；
           

一般情況下，資料結構多以結構體或類的形式實作，以類的形式實作可以同時管理多種資料結構，友善程式調用資料。