【數據結構入門】棧(Stack)的實現(定義、銷毀、入棧、出棧等) | 圖解數據結構,超詳細哦~

CodeWinter 2022-01-08 00:58:14 阅读数:847

stack

數據結構系列文章:

【數據結構入門】順序錶(SeqList)詳解(初始化、增、删、查、改)

【數據結構入門】無頭單向非循環鏈錶(SList)詳解(定義、增、删、查、改) | 圖解鏈錶,超生動詳細哦~

【數據結構入門】帶頭雙向循環鏈錶(List)詳解(定義、增、删、查、改) | 配有大量圖解,超詳細哦~

【數據結構入門】順序錶和鏈錶的區別,以及啥是緩存利用率

(1)前言

1)棧的概念

:是一種特殊的線性錶,其只允許在錶尾進行插入和删除元素操作。進行數據插入和删除操作的一端稱為棧頂,另一端稱為棧底。棧中的數據元素遵守後進先出LIFO(Last In First Out)的原則。

壓棧:棧的插入操作叫做進棧 / 壓棧 / 入棧,入數據在棧頂

出棧:棧的删除操作叫做出棧。出數據也在棧頂

image-20210910230852363

2)進棧出棧的形式

棧對線性錶的插入和删除的比特置做了限制,並沒有對元素進出的時間進行限制,所以,在不是所有元素都進棧的情况下,事先進去的元素也可以出棧,只要保證是棧頂元素出棧就可以。

所以棧是:一種入棧順序,多種出棧順序

比如:現在有元素1、2、3依次進棧,出棧順序有哪些?

  • 第一種:1、2、3(1進、1出、2進、2出、3進、3出)
  • 第二種:3、2、1(1、2、3進,3、2、1出)
  • 第三種:2、1、3(1、2進,2、1出,3進、3出)
  • 第四種:1、3、2(1進、1出,2、3進,3、2出)
  • 第五種:2、3、1(1、2進,2出,3進,3出,1出)

3)棧的存儲結構

image-20210911110342897
  • 棧的順序存儲結構

數組的首元素作為棧底,另外一端作為棧頂,同時定義一個變量 top 來記錄棧頂元素在數組中的比特置。

  • 棧的鏈式存儲結構

單鏈錶的尾部作為棧底,頭部作為棧頂,方便插入和删除(進棧頭插,出棧頭删),頭指針和棧頂指針 top 合二為一。


(2)棧的實現(順序棧)

  • 順序錶的結構相比鏈錶簡單,不影響效率的情况下會優先使用順序錶。
  • 這次我們用的可動態增長的數組來實現的,因為棧只會在一端進行插入和删除操作,用數組效率還是比較高,當然,也會存在一些問題,就是每次空間不够,要重新開辟空間,可能會造成一些內存浪費。

首先新建一個工程( 博主使用的是 VS2019 )

  • Stack.h(棧的類型定義、接口函數聲明、引用的頭文件)
  • Stack.c(棧接口函數的實現)
  • Test.c(主函數、測試棧各個接口功能)

Stack.h 頭文件代碼如下:

#pragma once
#include<stdio.h> /*printf, perror*/
#include<assert.h> /*assert*/
#include<stdlib.h> /*realloc*/
#include<stdbool.h> /*bool*/
typedef int STDataType; //類型重命名,棧中元素類型先假設為int
typedef struct Stack
{

STDataType* a; //指向動態開辟的數組
int top; //記錄棧頂比特置
int capacity; //棧的容量大小
}Stack;
//初始化棧
void StackInit(Stack* ps);
//銷毀棧
void StackDestroy(Stack* ps);
//入棧
void StackPush(Stack* ps, STDataType x);
//出棧
void StackPop(Stack* ps);
//檢測棧是否為空,如果為空返回true,否則返回NULL
bool StackEmpty(Stack* ps);
//獲取棧中有效元素個數
int StackSize(Stack* ps);
//獲取棧頂元素
STDataType StackTop(Stack* ps);

這裏重點講解 Stack.c 中各個接口函數的實現

1)棧的定義

  • 下面是定長的靜態棧的結構,實際中一般不實用,所以我們主要實現下面的支持動態增長的棧
typedef int STDataType; //類型重命名,棧中元素類型先假設為int
#define N 20
struct Stack
{

STDataType a[N]; //定長數組
int top; //記錄棧頂比特置
}SqStack;
  • 支持動態增長的棧

假設棧的容量 capacity 為 5,定義空棧時 top = -1,當棧存在一個元素時 top = 0

image-20210911141218031
typedef int STDataType; //類型重命名,棧中元素類型先假設為int
typedef struct Stack
{

STDataType* a; //指向動態開辟的數組
int top; //記錄棧頂比特置
int capacity; //棧的容量大小
}Stack;

2)棧的初始化

//初始化棧
void StackInit(Stack* ps)
{

assert(ps);
ps->a = NULL;
ps->top = -1;
ps->capacity = 0;
}

3)棧的銷毀

//銷毀棧
void StackDestroy(Stack* ps)
{

assert(ps);
if (ps->a)
{

free(ps->a);
}
ps->a = NULL;
ps->top = -1;
ps->capacity = 0;
}

4)入棧

//入棧
void StackPush(Stack* ps, STDataType x)
{

assert(ps);
if (ps->top == ps->capacity - 1) //檢查棧空間是否滿了
{

//如果棧原始容量為0,新容量設為4,否則設為原始容量的2倍
int newcapacity = (ps->capacity == 0) ? 4 : (ps->capacity) * 2;
//擴容至新容量
STDataType* temp = realloc(ps->a, newcapacity * sizeof(STDataType));
if (temp == NULL)
{

perror("realloc");
exit(-1);
}
ps->a = temp;
//更新容量
ps->capacity = newcapacity;
}
ps->top++; //棧頂指針加一
ps->a[ps->top] = x; //將新增元素放入棧頂空間
}

5)出棧

//出棧
void StackPop(Stack* ps)
{

assert(ps);
assert(ps->top != -1); //棧不能為空
ps->top--; //棧頂指針减一
}

6)檢測棧是否為空

//檢測棧是否為空,如果為空返回true,否則返回NULL
bool StackEmpty(Stack* ps)
{

assert(ps);
return ps->top == -1;
}

7)獲取棧中有效元素個數

//獲取棧中有效元素個數
int StackSize(Stack* ps)
{

assert(ps);
return ps->top + 1;
}

8)獲取棧頂元素

//獲取棧頂元素
STDataType StackTop(Stack* ps)
{

assert(ps);
assert(!StackEmpty(ps)); //棧不能為空
return ps->a[ps->top];
}

(3)測試棧的功能

  • 棧的實現,不能像順序錶一樣,去實現一個打印函數來遍曆棧並輸出,這樣就不符合棧的特點了(只能在棧頂插入删除,後進先出),所以我們這樣來實現出棧:獲取並打印棧頂元素,再删除棧頂元素,繼續獲取新的棧頂元素。
void TestStack() //測試函數
{

Stack s;
//c
StackInit(&s);
//入棧
StackPush(&s, 1);
StackPush(&s, 2);
StackPush(&s, 3);
StackPush(&s, 4);
StackPush(&s, 5);
//出棧
while (!StackEmpty(&s))
{

printf("%d ", StackTop(&s)); //獲取棧頂元素
StackPop(&s);
}
printf("\n");
//銷毀棧
StackDestroy(&s);
}
  • 運行結果
image-20210911142646437

大家快去動手實現一下吧!

版权声明:本文为[CodeWinter]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080058137439.html