前言
1.堆疊
- （1）順序堆疊
- - 1.堆疊的結構定義
  - 2.元素訪問
  - 3.初始化堆疊
  - 4.判斷堆疊是否為空
  - 5.清空堆疊
  - 6.計算堆疊中元素的個數
  - 7.獲得堆疊頂元素
  - 8.進堆疊操作Push
  - 9.出堆疊操作Pop
  - 10.遍歷堆疊中元素并進行列印
  - 11.順序堆疊完整代碼示例
  - 順序堆疊測驗結果
- (2)鏈堆疊
- - 1.//鏈堆疊的抽象資料型別定義
  - 2.//初始化鏈堆疊
  - 3.//入堆疊操作 Push
  - 4.//出堆疊操作 Pop
  - 5.//得到堆疊頂
  - 6.//遍歷列印堆疊中元素
  - 7.//回傳堆疊的長度
  - 8.//清空鏈堆疊中的元素
  - 9.鏈堆疊完整代碼示例
  - 10.鏈堆疊運行結果

前言

我們之前已經學習過線性表，堆疊（stack）和佇列（queue）也屬于線性表，只不過他們兩個都是特殊的線性表；

堆疊和佇列是特殊的線性表，除它兩的特殊點之外，其余操作和特性都與普通線性表相似，在學習堆疊和佇列之前，我們可以先復習線性表

傳送門—>線性表的順序儲存結構.
傳送門—>線性表的鏈式儲存結構.

1.堆疊

堆疊（stack）是僅限在表尾進行插入和洗掉操作的線性表，可分為順序堆疊和鏈堆疊

（1）順序堆疊

在這里插入圖片描述

顧名思義，順序堆疊就是線性表的順序儲存結構，只不過他的插入和洗掉只能在表尾進行；

我們吧允許進行插入和洗掉的一端稱為堆疊頂（top），另一端稱為堆疊底（base）不含任何資料元素的堆疊稱為空堆疊

1.堆疊的結構定義

#include<stdio.h>
#include<stdbool.h>					//bool（布爾型別的頭檔案） 
#define stacksize 200				//定義陣列大小為20
typedef bool Status;			//表示狀態 
typedef int Elemtype;		//int型別別名

typedef struct {
	Elemtype data[stacksize];			//資料域 
	Elemtype top;						//堆疊頂指標 
}My_Stack;

2.元素訪問

void visit(Elemtype e)			//訪問堆疊中的元素 
{
	printf("%d ", e);
}

3.初始化堆疊

Status initstack(My_Stack *s)			//初始化堆疊 
{
	//這里沒有給data申請空間建應該是因為陣列的大小已經定義完成 
	s -> top = -1;	
	return true;
}

4.判斷堆疊是否為空

Status stackempty(My_Stack s)			//判斷堆疊是否為空 
{
	if(s.top == -1)
		return true;
	else 
		return false;
}

5.清空堆疊

Status ClearStack(My_Stack *s) 		//將堆疊清空 
{ 
        s -> top = -1;
        return true;
}

6.計算堆疊中元素的個數

Elemtype length(My_Stack s)		//計算堆疊中元素的個數 
{
	return s.top + 1;
}

7.獲得堆疊頂元素

Status getTop(My_Stack s, Elemtype *e)	//獲得堆疊頂元素 
{
	if(s.top == -1)
		return false;
	else
		*e = s.data[s.top];
	return true;
}

8.進堆疊操作Push

Status push(My_Stack *s, Elemtype e)			//元素e入堆疊 
{
	if(s -> top == stacksize - 1)
		return false;
	else
	{
		s -> top++;				//堆疊頂指標加一 
		s -> data[s -> top] = e;		//將新元素賦給堆疊頂元素，新插入的元素進堆疊 ， 
		return true;
	 } 
}

沒有涉及回圈陳述句，時間復雜度為O(1)

9.出堆疊操作Pop

