数据结构 - 栈和队列

本篇博客将介绍栈和队列的定义以及实现。

1.栈的定义

        栈是一种特殊的线性表，只允许在固定的一端进行插入和删除数据，插入数据的一端叫做栈顶，另一端叫做栈底。栈中的数据遵守后进先出的原则 LIFO (Last In First Out)。

        插入数据的操作称为压栈/进栈/入栈。

        删除数据的操作称为出栈。

        压栈和出栈的操作都在栈顶。

2.  栈的实现

栈的实现可以利用数组或者链表，在此处由于数组在尾部插入和删除数据较为简单，因此我们利用数组实现栈的相关操作。数组的结构如下：

因此我们需要实现以下功能

typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;    //栈顶int capaicty;
}ST;void STInit(ST* pst); //初始化
void STDestroy(ST* pst);//内存释放
void STPush(ST* pst, STDataType x);//压栈
void STPop(ST* pst);//出栈
STDataType STTop(ST* pst);//返回栈顶数据
bool STEmpty(ST* pst);//判断栈是否为空
int STSize(ST* pst);//返回栈中数据个数

 接下来，我们可以初始定义一个结构体:

	ST st;

 具体函数代码如下：

void STInit(ST* pst)
{assert(pst);pst->a = NULL;//pst->top = -1; //top指向栈顶数据pst->top = 0;  //top指向栈顶数据的下一个pst->capaicty = 0;
}void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = 0;pst->capaicty = 0;
}void STPush(ST* pst, STDataType x)
{if (pst->top == pst->capaicty){	int newCapacity = pst->capaicty == 0 ? 4 : pst->capaicty * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capaicty = newCapacity;}pst->a[pst->top] = x;pst->top++;
}void STPop(ST* pst)
{assert(pst);assert(!STEmpty(pst));pst->top--;
}STDataType STTop(ST* pst)
{	assert(pst);assert(!STEmpty(pst));return pst->a[pst->top - 1];
}bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;//等于0为真
}int STSize(ST* pst)
{assert(pst);return pst->top;
}

需要注意的是，当打印栈时，则是通过 STDataType STTop(ST* pst); 返回栈顶数据打印，然后栈顶数据出栈，再打印新的栈顶。直到栈为空，代码如下：

while (!STEmpty(&st))
{printf("%d ", STTop(&st));STPop(&st);
}

3. 队列的定义 

        队列只允许一端进行插入数据的操作，二在另一端删除数据的一种特殊线性表，队列数据按照先进先出入队列 FIFO (First in FIrst Out)。

        队尾插入数据，对头删除数据。

4. 队列的实现 

同样的，队列的实现也可以利用数组和链表实现，在此处使用单链表较为简单，因为入队相当于单链表的尾插，出队相当于单链表的头删。

因此我们需要实现以下功能 ：

typedef int  QueueDataType;typedef struct QueueNode //定义每个结点的结构
{struct QueueNode* next;QueueDataType data;
}QNode;typedef struct Queue //标识整个队列
{QNode* phead;QNode* ptail;int size;
}Queue;void  QueueInit(Queue* pq);//队列初始化
void  QueueDestory(Queue* pq);//内存释放
void  QueuePush(Queue* pq, QueueDataType x);//入队
void  QueuePop(Queue* pq);//出队
QueueDataType QueueFront(Queue* pq);//队头数据
QueueDataType QueueBack(Queue* pq);//队尾数据
int QueueSize(Queue* pq);//队列节点个数
bool QueueEmpty(Queue* pq);//判断空队列

接下来，我们定义初始结构体：

Queue q;

 具体实现代码如下：

void  QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}
void  QueueDestory(Queue* pq) 
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}
void  QueuePush(Queue* pq, QueueDataType x) 
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail\n");return;}newnode->data = x;newnode->next = NULL;if (pq->ptail == NULL){assert(pq->phead == NULL);pq->phead = pq->ptail = newnode;}else {pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//1. 一个节点//2. 多个节点if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}
QueueDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}
QueueDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}
int QueueSize(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->size;
}
bool QueueEmpty(Queue* pq) 
{assert(pq);return pq->phead == NULL && pq->ptail == NULL;//空 turn//return pq->size;
}

同样的，返回对头数据打印，然后对头数据出队，再打印新的对头。直到队列为空，代码如下： 

while (!QueueEmpty(&q))
{printf("%d ", QueueFront(&q));QueuePop(&q);
}