C语言实现栈和队列

左手的ㄟ右手 2022-12-29 14:15 209阅读 0赞

#  #

# 栈 #

*  ### 栈的理解： ###

一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO (Last In First Out)的原则。  
**压栈:**栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。  
**出栈:**栈的删除操作叫做出栈。出数据也在栈顶。

*  ### 栈的实现： ###

栈的实现可以通过连续结构实现 （顺序表），也可以通过非连续结构实现 （链表）

连续结构实现：

**入栈：尾插 O（1） 头插 O（n）需要从后开始移动数据元素**

**出栈：尾删 O（1） 头删 O（n）需要从前开始覆盖移动数据元素**

非连续结构实现

**入栈：尾插 O（1） 头插 O（1）**

**出栈：尾删 O（1） 头删 O（1）**

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

![2020122311101583.png][]

*  ### 栈结构定义 ###

由于栈通过顺序表来实现，顺序表结构包含数据值，当前元素个数，以及存储容量

// 支持动态增长的栈
    typedef int STDataType;
    typedef struct Stack
    {
    	STDataType* _data;
    	int _size;
    	int _capacity; // 容量
    }Stack;

*  ### 栈接口声明 ###

//检查容量
    void checkCapcity(Stack* ps);
    // 初始化栈
    void StackInit(Stack* ps);
    // 入栈
    void StackPush(Stack* ps, STDataType data);
    // 出栈
    void StackPop(Stack* ps);
    // 获取栈顶元素
    STDataType StackTop(Stack* ps);
    // 获取栈中有效元素个数
    int StackSize(Stack* ps);
    // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
    int StackEmpty(Stack* ps);
    // 销毁栈
    void StackDestroy(Stack* ps);

*  ### 栈接口实现 ###

实现过程即为顺序表尾插尾删操作，极为简单，这里不做过多描述，不清楚的同学可以参考[C语言实现顺序表][C]

//检查容量
    void checkCapcity(Stack* ps)
    {
    	if (ps->_size == ps->_capacity)
    	{
    		int newCap = ps->_capacity == 0 ? 1 : 2 * ps->_capacity;
    		ps->_data = (STDataType*)realloc(ps->_data, sizeof(STDataType)*newCap);
    		ps->_capacity = newCap;
    	}
    }
    // 初始化栈
    void StackInit(Stack* ps)
    {
    	if (ps == NULL)
    		return;
    	ps->_data = NULL;
    	ps->_size = ps->_capacity = 0;
    }
    // 入栈
    void StackPush(Stack* ps, STDataType data)
    {
    	if (ps == NULL)
    		return;
    	checkCapcity(ps);
    	ps->_data[ps->_size++] = data;
    }
    // 出栈
    void StackPop(Stack* ps)
    {
    	if (ps == NULL || ps->_size == 0)
    		return;
    	ps->_size--;
    
    }
    // 获取栈顶元素
    STDataType StackTop(Stack* ps)
    {
    	return ps->_data[ps->_size - 1];
    }
    // 获取栈中有效元素个数
    int StackSize(Stack* ps)
    {
    	if (ps == NULL)
    		return 0;
    	return ps->_size;
    }
    // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
    int StackEmpty(Stack* ps)
    {
    	if (ps == NULL||ps->_size==0)
    		return 1;
    	else
    		return 0;
    }
    // 销毁栈
    void StackDestroy(Stack* ps)
    {
    	free(ps->_data);
    	ps->_size = 0;
    	ps->_capacity = 0;
    }

*  ### 栈的测试 ###

给出测试代码及结果

#include<stdio.h>
    #include"stack.h"
    
    void test()
    {
    	Stack st;
    	StackInit(&st);
    	StackPush(&st,1);
    	StackPush(&st, 2);
    	StackPush(&st, 3);
    	StackPush(&st, 4);
    	StackPush(&st, 5);
    	printf("依次打印栈顶元素：\n");
    	while (!StackEmpty(&st))
    	{
    		printf("%d ", StackTop(&st));
    		StackPop(&st);
    	}
    }
    
    int main()
    {
    	test();
    	return 0;
    }

**证明栈是先进后出 进栈顺序：1 2 3 4 5 出栈顺序 5 4 3 2 1**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70][]

# 队列 #

*  ### 队列的理解 ###

队列:只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

**入队列**:进行插入操作的一端称为队尾

**出队列**:进行删除操作的一端称为队头

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1][]

*  ### 队列的实现 ###

队列和栈类似，既可以通过顺序表这种连续的结构实现，也可以通过链表这种不连续的结构实现

连续结构：

**入队列**：尾插O（1） 头插O（n）

**出队列**：头删O（n） 尾删O（1）

不连续结构：

