数据结构(栈和队列的链表方式实现)
程序员文章站
2024-01-24 17:34:22
...
栈:一种特殊的线性结构,删除与插入元素的一端为栈顶,另一端为栈底,栈中元素遵循先进后出LIFO((Last In First Out)的原则.
栈的实现可以使用数组或者链表,我们今天主要使用链表实现,我们在前面已经谈了单链表的操作,关于栈和队列只不过是对链表加以限制,好了,我们直接开始。
一、链栈的定义和初始化
//结构定义
typedef int STData;
typedef struct StackNode{
STData Data;
struct StackNode *Next;
}StackNode,*Stack;
//初始化
void StackInit(Stack *phead){
assert(phead != NULL);
*phead = NULL;
}
二、入栈
//进栈(尾插)
assert(phead != NULL);
void StackPush(Stack *phead, STData x){
StackNode *s = (StackNode *)malloc(sizeof(StackNode));
s->Data = x;
s->Next = *phead;
*phead = s;
}
三、判栈空
bool IsEmpty(Stack phead){
return phead == NULL;
}
四、出栈
//出栈
void StackPop(Stack *phead){
assert(phead != NULL);
StackNode *p = *phead;
if (IsEmpty(*phead)){
printf("栈为空,无法出栈\n");
return;
}
*phead = (*phead)->Next;
free(p);
}
五、遍历栈元素
void StackShow(Stack phead){
StackNode *p = phead;
while (p != NULL){
printf("|%d|\n", p->Data);
p = p->Next;
}
printf(" - \n");
}
六、取栈顶元素
//取栈顶元素
STData StackTop(Stack phead){
assert(phead != NULL);
return phead->Data;
}
七、栈中元素个数
//求栈的元素个数
int StackSize(Stack phead){
StackNode *p = phead;
int count = 0;
while (p != NULL){
count++;
p = p->Next;
}
return count;
}
八、摧毁栈
//摧毁栈
void StackDestroy(Stack *phead){
assert(phead != NULL);
StackNode *p = (*phead)->Next;
StackNode *q = NULL;
while (p != NULL){
q = p;
*phead = p;
p = p->Next;
free(q);
}
free(phead);
}
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO(First In First Out) ,进行插入操作的一端称为队尾,进行删除操作的一端称为队头
一、链式队列的定义与初始化
//链式队列结构定义
typedef struct QueueNode{
QUData Data;
struct QueueNode *Next;
}QueueNode;
typedef struct Queue{
QueueNode *head; //队头指针
QueueNode *tail; //队尾指针
}Queue;
二、入队
//入队
void QueueEn(Queue *pq, QUData x){
assert(pq != NULL);
QueueNode *s = (QueueNode *)malloc(sizeof(QueueNode));
s->Data = x;
s->Next = NULL;
if (pq->head == NULL){
pq->head = pq->tail = s;
}
else{
pq->tail->Next = s;
pq->tail = s;
}
}
三、出队
//出对
void QueueDe(Queue *pq){
assert(pq != NULL);
if (IsEmpty(pq)){
printf("队列无元素,无法出对!\n");
return;
}
QueueNode *p = pq->head;
if (pq->head == pq->tail){
pq->head = pq->tail = NULL;
}
else{
pq->head = p->Next;
free(p);
}
}
四、遍历
//遍历
void QueueShow(Queue *pq){
assert(pq != NULL);
Queue *q = pq;
while (q->head!=NULL){
printf("%d ", q->head->Data);
q->head = q->head->Next;
}
}
五、取队头元素以及元素个数
//取队头元素
QUData QueueFront(Queue *pq){
assert(pq != NULL);
assert(IsEmpty(pq));
return pq->head->Data;
}
//求队列元素个数
int QueueSize(Queue *pq){
assert(pq != NULL);
QueueNode *p = pq->head;
int i = 0;
while (p!= NULL){
i++;
p = p->Next;
}
return i;
}
六、判空
//判空
bool IsEmpty(Queue *pq){
assert(pq != NULL);
return pq->head == NULL;
}
七、摧毁队列
//摧毁队列
void QueueDestroy(Queue *pq){
assert(pq != NULL);
QueueNode *p = pq->head;
while (p != NULL){
pq->head = p->Next;
free(p);
p = pq->head;
}
}
关于栈与队列的基本操作已经实现完成,大家如果有兴趣,可以取使用数组实现,在这里主要强调数组实现队列,有可能会出现“假满”状态,所以要懂得使用循环队列,后边我也会谈这个循环队列的实现,敬请期待!