---

一、棧

棧是只允許在一端進行插入或刪除操作的線性表。
棧頂：線性表允許進行插入刪除的那一端
棧底：固定的，不允許進行插入和刪除的那一端
空棧：不含如何元素的空表

順序棧

// linear_stack.cpp : This file contains the 'main' function. Program execution begins and ends there.
//#include <iostream>
#include <stdio.h>
#include <stdlib.h>#define Maxsize 50
#define Elemtype int
typedef struct 
{Elemtype data[Maxsize]; //存放棧中元素int top;    //棧頂指針
}SqStack;//初始化棧
void InitStack(SqStack &S)
{S.top = -1;
}//判空
bool StackEmpty(SqStack& S)
{if (S.top == -1){return true;  //判空}else{return false;  //不空}
}//進棧
bool Push(SqStack& S, Elemtype x)
{if (S.top == Maxsize - 1){return false;  //棧滿了}S.data[++S.top] = x;return true;
}//出棧bool Pop(SqStack& S, Elemtype &x)
{if (S.top == -1){return false;  //棧尾了}x = S.data[S.top--];return true;
}//讀棧頂數據
bool GetTop(SqStack& S, Elemtype& x)
{if (S.top == -1){return false;  //棧尾了}x = S.data[S.top];return true;
}int main()
{SqStack S;int x = 0;InitStack(S);Push(S,2);Push(S, 3);Pop(S, x);for (int i = 0; i <= S.top; i++){printf("%d \t", S.data[i]);}
}// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

線性棧(不帶頭結點)

// linear_stack.cpp : This file contains the 'main' function. Program execution begins and ends there.
//#include <iostream>
#include <stdio.h>
#include <stdlib.h>#define Maxsize 50
#define Elemtype int
typedef struct Linknode
{Elemtype data;     //數據域struct Linknode* next;   //指針域
}*LiStack;//初始化棧  不帶頭結點
void InitStack(LiStack & S)
{S = NULL;
}//判空
bool StackEmpty(LiStack& S)
{if (S == NULL){return true;  //判空}else{return false;}
}//進棧
bool Push(LiStack& S, Elemtype x)
{Linknode* p = (Linknode*)malloc(sizeof(Linknode));p->next = NULL;p->data = x;p->next = S;S = p;return true;
}//出棧bool Pop(LiStack& S)
{Linknode* p;if (S == NULL){return false;}p = S;S = S->next;free(p);return true;}//讀棧頂數據
bool GetTop(LiStack& S, Elemtype& x)
{if (S == NULL){return false;}x = S->data;return true;
}int main()
{LiStack S;InitStack(S);int x = 0;Push(S, 2);Push(S, 3);Pop(S);while (S != NULL){printf("%d \t ",S->data);S = S->next;}}// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

線性棧(帶頭結點)

// linear_stack.cpp : This file contains the 'main' function. Program execution begins and ends there.
//#include <iostream>
#include <stdio.h>
#include <stdlib.h>#define Maxsize 50
#define Elemtype int
typedef struct Linknode
{Elemtype data;     //數據域struct Linknode* next;   //指針域
}*LiStack;//初始化棧  帶頭結點
void InitStack(LiStack& S)
{//初始化S = (LiStack)malloc(sizeof(Linknode));S->data = 0;S->next = NULL;
}//判空
bool StackEmpty(LiStack& S)
{if (S->next == NULL){return true;  //判空}else{return false;}
}//進棧
bool Push(LiStack& S, Elemtype x)
{Linknode* p = (Linknode*)malloc(sizeof(Linknode));p->data = x;p->next = S->next;S->next = p;return true;
}//出棧bool Pop(LiStack& S)
{Linknode* p;if (S->next == NULL){return false;}p = S->next;S->next = p->next;free(p);return true;}//讀棧頂數據
bool GetTop(LiStack& S, Elemtype& x)
{if (S->next == NULL){return false;}x = S->next->data;return true;
}int main()
{LiStack S;InitStack(S);int x = 0;Linknode* p;Push(S, 2);Push(S, 3);Pop(S);p = S->next;while (p != NULL){printf("%d \t ", p->data);p = p->next;}}// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

共享棧

#include <cstdio>
#include <stdio.h>
#include <stdlib.h>
#define maxsize 3#define elemtype inttypedef struct
{elemtype data[maxsize];int top[2];
}stk;stk s;int push(int i, elemtype x)
{if (i > 1 || i < 0){printf("棧編號錯誤！\n");exit(0);}if ((s.top[1] - 1) == s.top[0]){printf("棧滿了！");return -1;}switch (i){case 1:s.data[--s.top[1]] = x;break;case 0:s.data[++s.top[0]] = x;break;}//添加成功return 1;}int pop(int i)
{if (i > 1 || i < 0){printf("棧編號錯誤！\n");exit(0);}switch (i){case 1:if (s.top[1] == maxsize){printf("棧底了！\n");exit(0);}elsereturn s.data[s.top[1]++];break;case 0:if (s.top[0] == -1){printf("棧底了！\n");exit(0);}elsereturn s.data[s.top[1]--];break;}//添加成功return 1;}int main()
{s.top[0] = -1;s.top[1] = maxsize;push(0, 2);push(1, 5);push(1, 7);push(1, 9);for (int i = 0; i < maxsize; i++){printf("%d\n", s.data[i]);}return 0;
}