**入队列**：尾插O（1） 头插O（1）

**出队列**：头删O（1） 尾删O（1）

**特例：带头尾指针的单链表**

**入队列**：尾插O（1）

**出队列**：头删O（1）

此时选取特例的结构来实现队列

*  ### 队列结构的定义 ###

队列结构由带头尾指针的单链表实现，单链表中每一个节点包含数据本身，以及next指针 链表结构包含头结点和尾结点

//队列实现：带有尾指针的单链表
    
    typedef int QDataType;
    typedef struct QNode
    {
    	QDataType _data;
    	struct QNode* _next;
    }QNode;
    
    typedef struct Queue {
    	//包含头尾指针
    	struct QNode* _head;
    	struct QNode* _tail;
    	int _size;
    }Queue;

*  ### 队列接口的声明 ###

//初始化队列
    void initQueue(Queue* q);
    
    //队尾插入
    void queuePush(Queue* q, QDataType val);
    
    //队头删除
    void queuePop(Queue* q);
    
    //返回队头元素
    QDataType queueFront(Queue* q);
    
    //返回队尾元素
    QDataType queueBack(Queue* q);
    
    //获取队列大小
    int queueSize(Queue* q);
    
    int EmptyQueue(Queue* q);
    
    void queueDestory(Queue* q);

*  ### 队列接口的实现 ###

在实现过程中实现尾插和头删的操作，由于有头结点和尾结点存在，无需遍历单链表 可直接操作，但需要注意判断头结点是否为空

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2][]

**在插入操作过程中，如果头结点为空 需要将头尾指针都指向新插入节点**

**在删除操作过程中，仅有一个头节点，此时头尾指针均指向该头结点 删除后 如果头指针为空，需要将尾指针指向空，否则尾指针变为野指针。**

QNode* createNode(QDataType val)
    {
    	QNode* node = (QNode*)malloc(sizeof(QNode));
    	if (node != NULL)
    	{
    		node->_data = val;
    		node->_next = NULL;
    	}
    	return node;
    }
    
    //初始化队列
    void initQueue(Queue* q)
    {
    	if (q == NULL)
    		return;
    	q->_head = NULL;
    	q->_tail = NULL;
    	q->_size = 0;
    }
    
    //队尾插入
    void queuePush(Queue* q, QDataType val)
    {
    	if (q == NULL)
    		return;
    	struct QNode* newnode = createNode(val);
    	if (q->_head == NULL)//若头为空
    		q->_head = q->_tail = newnode;
    	//头不为空，尾指针存在
    	else
    	{
    		q->_tail->_next = newnode;
    		q->_tail = newnode;//更新尾指针
    	}
    	q->_size++;
    }
    
    //队头删除
    void queuePop(Queue* q)
    {
    	if (q == NULL || q->_head == NULL)
    		return;
    	struct QNode* next = q->_head->_next;
    	free(q->_head);
    	q->_head = next;
    	if (q->_head == NULL)//如果空队列head=tail  头删之后 head为空  此时为了不让tail变野指针，将其置NULL
    		q->_tail = NULL;
    	q->_size--;
    }
    
    //返回队头元素
    QDataType queueFront(Queue* q)
    {
    	return q->_head->_data;
    }
    
    //返回队尾元素
    QDataType queueBack(Queue* q)
    {
    	return q->_tail->_data;
    }
    
    int EmptyQueue(Queue* q)
    {
    	return q->_head == NULL;
    }
    //获取队列大小
    int queueSize(Queue* q)
    {
    	if (q == NULL)
    		return 0;
    	return q->_size;
    }
    //销毁队列
    void queueDestory(Queue* q)
    {
    	QNode* cur = q->_head;
    	while (cur)
    	{
    		QNode* next = cur->_next;
    		free(cur);
    		cur = next;
    	}
    	q->_head = q->_tail = NULL;
    }

*  ### 队列的测试： ###

测试代码如下：

include<stdio.h>
    
    #include"queue.h"
    
    
    void test()
    {
    	Queue q;
    	initQueue(&q);
    	queuePush(&q, 1);
    	queuePush(&q, 2);
    	queuePush(&q, 3);
    	queuePush(&q, 4);
    	queuePush(&q, 5);
    	printf("依次出队打印队头元素:\n");
    	while(!EmptyQueue(&q))
    	{
    		printf("%d ", queueFront(&q));
    		queuePop(&q);
    	}
    	printf("\n");
    }
    
    int main()
    {
    	test();
    	return 0;
    }

**结果表明：队列是先进先出 入队顺序：1 2 3 4 5 出队顺序：1 2 3 4 5**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3][]

**上述已经实现了栈和队列的基本操作，接下来将通过leetcod算法实例来演示，二者之间的相互转换**

