栈和队列

1. 什么是栈，栈有什么特性？

栈是一种数据结构，说通俗点有点像是一个大袋子，所以它的特性是先入后出，先放进去的数据要等上面的数据取完后才能输出。每次输出的都是最后入进去的数据，同时不能对栈进行随机中间访问和中间插入和删除。

2.栈和栈区的区别是什么？

栈区是内存划分的一块空间，是为存储数据的，而栈是一种数据结构格式。

3. 为什么将递归程序转化成循环时需要用到栈？

因为递归程序的运行过程和栈非常的类似，最后递归进去的程序是最先结束递归的，和栈里存数据是一样的，最后的数据最先出来。

4.动态栈的实现

#pragma once
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
typedef int SDataType;
typedef struct Stack
{
	SDataType* _array;
	int _capacity;
	int _size;
}Stack;

void StackInit(Stack* ps)
{
	assert(ps);
	ps->_size = 0;
	ps->_capacity = 10;
	ps->_array = (SDataType *)malloc(ps->_capacity * sizeof(SDataType));
	if (ps->_array == NULL)
	{
		assert(0);
		return;
	}

}
void StackCheck(Stack* ps)
{
	assert(ps);
	SDataType* tmp = NULL;
		ps->_capacity += 10;
		ps->_array = (SDataType *)realloc(ps->_array,ps->_capacity * sizeof(SDataType));
		if (ps->_array == NULL)
		{
			assert(0);
			return;
		}
		//free(ps->_array);
		//ps->_array = tmp;
		//free(tmp);
}
void StackPush(Stack* ps, SDataType data)
{
	assert(ps);
	if (ps->_capacity == ps->_size)
	{
		ps->_capacity += 10;
		ps->_array = (SDataType *)realloc(ps->_array, ps->_capacity * sizeof(SDataType));
		if (ps->_array == NULL)
		{
			assert(0);
			return;
		}
	}
	ps->_array[ps->_size] = data;
	ps->_size++;
}
void StackPop(Stack* ps)
{
	assert(ps);
	if (ps->_size == 0)
	{
		return;
	}
	ps->_size--;
}
SDataType StackTop(Stack* ps)
{
	assert(ps);
	if (ps->_size == 0)
	{
		return NULL;
	}
	return ps->_array[ps->_size - 1];

}
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_size;
}
int StackEmpty(Stack* ps)
{
	assert(ps);
	return 0 == ps->_size;
}
void StackDestroy(Stack* ps)
{
    assert(ps);
	ps->_capacity = 0;
	ps->_size = 0;
	free(ps->_array);
}
void StackPrint(Stack* ps)
{
	assert(ps);
	for (int i = 0; i < ps->_size; i++)
		printf("%d->", ps->_array[i]);
	
void Test()
{
	Stack ps;
	StackInit(&ps);
	StackPush(&ps, 1);
	StackPush(&ps, 2);
	StackPush(&ps, 3);
	StackPush(&ps, 4);
	StackPush(&ps, 5);
	StackPush(&ps, 1);
	StackPush(&ps, 1);
	StackPush(&ps, 2);
	StackPush(&ps, 2);
	StackPush(&ps, 2);
	StackPush(&ps, 2);
	StackPush(&ps, 3);
	StackPush(&ps, 4);
	StackPush(&ps, 3);
	StackPush(&ps, 4);
	StackPush(&ps, 3);
	StackPush(&ps, 4);
	StackPush(&ps, 3);
	StackPush(&ps, 4);
	StackPrint(&ps);
    
	StackPop(&ps);
	StackPop(&ps);
	StackPop(&ps);
	StackPop(&ps);
	StackPrint(&ps);
	
	printf("the number og top : %d", StackTop(&ps));

	StackDestroy(&ps);

}

5.什么是队列，队列有什么特性？栈和队列有什么区别？

队列也是一种数据结构，就和现实中排队是一样的，队列的特性是先入先出，同时不能对队列进行随机中间访问、删除和插入。队列和栈帧的最大区别是队列先入先出，栈是先入后出。

6.队列的实现

#pragma once
#include <stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int QDataType;
typedef struct QNode
{
	struct QNode* _pNext;
	QDataType _data;
}QNode;

typedef struct Queue
{
	QNode* _front;
	QNode* _back;
}Queue;

void QueueInit(Queue* q)
{
	assert(q);
	q->_back = q->_front = NULL;

}
int QueueEmpty(Queue* q)
{
	assert(q);
	if (q->_front == NULL)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
QNode* BuyQNode(QDataType x)
{
	QNode* newNode = (QNode *)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		assert(0);
		return;
	}
	newNode->_data = x;
	newNode->_pNext = NULL;
	return newNode;
}
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newNode = BuyQNode(data);
	if (QueueEmpty(q))
	{
		q->_front = newNode;
		q->_back = q->_front;
	}
	{
		q->_back->_pNext = newNode;
		q->_back = q->_back->_pNext;
	}
}
void QueuePop(Queue* q)
{
	assert(q);
	if (QueueEmpty(q))
	{
		return;
	}
	QNode* tmp = q->_front;
	q->_front = q->_front->_pNext;
	free(tmp);
}
QDataType QueueFront(Queue* q)
{
	assert(q);
	if (QueueEmpty(q))
	{
		return NULL;
	}
	return q->_front->_data;
}
QDataType QueueBack(Queue* q)
{
	assert(q);
	if (QueueEmpty(q))
	{
		return NULL;
	}
	return q->_back->_data;

}
int QueueSize(Queue* q)
{
	assert(q);
	QNode* CurNode = q->_front;
	int count = 0;
	if (QueueEmpty(q))
		return count;
	while (CurNode != NULL)
	{
		CurNode = CurNode->_pNext;
		count++;
	}
	return count;
}
void QueueDestroy(Queue* q)
{
	assert(q);
	if (QueueEmpty(q))
		return;
	QNode* CurNode = q->_front;
	QNode* tmp = NULL;
	while (CurNode)
	{
		tmp = CurNode;
		CurNode = CurNode->_pNext;
		free(tmp);
	}
	CurNode = NULL;
}
void QueuePrint(Queue* q)
{
	assert(q);
	QNode* CurNode = q->_front;
	while (CurNode)
	{
		printf("%d->", CurNode->_data);
		CurNode = CurNode->_pNext;
	}
	printf("\n");
}

void Test()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);
	QueuePush(&q, 6);
	QueuePush(&q, 7);
	QueuePrint(&q);
	printf("the size of queue: %d\n", QueueSize(&q));

	QueuePop(&q);
	QueuePop(&q);
	QueuePop(&q);
	QueuePop(&q);
	QueuePrint(&q);
	printf("the size of queue: %d\n", QueueSize(&q));
	printf("The number of front: %d\n", QueueFront(&q));
	printf("The number of back: %d\n", QueueBack(&q));
	QueueDestroy(&q);

}

最后更新： 2019年05月16日 22:15

原始链接： http://CQolive.github.io/2019/05/16/栈和队列/

赏

× 请我吃糖~