데이터 구조 | | 창고 와 대기 열 (기본 인터페이스의 실현)

창고 와 대열
주의: 스 택 과 대기 열 에 대해 깊이 공부 해 야 합 니 다. 이 두 데이터 구 조 는 데이터 구조의 기초 라 고 할 수 있 습 니 다. 뒤의 많은 데이터 구조 에 사용 해 야 합 니 다. 그리고 면접 시험 이라는 부분 도 특히 많 기 때문에 스 택 과 대기 열 에 대해 소홀히 해 서 는 안 됩 니 다. 명심 하 세 요!
본 논문 에서 쓴 스 택 은 순서 스 택 이 고 대기 열 은 체인 대기 열 입 니 다.
왜 순서 스 택 과 체인 대기 열 을 써 야 합 니까?다음 블 로 그 를 볼 수 있 습 니 다: 링크 주소:https://blog.csdn.net/qq_40399012/article/details/81835465
창고.
스 택: 특수 한 선형 표 로 고정된 한 끝 에 만 요 소 를 삽입 하고 삭제 할 수 있 습 니 다.데이터 삽입 과 삭제 작업 을 하 는 한 끝 을 스 택 지붕 이 라 고 하고 다른 한 끝 을 스 택 바닥 이 라 고 합 니 다.어떠한 요소 도 포함 하지 않 는 스 택 을 빈 스 택 이 라 고 부 르 고 스 택 은 선진 적 인 후에 나 오 는 선형 표 라 고도 부른다.
스 택 은 순서 스 택 과 체인 스 택 으로 나 뉜 다.
메모: 순서 스 택 의 모든 작업 시간 복잡 도 는 O (1) 입 니 다.
순서 스 택 에 대한 기본 작업
제1 부분: 헤더 파일 Stack. h

#ifndef __STACK_H__
#define __STACK_H__
​
#include 
#include 
#include 
​
typedef int DataType;
​
typedef struct Stack
{
    DataType* stack;
    int capacity;
    int top;
}Stack;
​
void StackInit(Stack* ps);
void StackDestory(Stack* ps);
​
void StackPush(Stack* ps, DataType d);
void StackPop(Stack* ps);
DataType StackTop(Stack* ps);
int StackEmpty(Stack* ps);
int StackSize(Stack* ps);
​
​
​
#endif //__STACK_H__

 
두 번 째 부분: 함수 실현 부분: Stack. c

#include "Stack.h"
​
void StackInit(Stack* ps)
{
    assert(ps);
​
    ps->stack = (DataType*)malloc(sizeof(DataType)*3);
    ps->top = -1;//        
    ps->capacity = 3;
}
​
void StackDestory(Stack* ps)
{
    assert(ps);
​
    ps->stack = NULL;
    ps->top = -1;
    ps->capacity = 0;
}
​
void AddCapacity(Stack* ps)
{
    assert(ps);
​
    ps->stack = (DataType*)realloc(ps->stack, sizeof(DataType)*ps->capacity * 2);
    if (ps->stack == NULL)
    {
        perror("realloc size");
    }
    ps->capacity *= 2;
}
​
void StackPush(Stack* ps, DataType d)
{
    assert(ps);
​
    //            
    if (ps->top == ps->capacity - 1) //  
    {
        //    
        AddCapacity(ps);
        //    
        ps->stack[++ps->top] = d;
    }
    else
    {
        //      
        ps->stack[++ps->top] = d;
    }
}
​
void StackPop(Stack* ps)
{
    assert(ps);
    
    ps->top--;
}
DataType StackTop(Stack* ps)
{
    assert(ps);
​
    return ps->stack[ps->top];
}
​
//  0
//   1
int StackEmpty(Stack* ps)
{
    assert(ps);
​
    return ps->top == -1 ? 0 : 1;
}
​
int StackSize(Stack* ps)
{
    assert(ps);
​
    int size = ps->top + 1;
    return size;
}

 
세 번 째 부분: 테스트 부분 test. c