### （1） 栈实现队列 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 6][]

具体代码如下：在自定义队列结构中定义两个栈，一个入队栈，一个出队栈

typedef struct {
        struct Stack in_st;//入队栈
        struct Stack out_st;//出队栈
    } MyQueue;
    
    /** Initialize your data structure here. */
    
    MyQueue* myQueueCreate() {
         //动态创建
        MyQueue* q=(MyQueue*)malloc(sizeof(MyQueue));
        StackInit(&q->in_st);
        StackInit(&q->out_st);
        return q;
    }
    
    /** Push element x to the back of queue. */
    void myQueuePush(MyQueue* obj, int x) {
        StackPush(&obj->in_st,x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int myQueuePop(MyQueue* obj) {
        int top;
        if(!StackEmpty(&obj->out_st))//出队栈非空
        {
            top=StackTop(&obj->out_st);
            StackPop(&obj->out_st);
        }
        else//出队栈为空  将入队栈元素放入出队栈
        {
           while(!StackEmpty(&obj->in_st))
           {
               StackPush(&obj->out_st,StackTop(&obj->in_st));
               StackPop(&obj->in_st);
           }
           top=StackTop(&obj->out_st);
           StackPop(&obj->out_st); 
        }
        return top;
    }
    
    /** Get the front element. */
    int myQueuePeek(MyQueue* obj) {
        int top;
        if(StackEmpty(&obj->out_st))//出队栈空
        {
           while(!StackEmpty(&obj->in_st))
           {
               StackPush(&obj->out_st,StackTop(&obj->in_st));
               StackPop(&obj->in_st);
           }
           top=StackTop(&obj->out_st);
        }
        else
        {
           top=StackTop(&obj->out_st);
        }
        return top;
    }
    
    /** Returns whether the queue is empty. */
    bool myQueueEmpty(MyQueue* obj) {
        return StackEmpty(&obj->in_st)&&StackEmpty(&obj->out_st);
    }
    
    void myQueueFree(MyQueue* obj) {
        StackDestory(&obj->in_st);
        StackDestory(&obj->out_st);
        free(obj);
    }

**提交结果如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 7][]

### （2） 队列实现栈 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 8][]

typedef struct {
        struct Queue q;
    } MyStack;
    
    /** Initialize your data structure here. */
    
    MyStack* myStackCreate() {
        //动态创建
        MyStack* st=(MyStack*)malloc(sizeof(MyStack));
        initQueue(&st->q);
        return st;
    }
    
    /** Push element x onto stack. */
    void myStackPush(MyStack* obj, int x) {
        queuePush(&obj->q,x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int myStackPop(MyStack* obj) {
        int n=queueSize(&obj->q);
        while(n>1)//前n-1个元素先出队再入队
        {
            int front=queueFront(&obj->q);
            queuePop(&obj->q);
            queuePush(&obj->q,front);
            n--;
        }
        //此时n=1；
        int top=queueFront(&obj->q);
        queuePop(&obj->q);
        return top;
    }
    
    /** Get the top element. */
    int myStackTop(MyStack* obj) {
        return queueBack(&obj->q);
    }
    
    /** Returns whether the stack is empty. */
    bool myStackEmpty(MyStack* obj) {
        return EmptyQueue(&obj->q);
    }
    
    void myStackFree(MyStack* obj) {
        queueDestory(&obj->q);
        free(obj);
    }

此过程中，入栈直接入队操作即可，因为逆序，所以获取栈顶元素也可以通过队列（队尾指针）获取队尾元素即可

除出栈操作相对复杂一点，但此处只在同一个队列里完成，没有开辟其余空间

**提交结果如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 9][]

[2020122311101583.png]: /images/20221120/da9ea117947447a4a79878014da473e9.png
[C]: https://blog.csdn.net/qq_36131611/article/details/110882819
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70]: /images/20221120/4f3dc9908e9c4550ad312f97690fa78c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1]: /images/20221120/2c9921579a674644bcdd65477d7d5544.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2]: /images/20221120/cbf794a9b8a249ed9e8c4f5e1eaea511.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3]: /images/20221120/217dcef0c95d450582a779c3fc3408fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4]: /images/20221120/e7856d13a1b847478049ce7ae0d9ab44.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 5]: /images/20221120/4f5f4de814804c38b85d5a11ddd39dc3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 6]: /images/20221120/d262412066ae426e9a2ba355f3ec960a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 7]: /images/20221120/2167398dba8243f1b91694c35ee91a4c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 8]: /images/20221120/b85717037c5348e092f000be549d4cde.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 9]: /images/20221120/f6b3485c3db54c238b4d27d2daf80de4.png