Status pop(My_Stack *s, Elemtype *e)		//堆疊頂元素出堆疊 
{
	if(s -> top == -1)
		return false;
	else
	{
		*e = s -> data[s -> top];
		s -> top--;			//堆疊頂指標減一 
		return true;
	}
}
}

沒有涉及回圈陳述句，時間復雜度為O(1)

10.遍歷堆疊中元素并進行列印

Status traverse(My_Stack s)		//遍歷堆疊中元素并進行列印 
{
	int i = 0;
	while(i <= s.top)			 
		visit(s.data[i++]);
	printf("\n");
}

11.順序堆疊完整代碼示例

#include<stdio.h>

#include<stdbool.h>					//bool（布爾型別的頭檔案） 

#define stacksize 200				//定義陣列大小為20

typedef bool Status;			//表示狀態 

typedef int Elemtype;		//int型別別名

typedef struct 
{
	Elemtype data[stacksize];			//資料域 
	
	Elemtype top;						//堆疊頂指標 
	
}My_Stack;				

void visit(Elemtype e)			//訪問堆疊中的元素 
{
	printf("%d ", e);
}

Status initstack(My_Stack *s)			//初始化堆疊 
{
	//這里沒有給data申請空間建應該是因為陣列的大小已經定義完成 
	s -> top = -1;	
	return true;
}

Status stackempty(My_Stack s)			//判斷堆疊是否為空 
{
	if(s.top == -1)
		return true;
	else 
		return false;
} 

Status ClearStack(My_Stack *s) 		//將堆疊清空 
{ 
        s -> top = -1;
        return true;
}

Elemtype length(My_Stack s)		//計算堆疊中元素的個數 
{
	return s.top + 1;
}

Status getTop(My_Stack s, Elemtype *e)	//獲得堆疊頂元素 
{
	if(s.top == -1)
		return false;
	else
		*e = s.data[s.top];
	return true;
}

Status push(My_Stack *s, Elemtype e)			//元素e入堆疊 
{
	if(s -> top == stacksize - 1)
		return false;
	else
	{
		s -> top++;				//堆疊頂指標加一 
		s -> data[s -> top] = e;		//將新元素賦給堆疊頂元素，新插入的元素進堆疊 ， 
		return true;
	 } 
}

Status traverse(My_Stack s)		//遍歷堆疊中元素并進行列印 
{
	int i = 0;
	while(i <= s.top)			 
		visit(s.data[i++]);
	printf("\n");
	return true;
} 

Status pop(My_Stack *s, Elemtype *e)		//堆疊頂元素出堆疊 
{
	if(s -> top == -1)
		return false;
	else
	{
		*e = s -> data[s -> top];
		s -> top--;			//堆疊頂指標減一 
		return true;
	}
}

int main()
{
	My_Stack s;				
	
	int j, e;
	
	initstack(&s);

	for(j = 1;j <= 150;j+=10)
		push(&s, j);
			
	puts("進堆疊之后的元素依次為： ");
	
	traverse(s);
	
	pop(&s, &e); 
	
	printf("\n");
	
	printf("彈出的堆疊頂元素為 %d \n\n", e);
	
	if(stackempty(s))
	{
		printf("彈出堆疊頂元素之后的堆疊變為空\n\n");
	}
	else
	{
		printf("彈出堆疊頂元素之后的堆疊不為空\n\n");
	}
    getTop(s, &e);//獲取堆疊頂元素 
    
    printf("堆疊頂元素 TopElem = %d 堆疊的長度為 %d \n\n", e, length(s));
    
    printf("進行清空堆疊操作"); 
    
	ClearStack(&s);//清空堆疊 
	
	if(stackempty(s))
	{ 
		printf("清空堆疊后，堆疊空\n\n");
	}
	else 
	{
		printf("清空堆疊后，堆疊不空\n\n"); 
	}
	return 0;
}

順序堆疊測驗結果

在這里插入圖片描述

(2)鏈堆疊

