目錄
一、棧
二、隊(duì)列
三、循環(huán)隊(duì)列
一、棧
特性：
- 順序存儲(chǔ)，后進(jìn)先出
- 優(yōu)點(diǎn)是可隨機(jī)訪問(wèn)，尾部增刪效率高
- 缺點(diǎn)是可能會(huì)浪費(fèi)空間，不知道頭部增刪
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#define CAPACITY 3 //默認(rèn)初識(shí)容量
typedef int SData;
typedef struct Stack
{
SData* data;
size_t size;
size_t capacity;
}Stack;
void Init(Stack* s)
{
assert(s);
s->data = (SData*)malloc(sizeof(SData) * CAPACITY);
if (s == NULL)
{
perror("init::malloc");
exit(1);
}
s->size = 0;
s->capacity = CAPACITY;
}
bool Empty(Stack* s)
{
assert(s);
return s->size == 0;
}
void CheckCapacity(Stack* s)
{
assert(s);
if (s->size == s->capacity) {
SData* tmp = (SData*)realloc(s->data, sizeof(SData) * (s->size + CAPACITY));
if (tmp == NULL)
{
perror("realloc");
exit(1);
}
s->data = tmp;
s->capacity += CAPACITY;
}
}
void Push(Stack* s, SData x)
{
assert(s);
CheckCapacity(s);
s->data[s->size] = x;
++s->size;
}
void Pop(Stack* s)
{
assert(s);
if (!Empty(s))
--s->size;
}
size_t Size(Stack* s)
{
assert(s);
printf("the stack size is %d\n", s->size);
return s->size;
}
void PrintStack(Stack* s)
{
assert(s);
if (!Empty(s))
{
int i = 0;
while (i < s->size)
{
printf("%d ", s->data[i]);
++i;
}
printf("\n");
}
}
int main()
{
Stack s;
Init(&s);
Push(&s, 1);
Push(&s, 3);
Push(&s, 2);
Push(&s, 4);
Size(&s);
PrintStack(&s);
Pop(&s);
Pop(&s);
Pop(&s);
Pop(&s);
Pop(&s);
Size(&s);
PrintStack(&s);
return 0;
}二、隊(duì)列
特性：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-492242.html
- 鏈?zhǔn)酱鎯?chǔ)，先進(jìn)先出
- 優(yōu)點(diǎn)是無(wú)空間浪費(fèi)，頭部增刪效率高
- 缺點(diǎn)是不能隨機(jī)訪問(wèn)，尾部增刪效率低
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QData;
typedef struct Queue
{
QData data;
struct Queue* next;
}Queue;
void Init(Queue* q)
{
assert(q);
q->next = (Queue*)malloc(sizeof(Queue));
q->next->next = NULL;
}
bool Empty(Queue* q)
{
assert(q);
return q->next->next == NULL;
}
void Push(Queue* q, QData x)
{
assert(q);
Queue* node = (Queue*)malloc(sizeof(Queue));
node->data = x;
node->next = q->next->next;
q->next->next = node;
}
void Pop(Queue* q)
{
assert(q);
if (!Empty(q))
{
Queue* cur = q->next->next;
q->next->next = cur->next;
free(cur);
cur = NULL;
}
}
size_t Size(Queue* q)
{
assert(q);
size_t size = 0;
if (!Empty(q))
{
Queue* cur = q->next->next;
while (cur)
{
++size;
cur = cur->next;
}
}
printf("the list size is %d\n", size);
return size;
}
void PrintQueue(Queue* q)
{
assert(q);
if (!Empty(q))
{
Queue* cur = q->next->next;
printf("%d ", cur->data);
while (cur->next)
{
printf("-> %d ", cur->next->data);
cur = cur->next;
}
printf("\n");
}
}
int main()
{
Queue q;
Init(&q);
Push(&q, 1);
Push(&q, 3);
Push(&q, 4);
Push(&q, 2);
Size(&q);
PrintQueue(&q);
Pop(&q);
Pop(&q);
Pop(&q);
Pop(&q);
Pop(&q);
Size(&q);
PrintQueue(&q);
return 0;
}三、循環(huán)隊(duì)列
特性：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-492242.html
- 順序存儲(chǔ)，先進(jìn)先出，頭刪尾增
- 初始化設(shè)定空間容量CAPACITY，數(shù)據(jù)存儲(chǔ)量比空間容量少1（空位區(qū)分滿(mǎn)和空）
- head和tail的加減要考慮隊(duì)列是否存滿(mǎn)以及和CAPACITY的關(guān)系
- 判空：return tail == head;
- 判滿(mǎn)：return (tail + 1) % CAPACITY == head;
- Push：判斷非滿(mǎn)，tail = （tail + 1）% CAPACITY;
- Pop： 判斷非空，head = （head + 1）% CAPACITY;
- 優(yōu)點(diǎn)：空間可重復(fù)利用，支持隨機(jī)訪問(wèn)
- 缺點(diǎn)：空間有限不可擴(kuò)容
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#define CAPACITY 5 //總?cè)萘繛?，數(shù)據(jù)容量為4
typedef int CQData;
typedef struct CirQue
{
CQData* data;
int head;
int tail;
int size;
}CirQue;
void Init(CirQue* cq)
{
assert(cq);
cq->data = (CQData*)malloc(sizeof(CQData) * CAPACITY); //多開(kāi)辟一個(gè)空間
cq->head = cq->tail = cq->size = 0;
}
bool Empty(CirQue* cq)
{
assert(cq);
return cq->head == cq->tail;
}
bool Full(CirQue* cq)
{
assert(cq);
return (cq->tail + 1) % CAPACITY == cq->head;
}
int Size(CirQue* cq)
{
assert(cq);
return (cq->tail + CAPACITY - cq->head) % CAPACITY;
}
void Push(CirQue* cq, CQData x)
{
assert(cq);
if (!Full(cq))
{
cq->data[cq->tail] = x;
cq->tail = (cq->tail + 1) % CAPACITY;
}
}
void Pop(CirQue* cq)
{
assert(cq);
if (!Empty(cq))
cq->head = (cq->head + 1) % CAPACITY;
}
void PrintCirQue(CirQue* cq)
{
assert(cq);
if (!Empty(cq))
{
int pos = cq->head;
int size = Size(cq);
while (size--)
{
printf("%d ", cq->data[pos]);
pos = (pos + 1) % CAPACITY;
}
printf("\n");
}
}
int main ()
{
CirQue cq;
Init(&cq);
Push(&cq, 1);
Push(&cq, 3);
Push(&cq, 5);
printf("the CirQue size is %d\n", Size(&cq));
PrintCirQue(&cq);//1 3 5
Push(&cq, 2);
Push(&cq, 4);
Push(&cq, 6);
printf("the CirQue size is %d\n", Size(&cq));
PrintCirQue(&cq);//1 3 5 2
Pop(&cq);
Pop(&cq);
Pop(&cq);
printf("the CirQue size is %d\n", Size(&cq));
PrintCirQue(&cq);//2
Push(&cq, 10);
Push(&cq, 20);
Push(&cq, 30);
Push(&cq, 40);
printf("the CirQue size is %d\n", Size(&cq));
PrintCirQue(&cq);//2 10 20 30
Pop(&cq);
Pop(&cq);
Pop(&cq);
Pop(&cq);
Pop(&cq);
Pop(&cq);
printf("the CirQue size is %d\n", Size(&cq));
PrintCirQue(&cq);
return 0;
}
到了這里，關(guān)于【C/C++數(shù)據(jù)結(jié)構(gòu)與算法】C語(yǔ)言棧與隊(duì)列的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
