C語言-棧tack順序存儲和鍊式存儲

了解棧tack

棧也是一種特殊的線性表，棧的工作原理是先進後出，是以在對棧操作時隻能在棧頂操作。棧的插入操作，叫作入棧（壓棧），棧的删除操作，叫作出棧（彈棧）。

棧的順序存儲選擇尾部壓棧和彈棧時，不會涉及到數組元素的大量移動。

棧的鍊式存儲選擇在連結清單頭部入棧和出棧時，減少了數組元素的大量移動

注意：在棧的鍊式存儲中結點中涉及了指針變量，是以入棧的結點都需要malloc，在出棧時需要釋放結點記憶體

stack棧的順序存儲

棧的順序存儲類似線性表的順序存儲

//SeqStack.h
#pragma once
typedef void SeqStack;
//建立棧
SeqStack* SeqStack_Create(int capacity);
//銷毀棧
void SeqStack_Destroy(SeqStack* stack);
//清空棧
void SeqStack_Clear(SeqStack* stack);
//壓棧
int SeqStack_Push(SeqStack* stack, void* item);
//彈棧
void* SeqStack_Pop(SeqStack* stack);
//擷取棧頂元素
void* SeqStack_Top(SeqStack* stack);
//擷取棧的大小
int SeqStack_Size(SeqStack* stack);
//擷取棧的容量
int SeqStack_Capacity(SeqStack* list);
           

stack棧的鍊式存儲

//LinkStack.h
#pragma once
typedef void LinkStack;
//建立鍊棧
LinkStack* LinkStack_Create();
//銷毀鍊棧
void LinkStack_Destroy(LinkStack* stack);
//清空鍊棧
void LinkStack_Clear(LinkStack* stack);
//壓棧
int LinkStack_Push(LinkStack* stack, void* item);
//彈出
void* LinkStack_Pop(LinkStack* stack);
//擷取棧頂元素
void* LinkStack_Top(LinkStack* stack);
//擷取棧的大小
int LinkStack_Size(LinkStack* stack);
           

入棧出棧操作分析

入棧時需要為結點配置設定記憶體空間（鍊棧的結點包含了指向後繼結點的指針域）。同樣出棧時需要釋放為結點配置設定的記憶體。

//LinkStack.c
#pragma warning(disable : 4996)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "LinkStack.h"
#include "LinkList.h"

//棧中的結點去包含連結清單結點
typedef struct tag_LinkStackNode
{
    TLinkListNode node;
    void* item;
}TLinkStackNode;
//建立鍊棧
LinkStack * LinkStack_Create()
{
    LinkStack* temp = (LinkStack*)LinkList_Creat();
    return temp;
}
//銷毀棧
void LinkStack_Destroy(LinkStack* stack)
{
    LinkStack_Clear(stack);
    LinkList_Destroy((LinkList *)stack);
    return;
}
//清空棧
void LinkStack_Clear(LinkStack* stack)
{
    if (stack == NULL)
    {
        printf(" LinkStack_Clear err:stack = NULL");
        return;
	}
    //依次從棧頂彈出結點元素
    while (LinkStack_Size(stack) > 0)
    {
        LinkStack_Pop(stack);
    }
    return;
}
//入棧
int LinkStack_Push(LinkStack* stack, void* item)
{
    TLinkStackNode* temp = NULL;
    int ret = 0;
    if (stack == NULL || item == NULL)
    {
        printf(" LinkStack_Push err: stack = NULL || item = NULL");
        return -1;
    }
    temp = (TLinkStackNode *)malloc(sizeof(TLinkStackNode));//為結點配置設定記憶體
    if (temp == NULL)
    {
        return -2;
    }
    memset(temp, 0, sizeof(TLinkStackNode));//初始化結點
    temp->item = item;//儲存結點資料
    ret = LinkList_inster(stack, (TLinkListNode*)temp, 0);//入棧
    if (ret != 0)
    {
        printf(" LinkList_inster err:%d\n", ret);
        if (temp != NULL)
        {
            free(temp);
        }
        return ret;
    }
    return ret;
}
//出棧
void * LinkStack_Pop(LinkStack* stack)
{
    TLinkStackNode* temp = NULL;
    void *item = NULL;
    if (stack == NULL)
    {
        printf(" LinkStack_Pop err:stack = NULL");
        return NULL;
    }
    temp = (TLinkStackNode *)LinkList_Delete(stack, 0);//删除棧頂元素，并傳回結點
    if (temp != NULL)
    {
        item = temp->item;//擷取結點資料
        free(temp);//釋放結點
    }
    return item;//傳回結點資料
}
//擷取棧頂元素
void * LinkStack_Top(LinkStack* stack)
{
    TLinkStackNode* temp = NULL;
    if (stack == NULL)
    {
        printf(" LinkStack_Top err:stack = NULL");
        return NULL;
    }
    temp = (TLinkStackNode *)LinkList_Get(stack, 0);
    if (temp == NULL)
        return NULL;
    return temp->item;
}
//擷取棧的大小
int LinkStack_Size(LinkStack* stack)
{
    if (stack == NULL)
    {
        printf(" LinkStack_Size err:stack = NULL");
        return -1;
    }
    return LinkList_GetLength(stack);
}