顧名思義，鏈堆疊就是線性表的鏈式儲存結構
與鏈表的操作相似

1.//鏈堆疊的抽象資料型別定義

#define OK 1
#define ERROR 0
using namespace std; 
typedef int Status;
typedef int ElemType;
//鏈堆疊的抽象資料型別定義 
typedef struct StackNode
{
	 ElemType data;
	 
	struct StackNode *next;
	
}StackNode, *LinkStack;

2.//初始化鏈堆疊

Status InitStack(LinkStack &S)
{
	//構造一個空堆疊，堆疊頂指標置為空 
	S = NULL;
	return OK;
}

3.//入堆疊操作 Push

Status Push(LinkStack &S,ElemType e)
{
	    LinkStack p;//定義p 
	    //這里使用的是C++語法new出的地址，也可使用C語言的語法malloc
		p=(LinkStack)malloc(sizeof(StackNode)); //需要包含malloc頭檔案 
		//	p=new StackNode;//生成新結點 
		
		p->data=e;//e賦給新結點的資料域 
		
		p->next=S; //新結點插入堆疊頂 
		
		S=p;//修改堆疊頂指標為p
		
		return OK;
}

4.//出堆疊操作 Pop

Status Pop(LinkStack &S,ElemType &e)
{
	LinkStack p;//定義p 
	
	if(S==NULL) return ERROR;//堆疊空 
	
	e=S->data;//將堆疊頂元素賦給e 
	
	p=S;//p臨時保存堆疊頂元素以備釋放 
	
	S=S->next;//修改堆疊頂指標 
	
	free(p);//釋放空間 
	
	return OK;
}

5.//得到堆疊頂

ElemType GetTop(LinkStack S)
{
	
	if(S!=NULL) //堆疊非空
	 return S->data; 
}

6.//遍歷列印堆疊中元素

 ElemType GetElem(LinkStack S)
 {
 	LinkStack p=S;//定義一個指標p； 
	 while(p)//p不斷向堆疊尾移動
	 {
	 	cout<<p->data<<" ";
	 	p=p->next;
	  } 
	  cout<<endl;
 }

7.//回傳堆疊的長度

 int StackLen(LinkStack S)
 {
 	int len=0;
 	LinkStack p=S;
	 while(p)
	 {
	 	len++;
	 	p=p->next;
	  } 
	  return len;
  }

8.//清空鏈堆疊中的元素

 Status StackClear(LinkStack &S)
 {
 	LinkStack p=S;//定義一個指標p； 
	 while(p)//p不斷向堆疊尾移動，S=p，釋放S 
	 {
	 	p=p->next;
	 	free(S);
	 	S=p;
	  } 
	  return OK;
 }

9.鏈堆疊完整代碼示例

#include<iostream>

#include<malloc.h>

