C語言編程數(shù)據(jù)結(jié)構(gòu)的棧和隊(duì)列
棧
棧是一種以后進(jìn)先出為順序?qū)ο筮M(jìn)行添加或刪除的數(shù)據(jù)結(jié)構(gòu)
對棧進(jìn)行形象記憶就像是桌子上的一堆書或一堆盤。對盤子取或者存盤子，都只能對最上面的書或者盤子進(jìn)行操作。
對于棧而言，只有彈棧才能獲取其數(shù)據(jù)。
當(dāng)我們用C語言實(shí)現(xiàn)棧這個(gè)數(shù)據(jù)結(jié)構(gòu)。
其實(shí)有三種方法實(shí)現(xiàn)
1，數(shù)組
2，單鏈表
3，雙向鏈表
但是，對于雙向鏈表，實(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);//打印棧的元素，但前提是要退棧才能得到元素
對于數(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);
}
}
對于鏈表實(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)來限定空棧的情況。
對于棧而言，其更像是一個(gè)遞歸的具象化。
隊(duì)列
這種數(shù)據(jù)結(jié)構(gòu)就像是銀行柜臺的取號機(jī)，
先取號的先去柜臺。
始終滿足先入先出的概念
隊(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)的資料請關(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)文章
Qt提供了對象樹機(jī)制，能夠自動(dòng)、有效的組織和管理繼承自QObject的Qt對象。這篇文章將通過一些示例為大家介紹一下Qt中對象樹機(jī)制的使用，需要的可以參考一下2023-03-03
這篇文章主要介紹了C語言中循環(huán)嵌套的應(yīng)用方式，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-02-02
QT自定義QTextEdit實(shí)現(xiàn)大數(shù)據(jù)的實(shí)時(shí)刷新顯示功能實(shí)例
TextEdit是我們常用的Qt控件,用來顯示文本信息,下面這篇文章主要給大家介紹了關(guān)于QT自定義QTextEdit實(shí)現(xiàn)大數(shù)據(jù)的實(shí)時(shí)刷新顯示功能的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-05-05
這篇文章主要介紹了C++類常量和類枚舉，給類當(dāng)中定義一些常量，可以給所有類的對象使用，比如說我們在類當(dāng)中定義一個(gè)數(shù)組，希望可以定義一個(gè)常量，用來初始化數(shù)組的長度，那么下面我i嗎就來看看過程當(dāng)如何吧2022-01-01
__stdcall 和 __cdecl 的區(qū)別淺析，需要的朋友可以參考一下2013-03-03
C++ 模擬實(shí)現(xiàn)list(迭代器)實(shí)現(xiàn)代碼
這篇文章主要介紹了C++ 模擬實(shí)現(xiàn)list(迭代器)實(shí)現(xiàn)代碼的相關(guān)資料,需要的朋友可以參考下2017-05-05
C++指針和數(shù)組：字符和字符串、字符數(shù)組的關(guān)聯(lián)和區(qū)別
字符串是一種重要的數(shù)據(jù)類型，但是c語言并沒有顯示的字符串?dāng)?shù)據(jù)類型，因?yàn)樽址宰址Ａ康男问匠霈F(xiàn)或者存儲(chǔ)于字符數(shù)組中。在C++標(biāo)準(zhǔn)模板庫（STL）中提供了string類，實(shí)現(xiàn)了對字符串的封裝。2022-12-12
這篇文章主要介紹了C++抽象基類講解，象基類abstract base class簡稱ABC，C++實(shí)現(xiàn)繼承的時(shí)候，需要保證派生類和基類之間是一種is-a的關(guān)系。在大多數(shù)時(shí)刻，這樣的關(guān)系是沒有問題的，然而在一些特殊的情況可能會(huì)遇到問題，下面來看看文章的具體介紹吧2022-01-01
C++ 中malloc()和free()函數(shù)的理解
這篇文章主要介紹了C++ 中malloc()和free()函數(shù)的理解的相關(guān)資料,這里提供用法示例幫助大家理解這部分知識，需要的朋友可以參考下2017-08-08
C語言實(shí)現(xiàn)歌曲信息管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)歌曲信息管理系統(tǒng)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01