C語言編程數(shù)據(jù)結(jié)構(gòu)的棧和隊(duì)列
棧
棧是一種以后進(jìn)先出為順序?qū)?duì)象進(jìn)行添加或刪除的數(shù)據(jù)結(jié)構(gòu)
對(duì)棧進(jìn)行形象記憶就像是桌子上的一堆書或一堆盤。對(duì)盤子取或者存盤子，都只能對(duì)最上面的書或者盤子進(jìn)行操作。
對(duì)于棧而言，只有彈棧才能獲取其數(shù)據(jù)。
當(dāng)我們用C語言實(shí)現(xiàn)棧這個(gè)數(shù)據(jù)結(jié)構(gòu)。
其實(shí)有三種方法實(shí)現(xiàn)
1，數(shù)組
2，單鏈表
3，雙向鏈表
但是，對(duì)于雙向鏈表，實(shí)現(xiàn)棧而言過于復(fù)雜。
可以選擇數(shù)組或者單鏈表。
數(shù)組實(shí)現(xiàn)
標(biāo)題全部代碼
Stack_array.c
#include "Stack_array.h"
void InitStack(STstack* st)//棧的初始化
{
st->top = 0;
st->arr = (STData*)malloc(CAP*sizeof(STData));
st->capacity = CAP;
}
void StackPush(STstack* st, STData n)//元素入棧
{
if (st->top == st->capacity)//判斷是否需要擴(kuò)容
{
StackExpansion(st);
}
st->arr[st->top++] = n;
}
STData StackPop(STstack* st)//元素退棧
{
assert(st);
assert(!StackEmpty(st));//判斷是否為空棧
return st->arr[--st->top];
}
int StackEmpty(STstack* st)//判斷棧是否為空
{
if (st->top == 0)
return 1;
return 0;
}
void StackDestory(STstack* st)//銷毀棧，防止內(nèi)存泄漏
{
free(st->arr);
st->arr = NULL;
}
void StackExpansion(STstack* st)//擴(kuò)容
{
STData* tmp = (STData*)realloc((STData*)st->arr, sizeof(STData) * (st->capacity) * 2);
if (tmp == NULL)
{
printf("Exparsion Error\n");
exit(-1);
}
st->arr = tmp;
st->capacity *= 2;
}
void StackPrint(STstack* st)//打印棧的元素，但前提是要退棧才能得到元素
{
while(st->top)
{
STData ret = StackPop(st);
printf("%d ", ret);
}
}
Stack_array.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define CAP 4
typedef int STData;
typedef struct Stack//結(jié)構(gòu)體用于維護(hù)棧
{
int top;//棧頂標(biāo)記
STData* arr;//棧的指針
int capacity;//棧的容量
}STstack;
void InitStack(STstack* st);//棧的初始化
void StackPush(STstack* st, STData n);//元素入棧
STData StackPop(STstack* st);//元素退棧
void StackExpansion(STstack* st);//擴(kuò)容
int StackEmpty(STstack* st);//判斷棧是否為空
void StackDestory(STstack* st);//銷毀棧，防止內(nèi)存泄漏
void StackPrint(STstack* st);//打印棧的元素，但前提是要退棧才能得到元素
對(duì)于數(shù)組實(shí)現(xiàn)而言。創(chuàng)建一個(gè)結(jié)構(gòu)體用于維護(hù)整個(gè)棧。而其中有一個(gè)用于鏈接創(chuàng)建的數(shù)組。
typedef int STData;
typedef struct Stack//結(jié)構(gòu)體用于維護(hù)棧
{
int top;//棧頂標(biāo)記
STData* arr;//棧的指針
int capacity;//棧的容量
}STstack;
作為數(shù)組棧，需要一個(gè)動(dòng)態(tài)的數(shù)組。則這就需要一個(gè)Capacity作為衡量是否需要擴(kuò)容的標(biāo)準(zhǔn)。而top需要作為入棧元素的位置。
當(dāng)top的值等于Capacity時(shí)就意味著棧已經(jīng)滿了。因?yàn)閿?shù)組是從0開始的
初始化數(shù)組棧
在初始化時(shí)，要先動(dòng)態(tài)開辟一個(gè)數(shù)組空間，且，未壓棧壓入數(shù)據(jù)元素，其top要設(shè)為0.要保證當(dāng)需要壓棧時(shí)有明確指定的空間。同時(shí)，top的位置要為最后壓入數(shù)據(jù)的下一個(gè)下標(biāo)。
void InitStack(STstack* st)//棧的初始化
{
st->top = 0;
st->arr = (STData*)malloc(CAP*sizeof(STData));
st->capacity = CAP;
}
滿棧后擴(kuò)容
其Capacity要作為判斷是否滿棧的標(biāo)準(zhǔn)。且，滿棧后要進(jìn)行擴(kuò)容（因?yàn)槭莿?dòng)態(tài)數(shù)組）。
void StackExpansion(STstack* st)//擴(kuò)容
{
STData* tmp = (STData*)realloc((STData*)st->arr, sizeof(STData) * (st->capacity) * 2);
if (tmp == NULL)
{
printf("Exparsion Error\n");
exit(-1);
}
st->arr = tmp;
st->capacity *= 2;
}
同時(shí)，還要每次更改棧的容量，為下一次是否滿棧作為標(biāo)準(zhǔn)。
是否為空棧
int StackEmpty(STstack* st)//判斷棧是否為空
{
if (st->top == 0)
return 1;
return 0;
}
其是否為空。也就是top的位置在數(shù)組的0下標(biāo)位。
壓棧和退棧
void StackPush(STstack* st, STData n)//元素入棧
{
if (st->top == st->capacity)//判斷是否需要擴(kuò)容
{
StackExpansion(st);
}
st->arr[st->top++] = n;
}
STData StackPop(STstack* st)//元素退棧
{
assert(st);
assert(!StackEmpty(st));//判斷是否為空棧
return st->arr[--st->top];
}
壓棧
每次壓棧，都需要判斷是否滿棧，并決定是否擴(kuò)容。
同時(shí)，當(dāng)在原先top位置的數(shù)位置進(jìn)行賦值。并之后要將top向后移動(dòng)一個(gè)位置。保證下一次壓棧。
退棧
退棧返回top的上一個(gè)位置的元素。同時(shí)top向前移動(dòng)一個(gè)位置，不需要free，下次壓棧會(huì)自動(dòng)覆蓋。
鏈表實(shí)現(xiàn)
stack_chain.h
#include <stdio.h>
#include <stdlib.h>
#define N 3
typedef struct stackele
{
int n;
int* point;
}sta;
sta* top;
void initstack(sta* a);//初始化棧
void pushstack(sta* a,int num);//入棧
//void printstack(sta* a);//打印棧
//void fullstack(sta* a);//檢查是否滿棧的情況
void emptystack(sta* a);//檢查是否空棧的情況
int popstack(sta*a);//出棧
stack_chain.c
#include "stack_chain.h"
void initstack(sta* a)//初始化棧
{
top= NULL;
}
void pushstack(sta* a, int num)//入棧
{
sta* p = (sta*)malloc(sizeof(sta));
p->n = num;//新節(jié)點(diǎn)賦值
p->point = top;
top = p;
}
int popstack(sta* a)//出棧
{
emptystack(a);//檢查是否空棧的情況
int date;
sta* des = top;
top = top->point;
date = des->n;
free(des);
des = NULL;
return date;
}
void emptystack(sta* a)//檢查是否空棧的情況
{
if (top == NULL)
{
printf("Stack empty");
exit(0);
}
}
對(duì)于鏈表實(shí)現(xiàn)棧而言，和數(shù)組其實(shí)差不多。只不夠，每次壓棧都需要重新動(dòng)態(tài)開辟一個(gè)新節(jié)點(diǎn)，并且鏈入棧中。但是，這并不是普通的直接鏈入。而是需要頭插入棧。
這樣頭插入棧，可以方便退棧的時(shí)候，可以找到上一個(gè)元素。而壓棧是不需要什么順序。每一個(gè)壓棧節(jié)點(diǎn)就是top節(jié)點(diǎn)。
整個(gè)壓棧流程
void pushstack(sta* a, int num)//入棧
{
sta* p = (sta*)malloc(sizeof(sta));
p->n = num;//新節(jié)點(diǎn)賦值
p->point = top;
top = p;
}
整個(gè)彈棧流程
int popstack(sta* a)//出棧
{
emptystack(a);//檢查是否空棧的情況
int date;
sta* des = top;
top = top->point;
date = des->n;
free(des);
des = NULL;
return date;
}
出棧情況
尤其要把握一個(gè)條件：空棧
由于不是數(shù)組，且鏈?zhǔn)浇Y(jié)構(gòu)的特性，是不需要擴(kuò)容的。即不需要判斷滿棧的情況。
只考慮空棧的條件
void emptystack(sta* a)//檢查是否空棧的情況
{
if (top == NULL)
{
printf("Stack empty");
exit(0);
}
}
這里空棧的條件是top指針指向NULL時(shí)也就是
為什么呢？
因?yàn)槊看螐棗５臅r(shí)候，都會(huì)free掉top指向的空間然后讓top指向下一個(gè)節(jié)點(diǎn)。就這樣不斷移動(dòng)。但是我設(shè)計(jì)初始化的時(shí)候是top= NULL;而且每次壓棧都是p->point = top;這就會(huì)有一個(gè)標(biāo)準(zhǔn)來限定空棧的情況。
對(duì)于棧而言，其更像是一個(gè)遞歸的具象化。
隊(duì)列
這種數(shù)據(jù)結(jié)構(gòu)就像是銀行柜臺(tái)的取號(hào)機(jī)，
先取號(hào)的先去柜臺(tái)。
始終滿足先入先出的概念
隊(duì)列的實(shí)現(xiàn)
queue_chain.h
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int QUData;
typedef struct queue
{
QUData data;
struct queue* next;
}queue;
typedef struct Queue//結(jié)構(gòu)體用于維護(hù)隊(duì)列
{
queue* Dequeue;//隊(duì)頭指針
queue* Enqueue;//隊(duì)尾指針
}QUqueue;
void InitQueue(QUqueue* qu);//棧的初始化
void QueuePush(QUqueue* qu, QUData n);//元素入隊(duì)
QUData QueuePop(QUqueue* qu);//元素出隊(duì)
int QueueEmpty(QUqueue* qu);//判斷隊(duì)列是否為空
void QueueDestory(QUqueue* qu);//銷毀隊(duì)，防止內(nèi)存泄漏
void QueuePrint(QUqueue* qu);//打印隊(duì)列中的元素，但前提是要出隊(duì)才能得到元素
queue_chain.c
#include "queue_chain.h"
void InitQueue(QUqueue* qu)//隊(duì)列的初始化
{
qu->Dequeue = qu->Enqueue = NULL;
}
void QueuePush(QUqueue* qu, QUData n)//元素入隊(duì)
{
queue* newcell = (QUData*)malloc(sizeof(QUData));
newcell->data = n;
newcell->next = NULL;
if (qu->Dequeue == NULL)
{
qu->Enqueue = qu->Dequeue = newcell;
}
else
{
qu->Enqueue->next = newcell;
qu->Enqueue = newcell;
}
}
QUData QueuePop(QUqueue* qu)//元素出隊(duì)
{
if (QueueEmpty(qu))
{
printf("Queue Is Empty");
exit(-1);
}
QUData ret = qu->Dequeue->data;
qu->Dequeue = qu->Dequeue->next;
return ret;
}
int QueueEmpty(QUqueue* qu)//判斷隊(duì)列是否為空
{
if (qu->Dequeue == qu->Enqueue)
return 1;
return 0;
}
void QueueDestory(QUqueue* qu)//銷毀隊(duì)，防止內(nèi)存泄漏
{
queue* cur = qu->Dequeue;
while (cur)
{
queue* pnext = cur->next;
free(cur);
cur = pnext;
}
qu->Dequeue = qu->Enqueue = NULL;
}
void QueuePrint(QUqueue* qu)//打印隊(duì)列中的元素，但前提是要出隊(duì)才能得到元素
{
queue* cur = qu->Dequeue;
while (cur)
{
printf("%d ", cur->data);
cur = cur->next;
}
}
隊(duì) 畢竟是先入先出的數(shù)據(jù)結(jié)構(gòu)。
所以要兩個(gè)指針，
qu->Dequeue 指向隊(duì)頭，
qu->Enqueue 指向隊(duì)尾，
不然每次都去找隊(duì)尾是相當(dāng)浪費(fèi)時(shí)間的。
一個(gè)結(jié)構(gòu)體類型用于維護(hù)這個(gè)隊(duì)列
typedef int QUData;
typedef struct queue//描述每個(gè)隊(duì)的元素
{
QUData data;
struct queue* next;
}queue;
typedef struct Queue//結(jié)構(gòu)體用于維護(hù)隊(duì)列
{
queue* Dequeue;//隊(duì)頭指針
queue* Enqueue;//隊(duì)尾指針
}QUqueue;
隊(duì)頭指針負(fù)責(zé)出隊(duì)，
隊(duì)尾指針負(fù)責(zé)入隊(duì)。
概念流程圖
入隊(duì)
入隊(duì)列的實(shí)現(xiàn)
void QueuePush(QUqueue* qu, QUData n)//元素入隊(duì)
{
queue* newcell = (QUData*)malloc(sizeof(QUData));
newcell->data = n;
newcell->next = NULL;
if (qu->Dequeue == NULL)
{
qu->Enqueue = qu->Dequeue = newcell;
}
else
{
qu->Enqueue->next = newcell;
qu->Enqueue = newcell;
}
}
**當(dāng)然，入隊(duì)列在剛開始的時(shí)候，頭尾指針還是一起指向NULL。
當(dāng)入第一個(gè)元素時(shí)，那個(gè)元素即是第一個(gè)元素也是最后一個(gè)元素。要獨(dú)立判斷。**這是一個(gè)特殊情況。
出隊(duì)
出隊(duì)列的實(shí)現(xiàn)
QUData QueuePop(QUqueue* qu)//元素出隊(duì)
{
if (QueueEmpty(qu))
{
printf("Queue Is Empty");
exit(-1);
}
QUData ret = qu->Dequeue->data;
qu->Dequeue = qu->Dequeue->next;
return ret;
}
但是每次出隊(duì)列都需要判斷是否為空隊(duì)。如果是空隊(duì)還繼續(xù)出隊(duì)會(huì)相當(dāng)于NULL->next ,這是直接報(bào)錯(cuò)的。
所以還要一個(gè)函數(shù)判斷是否空隊(duì)。
是否空隊(duì)
int QueueEmpty(QUqueue* qu)//判斷隊(duì)列是否為空
{
if (qu->Dequeue == qu->Enqueue)
return 1;
return 0;
}
空隊(duì)就是相當(dāng)于回到了初始化的情形
qu->Dequeue = qu->Enqueue = NULL;
也就是兩者都指向同一處，也就是NULL。
以上就是C語言編程數(shù)據(jù)結(jié)構(gòu)的棧和隊(duì)列的詳細(xì)內(nèi)容，更多關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
感謝觀看~
- C語言深入刨析數(shù)據(jù)結(jié)構(gòu)之棧與鏈棧的設(shè)計(jì)與應(yīng)用
- 詳解C語言數(shù)據(jù)結(jié)構(gòu)之棧
- C語言實(shí)現(xiàn)通用數(shù)據(jù)結(jié)構(gòu)之通用椎棧
- C語言數(shù)據(jù)結(jié)構(gòu)進(jìn)階之棧和隊(duì)列的實(shí)現(xiàn)
- C語言編程數(shù)據(jù)結(jié)構(gòu)棧與隊(duì)列的全面講解示例教程
- C語言數(shù)據(jù)結(jié)構(gòu)之使用鏈表模擬棧的實(shí)例
- C語言中棧的結(jié)構(gòu)和函數(shù)接口的使用示例
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)馬踏棋盤，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-02-02
這篇文章主要為大家介紹了C語言的const,指針和引用，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
C語言實(shí)現(xiàn)數(shù)組的循環(huán)左移,右移,翻轉(zhuǎn)的示例
今天小編就為大家分享一篇C語言實(shí)現(xiàn)數(shù)組的循環(huán)左移,右移,翻轉(zhuǎn)的示例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-07-07
C語言數(shù)據(jù)結(jié)構(gòu)圖的創(chuàng)建與遍歷實(shí)驗(yàn)示例
這篇文章主要為大家介紹了C語言數(shù)據(jù)結(jié)構(gòu)圖的創(chuàng)建與遍歷實(shí)驗(yàn)示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-06-06
這篇文章主要介紹了C語言中fgets和fscanf區(qū)別詳解的相關(guān)資料,希望通過本文能幫助到大家，讓大家理解掌握這部分內(nèi)容，需要的朋友可以參考下2017-10-10
C語言數(shù)據(jù)結(jié)構(gòu)遞歸之斐波那契數(shù)列
這篇文章主要介紹了C語言數(shù)據(jù)結(jié)構(gòu)遞歸之斐波那契數(shù)列的相關(guān)資料,希望通過本文能幫助到大家，讓大家理解掌握這部分內(nèi)容，需要的朋友可以參考下2017-10-10
在C語言中逗號(hào)“,”也是一種運(yùn)算符，稱為逗號(hào)運(yùn)算符，其功能是把兩個(gè)表達(dá)式連接起來組成一個(gè)表達(dá)式，?稱為逗號(hào)表達(dá)式，這篇文章主要介紹了C語言中的逗號(hào)運(yùn)算符,需要的朋友可以參考下2022-11-11
c++中將二維數(shù)組元素變換為逆向存放的實(shí)現(xiàn)代碼
編程將一個(gè)二維數(shù)組元素變換為逆向存放，即按元素在內(nèi)存中的物理排列位置，第一個(gè)元素變成倒數(shù)第一個(gè)元素，第二個(gè)元素變成倒數(shù)第二個(gè)元素，依此類推2020-11-11
JSON（JavaScript?Object?Notation）是一種輕量級(jí)的數(shù)據(jù)交換格式，用來傳輸屬性值或者序列性的值組成的數(shù)據(jù)對(duì)象。本文將利用C語言實(shí)現(xiàn)手寫JSON解析，感興趣的可以了解一下2022-09-09
今天小編就為大家分享一篇C語言switch使用之詭異用法詳解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-12-12