C語言數(shù)據(jù)結(jié)構(gòu)－－棧

荔枝園子 2016-07-25

展開全文

1.  什么是棧

    棧其實就是一種線性表。只不過它有點(diǎn)特殊，它的特殊性主要體現(xiàn)在它是一種后進(jìn)先出(Last In First Out)的線性表，跟隊列剛好相對應(yīng)，隊列剛好是先進(jìn)先出(First In First Out)的在棧中只能在一端進(jìn)行操作，就是說保存數(shù)據(jù)和取出數(shù)據(jù)只能從線性表的一端進(jìn)行，一般地操作端我們稱之為棧頂，另一端則稱為棧底。

2.  棧的基本操作

棧的基本操作只有兩個：
入棧(push)：即將數(shù)據(jù)保存在棧頂。進(jìn)行該操作前，先修改棧頂指針，使其向上移動一個元素位置，然后將數(shù)據(jù)保存在棧頂指針?biāo)赶虻奈恢谩?br>出棧(pop)：即將棧頂?shù)臄?shù)據(jù)彈出，然后修改棧頂指針，使其指向棧中的下一個元素。
在棧中，只有棧頂元素是可以訪問的。

3.  兩種棧

一般地，棧使用兩種存儲表示方法。
順序棧：使用一組連續(xù)的內(nèi)存單元依次保存棧中的數(shù)據(jù)。一般情況下使用數(shù)組作為順序棧，序號為0的元素就是棧底，再定義一個變量來保存棧頂?shù)男蛱柤纯伞?br>鏈?zhǔn)綏＃菏褂面湵硇问絹肀４鏃Ｖ袀€元素的值，鏈表尾部(指向地址NULL)為棧底，鏈表的首部(head指針?biāo)赶虻脑?為棧頂。
兩種棧的最大區(qū)別就是順序棧是分布在一片連續(xù)的內(nèi)存單元里，而鏈?zhǔn)綏Ｒ话闶欠植荚诹闵⒌膬?nèi)存單元當(dāng)中。

接下來我們使用順序棧來實現(xiàn)一個保存學(xué)生姓名和年齡的小實例。下面我們來一步一步的縷一下整個思路。

1.要使用棧，那么我們首先應(yīng)該定義一個棧結(jié)構(gòu)

代碼:

//定義順序棧的結(jié)構(gòu)
typedef struct stack
{
  student data[SIZE+1];    //數(shù)據(jù)元素
  int top;              //棧頂
}SeqStack;

其中棧結(jié)構(gòu)里面包含了2個元素，一個是結(jié)構(gòu)體數(shù)組，數(shù)組名為data，其類型為student結(jié)構(gòu)體，用來保存學(xué)生的姓名和年齡。另一個整形變量top用來表示棧頂?shù)男蛱枴?/span>
2.定義好了棧結(jié)構(gòu)，接下來就應(yīng)該初始化棧。

代碼:

//初始化棧
SeqStack * SeqStackInit()
{
  SeqStack *p;
  if (p = (SeqStack *)malloc(sizeof(SeqStack)))         //申請棧內(nèi)存
  {
    p->top = 0;
    return p;
  }
  return NULL;             //申請內(nèi)存失敗返回空值
}

順序棧的初始化需要做2件事情：首先需要申請一片合適的內(nèi)存來保存棧中的數(shù)據(jù)，然后設(shè)置棧頂指針的值為0，表示這是一個空棧。
3. 釋放棧內(nèi)存

代碼:

 //釋放棧內(nèi)存
void SeqStackFree(SeqStack *s)
{
  if(s)
    free(s);
}

使用完畢，應(yīng)該及時釋放棧內(nèi)存，否則有可能造成內(nèi)存泄漏。
4. 判斷棧的當(dāng)前狀態(tài)

代碼:

//判斷棧的狀態(tài)
int SeqStackIsEmpty(SeqStack *s)                 //判斷棧是否為空
{
  return(s->top == 0);
}
void SeqStackClear(SeqStack *s)               //清空棧
{
  s->top = 0;
}
void SeqStackIsFull(SeqStack *s)      //判斷棧是否已滿
{
  return(s->top == SIZE);
}

在對棧進(jìn)行操作之前通常先要判斷一下棧的當(dāng)前狀態(tài)，再決定如何進(jìn)行操作。入棧前應(yīng)該先判斷棧是否已滿，出棧前應(yīng)該判斷棧是否為空。
5. 入棧

代碼:

 //入棧
int SeqStackPush(SeqStack *s, student data)     //入棧操作
{
  if ((s->top+1) > SIZE)
  {
    printf("棧溢出！\n");
    return 0;
  }
  s->data[++s->top] = data;         //將元素入棧
  return 1;
}

首先判斷top是否大于等于SIZE，如果結(jié)果為真，那么給出溢出提示。
第二設(shè)置top=top+1，棧頂指針加1，指向入棧地址，在這里我們可以想一想前面棧的基本操作當(dāng)中所說的入棧需要做些什么事情。
最后將入棧元素保存到top指向的位置。在這里注意++和->這兩個運(yùn)算符，其中++是個前綴運(yùn)算符，他的優(yōu)先級低于->運(yùn)算符。請注意前綴++和后綴++的優(yōu)先級是不一樣的。
6. 出棧