#include "Stack.h"
​
void TestStack()
{
    Stack s = { NULL };
    StackInit(&s);
    StackPush(&s, 1);
    StackPush(&s, 2);
    StackPush(&s, 3);
    StackPush(&s, 4);
    printf("    :%d
", StackSize(&s));
    while (StackEmpty(&s))
    {
        printf("%d ", StackTop(&s));
        StackPop(&s);
    }
    StackDestory(&s);
    printf("
");
}
​
int main()
{
    TestStack();
    return 0;    
}

 
대열
대기 열: 한 끝 에 만 삽입 작업 을 할 수 있 고 다른 한 끝 에 서 는 삭제 작업 을 할 수 있 는 특수 선형 표 입 니 다.삽입 작업 을 하 는 한 끝 을 팀 꼬리 라 고 하고 삭제 작업 을 하 는 한 끝 을 팀 머리 라 고 합 니 다.대열 은 선진 적 인 선발 특성 을 가지 고 있다.
체인 대기 열 에 대한 기본 동작
제1 부분: 헤더 파일 Queue. h

#ifndef __QUEUE_H__
#define __QUEUE_H__
​
#include 
#include 
#include 
​
typedef int DataType;
​
typedef struct QueueNode
{
    DataType data;
    struct QueueNode* next;
}QueueNode;
​
typedef struct Queue
{
    QueueNode* front;
    QueueNode* rear;
}Queue;
​
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
​
void QueuePush(Queue* pq, DataType d);
void QueuePop(Queue* pq);
DataType QueueFront(Queue* pq);
int QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
​
#endif //__QUEUE_H__

 
두 번 째 부분: 함수 실현 부분 Queue. c

#include "Queue.h"
​
void QueueInit(Queue* pq)
{
    assert(pq);
    
    pq->front = NULL;
    pq->rear = NULL;
}
​
void QueueDestory(Queue* pq)
{
    assert(pq);
​
    QueueNode* cur = pq->front;
    while (cur)
    {
        QueueNode* del = cur;
        cur = cur->next;
        free(del);
        del = NULL;
    }
    pq->front = NULL;
    pq->rear = NULL;
}
​
QueueNode* BuyNode(DataType d)
{
    QueueNode* newNode = (QueueNode*)malloc(sizeof(DataType));
    if (newNode == NULL)
    {
        perror("Buy newNode");
    }
​
    newNode->data = d;
    newNode->next = NULL;
    return newNode;
}
​
void QueuePush(Queue* pq, DataType d)
{
    assert(pq);
​
    //     
    if (pq->front == NULL)
    {
        QueueNode* newNode = BuyNode(d);
        pq->rear = newNode;
        pq->front = pq->rear;
    }
    else
    {
        QueueNode* newNode = BuyNode(d);
        pq->rear->next = newNode;
        pq->rear = newNode;
    }
}
​
void QueuePop(Queue* pq)
{
    assert(pq);
​
    pq->front = pq->front->next;
}
​
DataType QueueFront(Queue* pq)
{
    assert(pq);
​
    return pq->front->data;
}
​
//  0
//   1
int QueueEmpty(Queue* pq)
{
    assert(pq);
​
    return pq->front == NULL ? 0 : 1;
}
​
int QueueSize(Queue* pq)
{
    int size = 0;
    assert(pq);
​
    QueueNode* cur = pq->front;
    while (cur)
    {
        cur = cur->next;
        size++;
    }
    return size;
}

 
세 번 째 부분: 테스트 부분 test. c

#include "Queue.h"
​
void TestQueue()
{
    Queue q = { NULL };
    QueueInit(&q);
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);
    printf("     :%d
", QueueSize(&q));
    while (QueueEmpty(&q))
    {
        printf("%d ", QueueFront(&q));
        QueuePop(&q);
    }
    QueueDestory(&q);
    printf("
");
}
​
int main()
{
    TestQueue();
    return 0;    
}