淺析順序結(jié)構(gòu)存儲(chǔ)的棧

來(lái)源：本站原創(chuàng)|時(shí)間：2020-01-10|欄目：C語(yǔ)言|點(diǎn)擊：次

棧定義：僅限在表尾進(jìn)行插入和刪除的線性表

棧的特點(diǎn)：

1）一般來(lái)說(shuō)能在表尾進(jìn)行進(jìn)棧和出棧的數(shù)據(jù)

2）先進(jìn)后出（last in first out ）

3）棧會(huì)有棧頂，棧底，通常棧底為高地址，棧頂為高地址，如下圖所示

操作系統(tǒng)一般會(huì)在內(nèi)存劃出一塊，專(zhuān)門(mén)用于棧操作，當(dāng)然這個(gè)跟普通的操作有些區(qū)別：比如存放數(shù)組，地址是增加的；但是在存入數(shù)據(jù)到棧，地址則是不斷減小的

棧的存儲(chǔ)結(jié)構(gòu)：

復(fù)制代碼代碼如下:

typedef struct _SQSTACK
{
 SElemType* base;
 SElemType* top;
 int stacksize;
}
SqStack;

數(shù)據(jù)定義：

復(fù)制代碼代碼如下:

//默認(rèn)的存儲(chǔ)空間的大小和空間增長(zhǎng)大小
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10

//存儲(chǔ)數(shù)據(jù)的類(lèi)型定義
#ifndef INT_TYPE
#define INT_TYPE
#endif // INT_TYPE

#ifdef INT_TYPE
typedef  int  SElemType;
#elif defined FLOAT_TYPE
typedef  float SElemType;
#elif defined STRING_TYPE
typedef  char* SElemType;
#elif defined STRUCT_TYPE
typedef  void* SElemType;
#endif

棧的操作，會(huì)涉及到初始化棧，銷(xiāo)毀棧，進(jìn)棧（入棧），出棧，還有判斷?？眨瑮４笮?，以及清空棧，如下：
棧的初始化：

復(fù)制代碼代碼如下:

//初始化棧
int InitStack(SqStack *S)
{
 S->base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
 if (!S->base)
 {
  return -1;
 }
 S->top = S->base;
 S->stacksize = STACK_INIT_SIZE;
 return 0;
}

棧才初始化，里面還沒(méi)有數(shù)據(jù)，這時(shí)候top，base都指向分配空間的基地址，表示?？?BR>銷(xiāo)毀棧：

復(fù)制代碼代碼如下:

//銷(xiāo)毀棧
int DestroyStack(SqStack *S)
{
 if (S->base)
 {
  free(S->base);
  S->base = NULL;
  S->top = NULL;
  S->stacksize = 0;
 }
 return 0;
}

如果棧存在，就銷(xiāo)毀地址空間，將棧尺寸置0
進(jìn)棧：

復(fù)制代碼代碼如下:

int Push(SqStack *S, const SElemType data)
{
assert(S->base != NULL);
if (S->top - S->base >= STACK_INIT_SIZE)
{
  S->base = (SElemType*)realloc(S->base,
   (STACK_INIT_SIZE + STACK_INCREMENT) * sizeof(SElemType));
  if (!S->base)
  {
   return -1;
  }
  S->top = S->base + S->stacksize;
  S->stacksize += STACK_INCREMENT;
}
*S->top++ = data;

return 0;
}

如果棧存在，就銷(xiāo)毀地址空間，將棧尺寸置0
進(jìn)棧：

復(fù)制代碼代碼如下:

return 0;
}

如果棧的大小大于已分配長(zhǎng)度，重新分配空間，并使棧頂重新指向新的位置，之后就將數(shù)據(jù)存入當(dāng)前棧頂指向的位置，然后棧頂+1
出棧：

復(fù)制代碼代碼如下:

//出棧
int Pop(SqStack *S, SElemType *data)
{
 assert(S->base != NULL);
 if (S->base == S->top)
 {
  return -1;
 }
 *data = *(--S->top);

 return 0;
}

首先將棧頂位置-1，然后取得當(dāng)前位置的值
以下為輔助函數(shù)，如下：

復(fù)制代碼代碼如下:

//棧是否為空
int IsStackEmpty(const SqStack &S)
{
 return ((S.base == S.top) ? true:false);
}

復(fù)制代碼代碼如下:

//得到棧的長(zhǎng)度
int GetStackLength(const SqStack &S)
{
assert(S.base != NULL);

return S.stacksize;
}

復(fù)制代碼代碼如下:

//清空棧
int ClearStack(SqStack *S)
{
assert(S->base != NULL);
if (S->base != S->top)
{
S->top = S->base;
}
S->stacksize = 0;

return 0;
}

上一篇：linux使用gcc編譯c語(yǔ)言共享庫(kù)步驟

欄目：C語(yǔ)言

下一篇：C語(yǔ)言判斷回文數(shù)的小例子

本文標(biāo)題：淺析順序結(jié)構(gòu)存儲(chǔ)的棧

本文地址：http://m.jygsgssxh.com/a1/Cyuyan/3825.html

更多C語(yǔ)言

雷火电竞-中国电竞赛事及体育赛事平台

C語(yǔ)言

淺析順序結(jié)構(gòu)存儲(chǔ)的棧

您可能感興趣的文章

閱讀排行

本欄相關(guān)

隨機(jī)閱讀