個人主頁 ： 個人主頁
個人專欄 ： 《數(shù)據(jù)結(jié)構(gòu)》 《C語言》
前言
棧：一種特殊的線性結(jié)構(gòu)，其只允許在一端進(jìn)行插入，刪除數(shù)據(jù)。允許操作數(shù)據(jù)的一端被稱為棧頂，另一端被稱為棧底。
本篇博客將要實(shí)現(xiàn)的是數(shù)組棧。
一、棧的實(shí)現(xiàn)思路
對于棧的特殊性，用數(shù)組(在數(shù)組尾部插入刪除數(shù)據(jù)) 和 鏈表(頭插頭刪數(shù)據(jù))實(shí)現(xiàn)棧的時間復(fù)雜度都是O(1)，難度不大。
數(shù)組棧的優(yōu)劣
優(yōu)
- 數(shù)組支持隨機(jī)訪問(用下標(biāo)訪問數(shù)據(jù))，許多算法需要隨機(jī)訪問的支持，如二分法…
- 緩存利用率高
劣
- 空間不夠時要擴(kuò)容
- 有時會造成空間浪費(fèi)
1. 結(jié)構(gòu)的定義
棧的結(jié)構(gòu)非常簡單
一個指向動態(tài)開辟空間的指針，一個記錄實(shí)際空間大小的變量，一個記錄棧頂元素的下標(biāo)即可。
typedef int STDataType;
typedef struct Stack
{
STDataType* data;
int top;//棧頂下標(biāo)
int capacity;//空間大小
}Stack;
2. 初始化棧(StackInit)
data指針指向動態(tài)開辟的空間，capacity記錄此時空間大小，top置為0。
- top 置0，表示棧頂數(shù)據(jù)將要插入的位置。
- top 置-1，表示此時棧頂數(shù)據(jù)的位置。
這里，采用top 置0。
//初始化棧
#define SIZE 4
void StackInit(Stack* ps)
{
assert(ps);
ps->data = (STDataType*)malloc(sizeof(STDataType) * SIZE);
if (ps->data == NULL)
{
perror("malloc");
exit(-1);
}
ps->top = 0;
ps->capacity = SIZE;
}
3. 入棧(StackPush)
因為top初始化為0，所以直接在top下標(biāo)處入數(shù)據(jù)即可。但要注意，在入數(shù)據(jù)前要檢查容量，如果top == capacity 要擴(kuò)容。
- 此處檢查容量的操作，可以封裝成一個函數(shù)，但沒必要，因為棧的操作只有入棧要檢查容量，其它的操作并不需要檢查容量，封裝成一個函數(shù)反而效率減低了(函數(shù)的調(diào)用要形成函數(shù)棧幀)。
//入棧
void StackPush(Stack* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * (ps->capacity * 2));
if (tmp == NULL)
{
perror("realloc");
exit(-1);
}
ps->data = tmp;
ps->capacity *= 2;
}
ps->data[ps->top] = x;
ps->top++;
}
4. 出棧(StackPop)
top 表示的是棧頂數(shù)據(jù)將要入棧的位置，那么出棧操作，只需要讓top 減 1即可。(下次入棧數(shù)據(jù)會直接覆蓋)
但要注意，top = 0 時，表示棧內(nèi)沒有數(shù)據(jù)，不能進(jìn)行出棧操作。
- 出棧操作不能獲取數(shù)據(jù)
//出棧
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top != 0);
ps->top--;
}
5. 獲取棧頂元素(StackTop)
top 指向的是數(shù)據(jù)將要入棧的位置，也就是棧頂數(shù)據(jù)的下一個位置。
那么要獲取棧頂數(shù)據(jù)，只需要讀取top - 1處即可。但要注意，如果top = 0，那么top - 1 = -1，會越界訪問，所以top = 0 時，不能獲取棧頂元素。
//獲取棧頂元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->data[ps->top - 1];
}
6. 檢查棧是否為空(StackEmpty)
top 指向的是數(shù)據(jù)將要入棧的位置，其數(shù)值也表示棧內(nèi)數(shù)據(jù)個數(shù)。
所以我們只需要進(jìn)行 top == 0 的判斷，即可知道棧是否為空。
//檢查棧是否為空
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
7. 銷毀棧(StackDestroy)
free掉動態(tài)開辟的空間，使capacity 置 0，top 置 0。
//銷毀棧
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->data);
ps->top = 0;
ps->capacity = 0;
}
二、代碼實(shí)現(xiàn)
Stack.h 文件存放的是函數(shù)的聲明，頭文件的引用，結(jié)構(gòu)體的定義
Stack.c 文件存放的是函數(shù)的實(shí)現(xiàn)文章來源：http://www.zghlxwxcb.cn/news/detail-642710.html
//Stack.h 文件
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#define SIZE 4
typedef int STDataType;
typedef struct Stack
{
STDataType* data;
int top;
int capacity;
}Stack;
//初始化棧
void StackInit(Stack* ps);
//入棧
void StackPush(Stack* ps, STDataType x);
//出棧
void StackPop(Stack* ps);
//獲取棧頂元素
STDataType StackTop(Stack* ps);
//檢查棧是否為空
bool StackEmpty(Stack* ps);
//銷毀棧
void StackDestroy(Stack* ps);
//Stack.c 文件
#include "Stack.h"
//初始化棧
void StackInit(Stack* ps)
{
assert(ps);
ps->data = (STDataType*)malloc(sizeof(STDataType) * SIZE);
if (ps->data == NULL)
{
perror("malloc");
exit(-1);
}
ps->top = 0;
ps->capacity = SIZE;
}
//入棧
void StackPush(Stack* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * (ps->capacity * 2));
if (tmp == NULL)
{
perror("realloc");
exit(-1);
}
ps->data = tmp;
ps->capacity *= 2;
}
ps->data[ps->top] = x;
ps->top++;
}
//出棧
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top != 0);
ps->top--;
}
//獲取棧頂元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->data[ps->top - 1];
}
//檢查棧是否為空
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
//銷毀棧
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->data);
ps->top = 0;
ps->capacity = 0;
}
總結(jié)
以上就是我對于棧的實(shí)現(xiàn)。
文章來源地址http://www.zghlxwxcb.cn/news/detail-642710.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：棧的實(shí)現(xiàn)(C實(shí)現(xiàn))的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
