目錄

一：棧的介紹

1：什么是棧（Stack）？

2：棧的特點

3：棧的相關概念

1：基本概念

2：基本操作和圖示(如圖為順序棧實例)

4：棧的應用

三：棧的表示和操作實現

1：棧的抽象數據結構類型的定義

2：主要函數介紹

3.1 (重要)順序棧的表示和操作

1：了解順序棧

?2：特殊標志：棧空和棧滿

3：棧的數據類型定義和操作

四：棧的算法 利用

1：實現R進制轉換

2：實現后綴表達式（逆波蘭式）

---

---

一：棧的介紹

1：什么是棧（Stack）？

棧是一種常用的、重要的數據結構
棧是一種限定插入和刪除只能在表的 "端點”進行的線性表，此端點就在隊尾

如圖：只能在隊尾進行插入或刪除

2：棧的特點

后進先出LIFO

類比：洗碗盤子 子彈彈夾子彈出列

圖示：棧就好比一個這樣的特殊容器

?心中有圖 擼碼自然神

3：棧的相關概念

1：基本概念

1：表示

”表尾(即an端)稱為棧頂Top;表頭(即a端)稱為棧底Base

例如:棧s=(a1, a2, ....... an-1, an)
????????a1稱為棧底元素
????????an稱為棧頂元素
2.邏輯結構
與同線性表相同，仍為一一對應關系。
3.存儲結構
用順序棧和鏈棧存儲均可，但以順序棧更常見
4.運算規則
只能在棧頂運算，且訪問結點時依照后進先出(LIFO) 的原則。
5.實現方式
關鍵是編寫入棧和出棧函數，具體實現依順序棧或鏈棧的不同而不同。

2：基本操作和圖示(如圖為順序棧實例)

插入元素到棧頂(即表尾)的操作，稱為入棧。一般表示為壓入：PUSH (x)

從棧頂(即表尾)刪除最后一個元素的操作，稱為出棧。 一般表示為彈出：POP（X)

?

補：如圖：棧頂指針先指向最后一個元素（a3），再實現出棧操作? 概括為：e=*--S.top

4：棧的應用

■數制轉換??????????????????? ■行編輯程序
■函數調用??? ????????????????■迷宮求解
■遞歸調用的實?? ????????? ■表達式求值
■括號匹配的檢驗???????? ■八皇后問題

三：棧的表示和操作實現

1：棧的抽象數據結構類型的定義

補： 解釋圖中數據關系：ai-1是ai的前驅，ai是ai-1的后繼 |類比子彈入彈 ai-1先進入 ai后進入

2：主要函數介紹

Status InitStack(SqStack &S) 初始化棧
Status GetTopStack(SqStack S, ElemType &e) 獲取棧頂元素，參數e存放棧頂元素的值
Status PushStack(SqStack &S, ElemType e) 進棧，將元素e入棧
Status PopStack(SqStack &S, ElemType &e) 出棧，出棧的元素存放在參數e中
Status EmptyStack(SqStack S) 判斷棧是否為空
Status LengthStack(SqStack S) 獲取棧的實際長度
Status DestroyStack(SqStack &S) 銷毀棧
Status StackTraverse(SqStack S) 遍歷棧，打印每個元素

3.1 (重要)順序棧的表示和操作

1：了解順序棧

補：top指針 指向棧頂元素an的上一位的下標位置

??????????????????????????????????????????????????????????????????? stacksize:棧的最大容量

?2：特殊標志：棧空和棧滿

空棧：可以添加新元素，并且無法出棧（下溢）

棧滿（上溢）：無法添加新元素

????????????????解決：1報錯 2:開辟新空間

3：棧的數據類型定義和操作

1 順序棧的表示

#define stack_INIT_SIZE???? 100

?typedef struct {
?????? SElemType? *base;?? //棧底指針
?????? SElemType? *top;???? //棧頂指針
?????? int stacksize;?????? //棧空間 棧可用最大空間
}Sqstack;

理解：

2 順序棧的初始化

