스 택 과 대기 열 설명 및 구현
창고
스 택: 특수 한 선형 표 로 고정된 한 끝 에 만 요 소 를 삽입 하고 삭제 할 수 있 습 니 다.데이터 삽입 과 삭제 작업 을 하 는 한 끝 을 스 택 지붕 이 라 고 하고 다른 한 끝 을 스 택 바닥 이 라 고 합 니 다.스 택 에 있 는 데이터 요 소 는 후진 선 출 LIFO (Last In First Out) 의 원칙 을 준수 합 니 다.
스 택: 스 택 의 삽입 작업 을 스 택 / 스 택 / 스 택 에 들 어가 고 데 이 터 는 스 택 꼭대기 에 있 습 니 다.
스 택 나 가기: 스 택 의 삭제 작업 을 스 택 나 가기 라 고 합 니 다.데이터 도 창고 꼭대기 에 있 습 니 다.
Stack. h 중 일부 성명
#include(1). 스 택 초기 화
(1). 스 택 동적 으로 메모리 공간 을 엽 니 다 (2). 스 택 의 맨 아래 표 시 를 0 으로 설정 합 니 다. 즉, 스 택 의 맨 아래 표 시 는 top 이 스 택 의 유효 요소 의 개 수 를 대표 합 니 다 (3). 스 택 의 시작 용량 을 설정 합 니 다.
void StackInit(Stack* pst)
{
assert(pst);
pst->a = (STDataType*)malloc(sizeof(STDataType) * INIT_CAPACITY);
if (pst->a == NULL)
{
printf("malloc failed
");
exit(-1);
}
pst->top = 0;
pst->capacity = INIT_CAPACITY;
}
(2) 입 점
(1). 스 택 공간 이 가득 차 면 realloc 함수 동적 용량 증가 (2) 를 사용 합 니 다. 스 택 에 들 어간 데 이 터 를 스 택 에 넣 습 니 다 (3). 스 택 맨 위 에 표 시 된 + 1
void StackPush(Stack* pst, STDataType x)
{
assert(pst);
//
if (pst->top == pst->capacity)
{
pst->capacity *= 2;
STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * pst->capacity);
if (tmp == NULL)
{
printf("realloc failed
");
exit(-1);
}
pst->a = tmp;
}
pst->a[pst->top] = x;
pst->top++;
}
(3). 출고
(1). 스 택 이 비어 있 는 지 판단 하기 (2). 스 택 맨 아래 표 - 1
void StackPop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));
pst->top--;
}
(4). 스 택 상단 요소 가 져 오기
(1). 창고 가 비어 있 는 지 판단 하기 (2). 창고 꼭대기 요 소 를 가 져 오기
STDataType StackTop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));
return pst->a[pst->top - 1];
}
(5). 스 택 의 유효 요소 개 수 를 가 져 옵 니 다.
스 택 맨 아래 표 시 는 스 택 의 유효 요소 갯 수 입 니 다.
int StackSize(Stack* pst)
{
assert(pst);
return pst->top;
}
(6). 스 택 이 비어 있 는 지 확인 합 니 다. 비어 있 으 면 true 로 돌아 갑 니 다. 비어 있 지 않 으 면 false 로 돌아 갑 니 다.
스 택 맨 아래 표 시 는 스 택 의 유효 요소 개 수 를 대표 하기 때문에 스 택 맨 아래 표 시 를 0 으로 판단 하면 됩 니 다.
bool StackEmpty(Stack* pst)
{
assert(pst);
return pst->top == 0;
}
(7). 창고 소각
(1). 스 택 의 맨 아래 표지 와 스 택 의 용량 을 0 (2) 으로 설정 합 니 다. 동적 으로 열 린 메모리 공간 을 방출 합 니 다.
void StackDestroy(Stack* pst)
{
assert(pst);
pst->top = pst->capacity = 0;
free(pst->a);
pst->a = NULL;
}
(8). 전체 코드 구현
Stack.h
#pragma once
#includeStack.c
#include"Stack.h"
//
void print(Stack* pst)
{
assert(pst);
int i = 0;
for (i = 0; i < pst->top; i++)
{
printf("%d ", pst->a[i]);
}
printf("
");
}
// ， true, false
bool StackEmpty(Stack* pst)
{
assert(pst);
return pst->top == 0;
}
//
void StackInit(Stack* pst)
{
assert(pst);
pst->a = (STDataType*)malloc(sizeof(STDataType) * INIT_CAPACITY);
if (pst->a == NULL)
{
printf("malloc failed
");
exit(-1);
}
pst->top = 0;
pst->capacity = INIT_CAPACITY;
}
//
void StackPush(Stack* pst, STDataType x)
{
assert(pst);
//
if (pst->top == pst->capacity)
{
pst->capacity *= 2;
STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * pst->capacity);
if (tmp == NULL)
{
printf("realloc failed
");
exit(-1);
}
pst->a = tmp;
}
pst->a[pst->top] = x;
pst->top++;
}
//
void StackPop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));
pst->top--;
}
//
STDataType StackTop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));
return pst->a[pst->top - 1];
}
//
int StackSize(Stack* pst)
{
assert(pst);
return pst->top;
}
//
void StackDestroy(Stack* pst)
{
assert(pst);
pst->top = pst->capacity = 0;
free(pst->a);
pst->a = NULL;
}
TestStack.c
#include"Stack.h"
void TestStack01()
{
Stack st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
print(&st);
StackPop(&st);
print(&st);
StackPop(&st);
StackPop(&st);
StackPop(&st);
StackPop(&st);
StackDestroy(&st);
}
int main()
{
TestStack01();
}
대열
대기 열: 한 끝 에 만 데 이 터 를 삽입 할 수 있 고 다른 한 끝 에서 데 이 터 를 삭제 하 는 특수 선형 표 입 니 다. 대기 열 은 먼저 FIFO (First In First Out) 를 가지 고 있 습 니 다.
입 대기 열: 삽입 작업 을 하 는 한 끝 을 팀 꼬리 라 고 합 니 다.
출력 대기 열: 삭제 작업 을 하 는 한 끝 을 팀 헤드 라 고 합 니 다.
Queue. h 중 일부 성명
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
}Queue;
(1). 대기 열 초기 화
팀 헤드 와 팀 꼬리 지침 을 비 워 두다.
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
(2). 대기 열 에 들 어가 기
(1). 대기 열 이 비어 있 으 면 head 와 tail 포인터 가 새로운 신청 의 끝 점 을 가리 키 게 합 니 다 (2). 대기 열 이 비어 있 지 않 으 면 tail - > next 가 새로운 신청 의 끝 점 을 가리 키 고 tail 을 새로운 꼬리 로 이동 합 니 다 (tail = tail - > next)
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
if (newNode == NULL)
{
printf("malloc failed
");
exit(-1);
}
newNode->data = x;
newNode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newNode;
}
else
{
pq->tail->next = newNode;
pq->tail = pq->tail->next;
}
}
(3).
대열 을 나 서 는 것 은 삭제 하 는 것 과 같다.
(1). 대기 열 이 비어 있 는 지, 비어 있 는 지 판단 합 니 다. (2) 두 번 째 노드 의 주소 (3) 를 저장 합 니 다. 첫 번 째 노드 (4) 를 풀 어 줍 니 다. head 지침 을 바 꾸 어 새 머리 를 가리 키 도록 합 니 다.
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
(4). 대기 열 머리 요소 가 져 오기
(1). 대기 열 이 비어 있 는 지 여 부 를 판단 하고 빈 단언 으로 오 류 를 알 립 니 다 (2). head - > data 로 돌아 갑 니 다.
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
(5). 줄 의 끝 요 소 를 가 져 옵 니 다.
(1). 대기 열 이 비어 있 는 지 여 부 를 판단 하고 빈 단언 으로 오 류 를 알 립 니 다 (2). tail - > data 로 돌아 갑 니 다.
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
(6). 대기 열 에 있 는 유효 요소 개 수 를 가 져 옵 니 다.
링크 를 옮 겨 다 니 며 링크 요소 의 개 수 를 얻 으 면 됩 니 다.
int QueueSize(Queue* pq)
{
assert(pq);
int count = 0;
QueueNode* cur = pq->head;
while (cur)
{
count++;
cur = cur->next;
}
return count;
}
(7). 대기 열 이 비어 있 는 지 확인 합 니 다. 비어 있 으 면 true 로 돌아 갑 니 다. 비어 있 지 않 으 면 false 입 니 다.
헤드 포인터 가 비어 있 는 지 확인 하면 됩 니 다.
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
(8). 대기 열 폐기
링크 를 옮 겨 다 니 며 하나씩 없 애 면 됩 니 다.
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
}
(9). 전체 코드 구현
Queue.h
#pragma once
#includeQueue.c
#include"Queue.h"
//
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
//
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
if (newNode == NULL)
{
printf("malloc failed
");
exit(-1);
}
newNode->data = x;
newNode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newNode;
}
else
{
pq->tail->next = newNode;
pq->tail = pq->tail->next;
}
}
//
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
//
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
//
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
//
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
//
void QueueDestroy(Queue* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
}
//
int QueueSize(Queue* pq)
{
assert(pq);
int count = 0;
QueueNode* cur = pq->head;
while (cur)
{
count++;
cur = cur->next;
}
return count;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
