資料結構 之 棧（Stack）的實作及簡單操作

棧是限定僅在表尾進行插入和删除操作的線性表，由于棧隻能在尾進行插入和删除，是以這裡我們選用順序表來實作棧更友善快捷一點

對于棧我們要做的有棧的初始化，入棧，出棧，檢視棧頂元素，檢視棧内元素個數，清空棧，列印棧

在Stack.h:中對棧相關接口函數進行聲明以及對棧的結構體進行定義

Stack.h:

#pragma once
#define NUM 50//棧的大小
typedef int DataType;

typedef struct Stack
{
	DataType* _array;
	size_t	_top; //棧頂 
	size_t	_end;
}Stack;

// 棧的實作接口 
void StackInit(Stack* s);//棧的初始化
void StackPush(Stack* s, DataType x);//入棧
void StackPop(Stack* s);//出棧
DataType StackTop(Stack* s);//檢視棧頂元素
size_t StackSize(Stack* s);//棧内元素個數
int StackEmpty(Stack* s);//清空棧
void StackPrintf(Stack* s);//列印棧内元素(由棧底到棧頂)
           

這裡用宏定義棧的大小

接着在Stack.c中對相關接口函數一一實作

Stack.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"Stack.h"

void StackInit(Stack* s)//初始化棧
{
	s->_array = (DataType*)malloc(sizeof(DataType)*NUM);//malloc申請記憶體空間
	if (s->_array != NULL)
	{
		s->_end = s->_top = 0;
		return;
	}
	printf("棧初始化失敗！！");
	return;
}

void StackPush(Stack* s, DataType x)//入棧
{
	assert(s);
	if (s->_top == NUM)
	{
		printf("stack overflow");//棧溢出
		return;
	}
	s->_array[s->_top] = x;
	s->_top++;
}

void StackPop(Stack* s)//出棧
{
	assert(s);
	s->_top--;
}

DataType StackTop(Stack* s) //棧頂元素
{
	assert(s);
	if (s->_top == 0)
	{
		printf("棧為空！！");
		return -1;
	}
	else
		return s->_array[s->_top- 1];
}

size_t StackSize(Stack* s)//棧内元素個數
{
	assert(s);
	return s->_top;
}

int StackEmpty(Stack* s)//清空棧
{
	s->_top = 0;
	return 0;
}

void StackPrintf(Stack* s)//列印棧内元素
{
	assert(s);
	rsize_t i = 0;
	for (i = 0; i < s->_top; i++)
	{
		printf("%-3d", s->_array[i]);
	}
	printf("\n");
}

int main()
{
	Stack s;
	StackInit(&s);
	StackPush(&s, 1);
	StackPush(&s, 2);
	StackPush(&s, 3);
	StackPush(&s, 4);
	StackPush(&s, 5);
	StackPop(&s);
	StackPush(&s, 6);
	printf("棧内元素為：");
	StackPrintf(&s);
	printf("棧内元素個數為：%d\n", StackSize(&s));
	printf("棧頂元素為：%d\n", StackTop(&s));
	system("pause");
	return 0;
}
           

這裡我們用宏定義棧的大小，需要注意的是因為棧的大小是一定的，是以在入棧時候要判斷棧是否是滿的，這裡如果不加以判斷就有可能造成通路越界，在這裡當棧滿時 螢幕列印 stack overflow

關于stack overflow這個問題我們在平時寫遞歸時候如果不慎寫出死循環之類的問題經常程式因為棧溢出而挂掉

int main()
{
	Stack s;
	StackInit(&s);
	StackPush(&s, 1);
	StackPush(&s, 2);
	StackPush(&s, 3);
	StackPush(&s, 4);
	StackPush(&s, 5);
	StackPop(&s);
	StackPush(&s, 6);
	printf("棧内元素為：");
	StackPrintf(&s);
	printf("棧内元素個數為：%d\n", StackSize(&s));
	printf("棧頂元素為：%d\n", StackTop(&s));
	system("pause");
	return 0;
}
           

簡單的對相關接口進行測試