Status iniStack(Sqstack &S){
??? S.base = (SElemType*)malloc(stack_INIT_SIZE*sizeof(SElemType));

??? //S.base =new SElemType[stack_INIT_SIZE];
? ? if(!S.base) exit(OVERFLOW);
??? S.top =S.base;
??? S.stacksize=stack_INIT_SIZE;???????????? ?
}

如圖：初始化要點 1：棧空 top=base 2：top base 指針指向第一個元素 3：stacksize的賦值

補：判斷棧是否為空（如上圖）

//判棧空
bool Empty(SqStack S){
??? if(S.top == -1){
??????? return true;
??? }else{
??????? return false;
??? }
}

3 棧的長度

int StackLength( SqStack S){

????????return S.top - S.base;

}
?

4 清空棧

Status ClearStack(SqStack S) {

??????? if(S.base) S.top=S.base;

??????? return OK;

}

5 銷毀順序棧

Status DestroyStack(SqStack &S){

??????? if(S.base){

??????????????? delete S.base;

??????????????? S.stacksize = 0;

??????????????? S.top=S.base =NULL; ??????

????????}

??????? return OK;

}

銷毀順序棧：3步 結構體內部3個變量的值? 并釋放兩個指針空間的地址

6：順序棧入棧

順序棧入棧的步驟

1：是否棧滿（上溢），是不能添加新元素 => 2：元素e壓入棧頂 => 3：指針+1

Status push(Sqstack &S,SElemType e){
??? if(S.base-S.top==stacksize)
??????? return ERROR;
??? *S.top++=e;
??? return OK;
}

7 順序棧的出棧

順序棧出棧的步驟

1：是否棧空（下溢）=> 2：棧頂指針-1 => 3：取棧頂元素e值?

?Status pop(Sqstack &S,SElemType &e){
??? if(S.base==S.top)//等價 if(StackEmpty(S))
??????? return ERROR;
??? e=*--S.top;
??? return OK;
}

四：棧的算法 利用

1：實現R進制轉換

本題要求實現十進制轉R（R<10 && R>0）進制。

#include <stdio.h>
#include <malloc.h>
typedef int Status;
typedef int SElemType;
#define stack_INIT_SIZE???? 100
#define stackINCREMENT? 10
#define OK 1
#define ERROR 0
#define OVERFLOW -2
?typedef struct {
?????? SElemType? *base;?? //棧底指針
?????? SElemType? *top;???? //棧頂指針
?????? int stacksize;?????? //棧空間
}Sqstack;
Sqstack S;
Status iniStack(Sqstack &S);
Status push(Sqstack &S,SElemType x);
Status pop(Sqstack &S,SElemType &e);
void conversion(int n,int R);
int main()
{
??? int N,R;
??? scanf("%d",&N);? //輸入十進制數
??? scanf("%d",&R);? //輸入要轉換的進制
??? if(R<0||R>=10)? //判斷R是否合法
??? {
??????? printf("illegal input");
??????? return ERROR;
??? }
??? //printf("開始");
??? conversion(N,R);? //進制轉換
??? return OK;
}

/* 請在這里填寫答案 */

Status iniStack(Sqstack &S){
??? S.base = (SElemType*)malloc(stack_INIT_SIZE*sizeof(SElemType));
//?? ?if(!S.base) exit(OVERFLOW);
??? S.top =S.base;
??? S.stacksize=stack_INIT_SIZE;???????????? ?
}
Status push(Sqstack &S,SElemType x){
??? if(S.base-S.top==stack_INIT_SIZE)
??????? return ERROR;
??? *S.top++=x;
??? return OK;
}
Status pop(Sqstack &S,SElemType &e){
??? if(S.base==S.top)
??????? return ERROR;
??? e=*--S.top;
??? return OK;
}
bool StackEmpty(Sqstack &S)
{
?? ?if (S.top == S.base) return false;
?? ?return true;
}
void conversion(int n,int R){
?? ?int e;Sqstack S;
?? ?iniStack(S);
//?? ?printf("開始");
??? //printf("%d",n);
??? while(n>=R){
??????? push(S,n%R);
??????? n/=R;
??????? //printf("%d",n);
??? }
??? push(S,n);
?? // printf("push結束");
??? while(S.base!=S.top){
??????? pop(S,e);
??????? printf("%d",e);
??? }
}