#define OK 1
#define ERROR 0
using namespace std; 
typedef int Status;
typedef int ElemType;
//鏈堆疊的抽象資料型別定義 
typedef struct StackNode
{
	 ElemType data;
	 
	struct StackNode *next;
	
}StackNode, *LinkStack; 
//初始化鏈堆疊 
Status InitStack(LinkStack &S)
{
	//構造一個空堆疊，堆疊頂指標置為空 
	S = NULL;
	return OK;
}
//入堆疊操作 
Status Push(LinkStack &S,ElemType e)
{
	    LinkStack p;//定義p 
	    //這里使用的是C++語法new出的地址，也可使用C語言的語法malloc
		p=(LinkStack)malloc(sizeof(StackNode)); //需要包含malloc頭檔案 
		//	p=new StackNode;//生成新結點 
		
		p->data=e;//e賦給新結點的資料域 
		
		p->next=S; //新結點插入堆疊頂 
		
		S=p;//修改堆疊頂指標為p
		
		return OK;
}
//出堆疊操作 
Status Pop(LinkStack &S,ElemType &e)
{
	LinkStack p;//定義p 
	
	if(S==NULL) return ERROR;//堆疊空 
	
	e=S->data;//將堆疊頂元素賦給e 
	
	p=S;//p臨時保存堆疊頂元素以備釋放 
	
	S=S->next;//修改堆疊頂指標 
	
	delete p;//釋放空間 
	
	return OK;
} 
//得到堆疊頂 
ElemType GetTop(LinkStack S)
{
	
	if(S!=NULL) //堆疊非空
	 return S->data; 
	 return 0;
}  
//遍歷堆疊中元素
 ElemType GetElem(LinkStack S)
 {
 	LinkStack p=S;//定義一個指標p； 
	 while(p)
	 {
	 	cout<<p->data<<" ";
	 	p=p->next;
	  } 
	  cout<<endl;
	  return OK;
 }
 //回傳堆疊的長度
 int StackLen(LinkStack S)
 {
 	int len=0;
 	LinkStack p=S;
	 while(p)
	 {
	 	len++;
	 	p=p->next;
	  } 
	  return len;
  } 
 //清空鏈堆疊中的元素 
 Status StackClear(LinkStack &S)
 {
 	LinkStack p=S;//定義一個指標p； 
	 while(p)//p不斷向堆疊尾移動，S=p，釋放S 
	 {
	 	p=p->next;
	 	free(S);
	 	S=p;
	  } 
	  return OK;
 }
int main()
{
	LinkStack S; 
	
	ElemType e; 
	
	InitStack(S); 
	
	cout<<"進行入堆疊操作"<<endl;
	
	cout<<endl; 
	
	for(int i=1;i<150;i+=10)
	{
		Push(S,i);//入堆疊 
	 } 
	 cout<<"此時的堆疊頂為: "<<GetTop(S)<<endl;
	 cout<<endl;
	 
	 cout<<"由堆疊頂到堆疊底遍歷堆疊中元素"<<endl ;
	 
	GetElem(S);
	cout<<endl;
	
	cout<<"此時堆疊的長度為"<<StackLen(S)<<endl ;
	cout<<endl; 
	
	Pop(S,e);
	
	cout<<"Pop后的堆疊頂為: "<<GetTop(S)<<endl;
	 cout<<endl;
	 
	 cout<<"Pop后由堆疊頂到堆疊底遍歷堆疊中元素"<<endl ;
	GetElem(S);
	cout<<endl;
	
	cout<<"此時堆疊的長度為"<<StackLen(S)<<endl<<endl; 
	cout<<"清空堆疊操作"<<endl; 
	
	StackClear(S);
	cout<<"此時堆疊的長度為"<<StackLen(S)<<endl ;
	return 0;
}

10.鏈堆疊運行結果

在這里插入圖片描述

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/400559.html

標籤：其他

上一篇：Python資料結構：BF演算法、匹配括號、回文鏈表、生成螺旋矩陣、移除串列元素、計算后綴運算式的值、順時針旋轉n維矩陣90度、折半查找

下一篇：鏈表取節點尾插力扣刷題（新年第一篇博客）

疫情封校，在宿舍學習資料結構——堆疊(Stack)詳解(實體代碼&&各介面代碼）

目錄

前言

1.堆疊

（1）順序堆疊

1.堆疊的結構定義

2.元素訪問

3.初始化堆疊

4.判斷堆疊是否為空

5.清空堆疊

6.計算堆疊中元素的個數

7.獲得堆疊頂元素

8.進堆疊操作Push

9.出堆疊操作Pop

10.遍歷堆疊中元素并進行列印

11.順序堆疊完整代碼示例

順序堆疊測驗結果

(2)鏈堆疊

1.//鏈堆疊的抽象資料型別定義

2.//初始化鏈堆疊

3.//入堆疊操作 Push

4.//出堆疊操作 Pop

5.//得到堆疊頂

6.//遍歷列印堆疊中元素

7.//回傳堆疊的長度

8.//清空鏈堆疊中的元素

9.鏈堆疊完整代碼示例

10.鏈堆疊運行結果