데이터 구조 스 택 과 대기 열의 c 언어 구현

1. 스 택 이란 무엇 입 니까? 스 택 은 어떤 특성 이 있 습 니까?스 택: 특수 한 선형 표 입 니 다. 그 중에서 고정된 한 끝 에 만 요 소 를 삽입 하고 삭제 할 수 있 습 니 다. 데이터 삽입 과 삭제 작업 을 하 는 한 끝 을 스 택 지붕 이 라 고 하고 다른 한 끝 을 스 택 지붕 이 라 고 합 니 다.스 택 에 있 는 데이터 요 소 는 후진 후 나 오 는 원칙 (LIFO) 을 지 킵 니 다.스 택: 스 택 의 삽입 작업 을 스 택 에 들 어가 고 스 택 에 들 어가 고 데이터 가 스 택 에서 스 택 을 나 오 는 것 이 라 고 합 니 다. 스 택 의 삭제 작업 을 스 택 이 라 고 합 니 다. 데 이 터 를 내 는 것 도 스 택 에서 나 옵 니 다.
2. C 언어 로 동적 스 택 구현

#pragma once

typedef int SDataType;
typedef struct Stack
{
	int* _array;
	int _capacity;
	int _size;
}Stack;

void StackInit(Stack* ps);
void StackPush(Stack* ps, SDataType data);
void StackPop(Stack* ps);
SDataType StackTop(Stack* ps);
int StackSize(Stack* ps);
int StackEmpty(Stack* ps);
void StackDestroy(Stack* ps);

#include 
#include 
#include "0514.h"
#include 

void StackInit(Stack* ps)
{
	ps->_capacity = 4;
	ps->_size = 0;
	int *_arr = (int *)malloc(sizeof(int) * (ps->_capacity));
	if (_arr == NULL)
	{
		assert(0);
	}
	ps->_array = _arr;
}
void StackPush(Stack* ps, SDataType data)
{
	assert(ps);
	if (ps->_size == ps->_capacity)
	{
		ps->_capacity = ps->_capacity * 2;
		int * new_arr = (int *)malloc(sizeof(int) * (ps->_capacity));
		if (new_arr == NULL)
		{
			assert(0);
		}
		for (int i = 0; i < ps->_size; ++i)
		{
			new_arr[i] = ps->_array[i];
		}
		ps->_array = new_arr;
	}
	ps->_array[ps->_size] = data;
	ps->_size++;
}
void StackPop(Stack* ps)
{
	assert(ps);
	if (ps->_size == 0)
	{
		return 0;
	}
	ps->_size--;
}
SDataType StackTop(Stack* ps)
{
	assert(ps);
	if (ps->_size == NULL)
	{
		return -1;
	}
	else
	{
		return ps->_array[ps->_size - 1];
	}
}
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_size;
}
int StackEmpty(Stack* ps)
{
	assert(ps);
	if (ps->_size == 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_array);
	ps->_array = NULL;
}
int main()
{
	Stack ps;
	StackInit(&ps);
	StackPush(&ps, 1);
	StackPush(&ps, 2);
	StackPush(&ps, 3);
	StackPush(&ps, 4);
	StackPush(&ps, 5);
	StackPush(&ps, 6);
	StackPop(&ps);
	StackPop(&ps);
	int tmp = StackTop(&ps);
	printf("%d
", tmp);
	int size = StackSize(&ps);
	printf("%d
", size);
	StackDestroy(&ps);
	system("pause");
	return 0;
}

3. 스 택 과 프로그램 이 실 행 될 때의 스 택 구역 은 어떤 차이 가 있 습 니까?스 택 구역 은 메모리 공간 이 고 스 택 은 후진 에서 먼저 나 온 데이터 구조 스 택 구역 은 스 택 의 구조 사상 을 사용 하여 만 든 메모리 입 니 다.
4. 왜 재 귀 프로그램 을 순환 으로 바 꿀 때 스 택 을 사용 해 야 합 니까?재 귀 프로그램의 사상 은 스 택 과 같 습 니 다. 먼저 재 귀 함수 에 들 어간 후에 종료 합 니 다.
5. 대기 열 이 무엇 입 니까? 대기 열 은 어떤 특성 이 있 습 니까?창고 와 대열 은 어떤 차이 가 있 습 니까?대기 열: 한 단락 에서 만 데이터 삽입 작업 을 할 수 있 습 니 다. 다른 한 끝 에서 데 이 터 를 삭제 하 는 특수 선형 표 입 니 다. 대기 열 은 먼저 들 어 가 는 특성 을 가지 고 대기 열 에 들 어 갑 니 다. 삽입 작업 을 하 는 한 끝 을 대기 열 이 라 고 합 니 다. 삭제 작업 을 하 는 한 끝 은 대기 열 이 됩 니 다.
6. C 언어 로 대기 열 을 만 드십시오.

#pragma once
typedef int QDataType;
typedef struct QNode
{
	struct QNode* _pNext;
	QDataType _data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;
void QueueInit(Queue* q);
void QueuePush(Queue* q, QDataType data);
void QueuePop(Queue* q);
QDataType QueueFront(Queue* q);
QDataType QueueBack(Queue* q);
int QueueSize(Queue* q);
int QueueEmpty(Queue* q);
void QueueDestroy(Queue* q);

#include 
#include 
#include 
#include "0515.h"

void QueueInit(Queue* q)
{
	if (q == NULL)
	{
		return 0;
	}
	q->head = NULL;
	q->tail = NULL;
}
QNode* BuyNewNode(QDataType data)
{
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		assert(0);
	}
	newNode->_data = data;
	newNode->_pNext = NULL;
	return newNode;
}
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* curNode = NULL;
	if (QueueEmpty(q))
	{
		q->head = BuyNewNode(data);
		q->tail = q->head;
	}
	else
	{
		q->tail->_pNext = BuyNewNode(data);
		q->tail = q->tail->_pNext;
	}
}
void QueuePop(Queue* q)
{
	assert(q);
	if (QueueEmpty(q))
	{
		return 0;
	}
	else
	{
		QNode* delNode = q->head;
		q->head = q->head->_pNext;
		free(delNode);
		delNode = NULL;
	}
}
QDataType QueueFront(Queue* q)
{
	assert(q);
	if (QueueEmpty(q))
	{
		return 0;
	}
	return q->head->_data;
}
QDataType QueueBack(Queue* q)
{
	assert(q);
	if (QueueEmpty(q))
	{
		return 0;
	}
	return q->tail->_data;
}
int QueueSize(Queue* q)
{
	assert(q);
	QNode* curNode = q->head;
	int count = 0;
	while (curNode)
	{
		curNode = curNode->_pNext;
		++count;
	}
	return count;
}
int QueueEmpty(Queue* q)
{
	assert(q);
	if (q->head == NULL)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
void QueueDestroy(Queue* q)
{
	assert(q);
	while (!QueueEmpty(q))
	{
		QueuePop(q);
	}
}
int main()
{
	Queue q;
	int front = 0,size = 0;
	int back = 0;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	front = QueueFront(&q);
	back = QueueBack(&q);
	printf("front=%d tail=%d
",front,back);
	size = QueueSize(&q);
	printf("size=%d
", size);
	QueuePop(&q);
	front = QueueFront(&q);
	printf("front=%d
", front);
	size = QueueSize(&q);
	printf("size=%d
", size);
	QueueDestroy(&q);
	system("pause");
	return 0;
}