代碼:

//出棧
student SeqStackPop(SeqStack *s)     //出棧操作
{
  if (s->top == 0)
  {
    printf("棧為空！\n");
    exit(0);
  }
  return (s->data[s->top--]);            //彈出棧頂元素
}

首先判斷top是否小于等于0.如果結(jié)果為真，則提示棧為空。
第二將棧頂指針top所指向位置的元素返回。
最后設(shè)置top=top-1,使棧頂減1，指向棧的下一個元素。
在這里同樣可以參考一下上面棧的基本操作當(dāng)中關(guān)于出棧的操作。
7. 獲取棧頂元素

代碼:

//獲取棧頂?shù)脑?br>student SeqStackPeek(SeqStack *s)          //讀取棧頂元素
{
  if (s->top == 0)         //判斷棧是否為空
  {
    printf("棧為空！");
    exit(0);
  }
  return (s->data[s->top]);  //返回棧頂元素
}

使用出棧函數(shù)操作后，原來棧頂?shù)脑鼐捅粡棾隽?，也就是說出棧后原來棧頂?shù)脑鼐筒淮嬖诹?。但是在有些時候我們可能會需要獲取棧頂?shù)脑?，但又需要繼續(xù)保留該元素在棧頂，這是就用到了這個函數(shù)，注意它與SeqStackPop函數(shù)的區(qū)別，該函數(shù)只是返回當(dāng)前棧頂?shù)脑?，并不修改棧頂指針，所以獲取棧頂元素后，原來的棧頂依然存在。
有了上面足夠的知識，我們開始在main函數(shù)中實現(xiàn)一下這個小實例的具體操作。

以下是SeqStackTest.c的代碼

代碼:

#include <stdio.h>
#include <stdlib.h>
#define SIZE 50
typedef struct  
{
  char name[15];
  int age;
}student;
#include "SeqStack.h"
int main()
{
  SeqStack *stack;
  student pushstudent,popstudent;             //定義棧操作的元素
  stack = SeqStackInit();      //初始化棧
  printf("入棧操作！\n");
  printf("輸入姓名 年齡進(jìn)行入棧操作：\n");
  scanf("%s%d",pushstudent.name,&pushstudent.age);
  SeqStackPush(stack,pushstudent);             //入棧
  printf("輸入姓名 年齡進(jìn)行入棧操作：\n");
  scanf("%s%d",pushstudent.name,&pushstudent.age);
  SeqStackPush(stack,pushstudent);             //入棧
  printf("\n出棧操作:\n按任意鍵進(jìn)行出棧操作：\n");
  getchar();
  popstudent = SeqStackPop(stack);        //出棧
  printf("出棧的數(shù)據(jù)是:\n");   
  printf("%10s%10s\n","姓名","年齡");
  printf("%10s%10d\n",popstudent.name,popstudent.age);
  printf("再按任意鍵進(jìn)行出棧操作：");
  getchar();
  popstudent = SeqStackPop(stack);    //出棧
  printf("出棧的數(shù)據(jù)是:\n");   
  printf("%10s%10s\n","姓名","年齡");
  printf("%10s%10d\n",popstudent.name,popstudent.age);
  SeqStackFree(stack);          //釋放棧所用的內(nèi)存
  getchar();
  return 0;
}

下面是SeqStack.h的代碼

代碼:

//定義順序棧的結(jié)構(gòu)
typedef struct stack
{
  student data[SIZE+1];    //數(shù)據(jù)元素
  int top;              //棧頂
}SeqStack;
//初始化棧
SeqStack * SeqStackInit()
{
  SeqStack *p;
  if (p = (SeqStack *)malloc(sizeof(SeqStack)))         //申請棧內(nèi)存
  {
    p->top = 0;
    return p;
  }
  return NULL;             //申請內(nèi)存失敗返回空值
}
//釋放棧內(nèi)存
void SeqStackFree(SeqStack *s)
{
  if(s)
    free(s);
}
//判斷棧的狀態(tài)
int SeqStackIsEmpty(SeqStack *s)                 //判斷棧是否為空
{
  return(s->top == 0);
}
void SeqStackClear(SeqStack *s)               //清空棧
{
  s->top = 0;
}
void SeqStackIsFull(SeqStack *s)      //判斷棧是否已滿
{
  return(s->top == SIZE);
}
//入棧
int SeqStackPush(SeqStack *s, student data)     //入棧操作
{
  if ((s->top+1) > SIZE)
  {
    printf("棧溢出！\n");
    return 0;
  }
  s->data[++s->top] = data;         //將元素入棧
  return 1;
}
//出棧
student SeqStackPop(SeqStack *s)     //出棧操作
{
  if (s->top == 0)
  {
    printf("棧為空！\n");
    exit(0);
  }
  return (s->data[s->top--]);            //彈出棧頂元素
}
//獲取棧頂?shù)脑?br>student SeqStackPeek(SeqStack *s)          //讀取棧頂元素
{
  if (s->top == 0)         //判斷棧是否為空
  {
    printf("棧為空！");
    exit(0);
  }
  return (s->data[s->top]);  //返回棧頂元素

本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點(diǎn)擊一鍵舉報。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來自：荔枝園子 > 《c語言》

舉報/認(rèn)領(lǐng)