2：實現后綴表達式（逆波蘭式）

在一行中輸入一個以回車結束的非空后綴表達式，回車不屬于表達式的一部分，操作數和運算符都以空格分隔，運算數為不超過100的正整數，運算符僅有+、-、*、/ 四種，題目保證輸入的是合法的后綴表達式形式。

#include <stdio.h>
#include <malloc.h>
#include <iostream>
using namespace std;
typedef int Status;
typedef int SElemType;
#define stack_INIT_SIZE???? 3000000
#define stackINCREMENT? 10
#define OK 1
#define ERROR 0
#define OVERFLOW -2
?typedef struct {
????? long long int? *base;?? //棧底指針
????? long long? int? *top;???? //棧頂指針
?????? int stacksize;?????? //棧空間
}Sqstack;
Sqstack S;
Status iniStack(Sqstack &S){
??? S.base = (long long int*)malloc(stack_INIT_SIZE*sizeof(long long int));
//?? ?if(!S.base) exit(OVERFLOW);
??? S.top =S.base;
??? S.stacksize=stack_INIT_SIZE;???????????? ?
}
Status push(Sqstack &S,long long int x){
??? if(S.base-S.top==stack_INIT_SIZE)
??????? return ERROR;
??? *S.top++=x;
??? return OK;
}
Status pop(Sqstack &S,long long int &e){
??? if(S.base==S.top)
??????? return ERROR;
??? e=*--S.top;
??? return OK;
}
bool StackEmpty(Sqstack &S)
{
?? ?if (S.top == S.base) return false;
?? ?return true;
}
void conversion(int n,int R){
?? ?long long int e;Sqstack S;
?? ?iniStack(S);
//?? ?printf("開始");
??? //printf("%d",n);
??? while(n>=R){
??????? push(S,n%R);
??????? n/=R;
??????? //printf("%d",n);
??? }
??? push(S,n);
?? // printf("push結束");
??? while(S.base!=S.top){
??????? pop(S,e);
??????? printf("%d",e);
??? }
}

int A(char* str)
{
??? int i = 0;
??? Sqstack Numbers;
??? iniStack(Numbers);
??? SElemType number_to_push;
?? ?long long int num1, num2;
??? while (str[i] != '\0') {
??????? if (str[i] != ' ') {
??????????? if (str[i] >= '0' && str[i] <= '9') {
??????????????? number_to_push = 0;
??????????????? while (str[i] != ' ' && str[i]) {
??????????????????? number_to_push = number_to_push * 10 + (str[i] - '0');
??????????????????? i++;
??????????????? }
??????????????? push(Numbers, number_to_push);
??????????? } else {
??????????????? pop(Numbers, num2);
??????????????? pop(Numbers, num1);
??????????????? switch (str[i]) {
??????????????? case '+': {
??????????????????? num1 += num2;
??????????????????? break;
??????????????? }
??????????????? case '-': {
??????????????????? num1 -= num2;
??????????????????? break;
??????????????? }
??????????????? case '*': {
??????????????????? num1 *= num2;
??????????????????? num1=num1%1000000007;
??????????????????? break;
??????????????? }
??????????????? case '/': {
??????????????????? num1 /= num2;
??????????????????? break;
??????????????? }
??????????????? case '%': {
??????????????????? num1 %= num2;
??????????????????? break;
??????????????? }
??????????????? }
??????????????? push(Numbers, num1%1000000007);
??????????? }
??????? }
??????? i++;
??? }
??? pop(Numbers, num1);
??? return num1;
}
int main(){
??????? Sqstack S;
??????? iniStack(S);
??????? int num1;
??????? char num[300000];
//?????? scanf("%s",&num);
?????? gets(num);
?? ??? ?//cin.getline(num,300000);
?????? printf("%s",num);
??????? num1=A(num);
??????? printf("%d",num1);
}

?? ?
?????? ?

總結

以上是生活随笔為你收集整理的(全网最细）顺序栈详解 ＋实例解析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。