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