C語言編程數(shù)據(jù)結(jié)構(gòu)的棧和隊列
棧
棧是一種以后進先出為順序?qū)ο筮M行添加或刪除的數(shù)據(jù)結(jié)構(gòu)
對棧進行形象記憶就像是桌子上的一堆書或一堆盤。對盤子取或者存盤子，都只能對最上面的書或者盤子進行操作。
對于棧而言，只有彈棧才能獲取其數(shù)據(jù)。
當我們用C語言實現(xiàn)棧這個數(shù)據(jù)結(jié)構(gòu)。
其實有三種方法實現(xiàn)
1，數(shù)組
2，單鏈表
3，雙向鏈表
但是，對于雙向鏈表，實現(xiàn)棧而言過于復雜。
可以選擇數(shù)組或者單鏈表。
數(shù)組實現(xiàn)
標題全部代碼
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)//銷毀棧，防止內(nèi)存泄漏
{
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//結(jié)構(gòu)體用于維護棧
{
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);//銷毀棧，防止內(nèi)存泄漏
void StackPrint(STstack* st);//打印棧的元素，但前提是要退棧才能得到元素
對于數(shù)組實現(xiàn)而言。創(chuàng)建一個結(jié)構(gòu)體用于維護整個棧。而其中有一個用于鏈接創(chuàng)建的數(shù)組。
typedef int STData;
typedef struct Stack//結(jié)構(gòu)體用于維護棧
{
int top;//棧頂標記
STData* arr;//棧的指針
int capacity;//棧的容量
}STstack;
作為數(shù)組棧，需要一個動態(tài)的數(shù)組。則這就需要一個Capacity作為衡量是否需要擴容的標準。而top需要作為入棧元素的位置。
當top的值等于Capacity時就意味著棧已經(jīng)滿了。因為數(shù)組是從0開始的
初始化數(shù)組棧
在初始化時，要先動態(tài)開辟一個數(shù)組空間，且，未壓棧壓入數(shù)據(jù)元素，其top要設(shè)為0.要保證當需要壓棧時有明確指定的空間。同時，top的位置要為最后壓入數(shù)據(jù)的下一個下標。
void InitStack(STstack* st)//棧的初始化
{
st->top = 0;
st->arr = (STData*)malloc(CAP*sizeof(STData));
st->capacity = CAP;
}
滿棧后擴容
其Capacity要作為判斷是否滿棧的標準。且，滿棧后要進行擴容（因為是動態(tài)數(shù)組）。
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的位置在數(shù)組的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位置的數(shù)位置進行賦值。并之后要將top向后移動一個位置。保證下一次壓棧。
退棧
退棧返回top的上一個位置的元素。同時top向前移動一個位置，不需要free，下次壓棧會自動覆蓋。
鏈表實現(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é)點賦值
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);
}
}
對于鏈表實現(xiàn)棧而言，和數(shù)組其實差不多。只不夠，每次壓棧都需要重新動態(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;
}
出棧情況
尤其要把握一個條件：空棧
由于不是數(shù)組，且鏈式結(jié)構(gòu)的特性，是不需要擴容的。即不需要判斷滿棧的情況。
只考慮空棧的條件
void emptystack(sta* a)//檢查是否空棧的情況
{
if (top == NULL)
{
printf("Stack empty");
exit(0);
}
}
這里空棧的條件是top指針指向NULL時也就是
為什么呢？
因為每次彈棧的時候，都會free掉top指向的空間然后讓top指向下一個節(jié)點。就這樣不斷移動。但是我設(shè)計初始化的時候是top= NULL;而且每次壓棧都是p->point = top;這就會有一個標準來限定空棧的情況。
對于棧而言，其更像是一個遞歸的具象化。
隊列
這種數(shù)據(jù)結(jié)構(gòu)就像是銀行柜臺的取號機，
先取號的先去柜臺。
始終滿足先入先出的概念
隊列的實現(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)體用于維護隊列
{
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);//銷毀隊，防止內(nèi)存泄漏
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)//銷毀隊，防止內(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)//打印隊列中的元素，但前提是要出隊才能得到元素
{
queue* cur = qu->Dequeue;
while (cur)
{
printf("%d ", cur->data);
cur = cur->next;
}
}
隊 畢竟是先入先出的數(shù)據(jù)結(jié)構(gòu)。
所以要兩個指針，
qu->Dequeue 指向隊頭，
qu->Enqueue 指向隊尾，
不然每次都去找隊尾是相當浪費時間的。
一個結(jié)構(gòu)體類型用于維護這個隊列
typedef int QUData;
typedef struct queue//描述每個隊的元素
{
QUData data;
struct queue* next;
}queue;
typedef struct Queue//結(jié)構(gòu)體用于維護隊列
{
queue* Dequeue;//隊頭指針
queue* Enqueue;//隊尾指針
}QUqueue;
隊頭指針負責出隊，
隊尾指針負責入隊。
概念流程圖
入隊
入隊列的實現(xiàn)
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。
當入第一個元素時，那個元素即是第一個元素也是最后一個元素。要獨立判斷。**這是一個特殊情況。
出隊
出隊列的實現(xiàn)
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 ,這是直接報錯的。
所以還要一個函數(shù)判斷是否空隊。
是否空隊
int QueueEmpty(QUqueue* qu)//判斷隊列是否為空
{
if (qu->Dequeue == qu->Enqueue)
return 1;
return 0;
}
空隊就是相當于回到了初始化的情形
qu->Dequeue = qu->Enqueue = NULL;
也就是兩者都指向同一處，也就是NULL。
以上就是C語言編程數(shù)據(jù)結(jié)構(gòu)的棧和隊列的詳細內(nèi)容，更多關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)的資料請關(guān)注腳本之家其它相關(guān)文章！
感謝觀看~
相關(guān)文章
Qt提供了對象樹機制，能夠自動、有效的組織和管理繼承自QObject的Qt對象。這篇文章將通過一些示例為大家介紹一下Qt中對象樹機制的使用，需要的可以參考一下2023-03-03
這篇文章主要介紹了C語言中循環(huán)嵌套的應用方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
QT自定義QTextEdit實現(xiàn)大數(shù)據(jù)的實時刷新顯示功能實例
TextEdit是我們常用的Qt控件,用來顯示文本信息,下面這篇文章主要給大家介紹了關(guān)于QT自定義QTextEdit實現(xiàn)大數(shù)據(jù)的實時刷新顯示功能的相關(guān)資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-05-05
這篇文章主要介紹了C++類常量和類枚舉，給類當中定義一些常量，可以給所有類的對象使用，比如說我們在類當中定義一個數(shù)組，希望可以定義一個常量，用來初始化數(shù)組的長度，那么下面我i嗎就來看看過程當如何吧2022-01-01
__stdcall 和 __cdecl 的區(qū)別淺析，需要的朋友可以參考一下2013-03-03
C++ 模擬實現(xiàn)list(迭代器)實現(xiàn)代碼
這篇文章主要介紹了C++ 模擬實現(xiàn)list(迭代器)實現(xiàn)代碼的相關(guān)資料,需要的朋友可以參考下2017-05-05
C++指針和數(shù)組：字符和字符串、字符數(shù)組的關(guān)聯(lián)和區(qū)別
字符串是一種重要的數(shù)據(jù)類型，但是c語言并沒有顯示的字符串數(shù)據(jù)類型，因為字符串以字符串常量的形式出現(xiàn)或者存儲于字符數(shù)組中。在C++標準模板庫（STL）中提供了string類，實現(xiàn)了對字符串的封裝。2022-12-12
這篇文章主要介紹了C++抽象基類講解，象基類abstract base class簡稱ABC，C++實現(xiàn)繼承的時候，需要保證派生類和基類之間是一種is-a的關(guān)系。在大多數(shù)時刻，這樣的關(guān)系是沒有問題的，然而在一些特殊的情況可能會遇到問題，下面來看看文章的具體介紹吧2022-01-01
C++ 中malloc()和free()函數(shù)的理解
這篇文章主要介紹了C++ 中malloc()和free()函數(shù)的理解的相關(guān)資料,這里提供用法示例幫助大家理解這部分知識，需要的朋友可以參考下2017-08-08
這篇文章主要為大家詳細介紹了C語言實現(xiàn)歌曲信息管理系統(tǒng)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01