棧的多種C語言實現

標題：棧的多種C語言實現

內容：棧是一種後進先出（LIFO）的數據結構，C語言中可以使用數組、全局變量、指針傳參、引用傳參等方法實現。

作者：MilkCu

概念

棧的定義

我們可以使用下面的結構體來定義棧：

typedef struct stack {
 int top;
 int key[M];
} stack;

棧的屬性

以棧s為例討論。

s.top指向最新插入的元素。
當棧中包含的元素為s.key[1..s.top]，其中s.key[1]是棧底元素，s.key[s.top]是棧頂元素。

棧的操作

壓入（push）：將數據放在棧頂；

彈出（pop）：返回彈出值，並刪除元素。

棧的狀態

s.top = 0時，棧中不包含任何元素，即棧是空的。

實現

普通數組實現

最簡單的實現方法，不會涉及到結構體的參數傳遞問題。

使用s[0]表示s.top。

# include <stdio.h>
# define M 100
int stackEmpty(int s[]);
void push(int s[], int x);
int pop(int s[]);
int main(void)
{
 int s[M];
 s[0] = 0;
 printf("stackEmpty - %d\n", stackEmpty(s));
 push(s, 2);
 push(s, 5);
 printf("stackEmpty - %d\n", stackEmpty(s));
 printf("pop - %d\n", pop(s));
 return 0;
}
int stackEmpty(int s[])
{
 if(s[0] == 0) {
  return 1;
 } else {
  return 0;
 }
}
void push(int s[], int x)
{
 s[0]++;
 s[s[0]] = x;
}
int pop(int s[])
{
 if(s[0] == 0) {
  return -1;
 } else {
  return s[s[0]--];
 }
}

指針傳參實現

傳遞參數的時候要用指針，否則不能改變參數的值！

# include <stdio.h>
# define M 100
typedef struct stack {
 int top;
 int key[M];
} stack;
int stackEmpty(stack s);
void push(stack * s, int x);
int pop(stack * s);
int main(void)
{
 stack s;
 s.top = 0;
 /* 測試代碼 */
 push(&s, 2);
 push(&s, 3);
 printf("pop - %d\n", pop(&s));
 printf("stackEmpty - %d", stackEmpty(s));
}
int stackEmpty(stack s)
{
 if(s.top == 0) {
  return 1;
 } else {
  return 0;
 }
}
void push(stack * sp, int x)
{
 sp -> top += 1;
 sp -> key[sp -> top] = x;
}
int pop(stack * sp)
{
 if(sp -> top == 0) {
  return -1;
 } else {
  sp -> top--;
  return sp -> key[sp -> top + 1];
 }
}