知識星球
（點選上方公眾號，可快速關註）
轉自：jingmoxukong
http://www.cnblogs.com/jingmoxukong/p/3533399.html
棧
棧的基本操作有初始化棧，判棧是否為空，入棧，出棧，獲取棧頂元素。
棧可分為兩種儲存結構：順序棧和鏈棧。
順序棧
順序棧結構：
typedef struct
{
ElemType data[MAXSIZE];
int top;
} SqStack;
順序棧四個要素：
（1）棧空條件：st.top == -1
（2）棧滿條件: st.top == MAXSIZE – 1
（3）進棧條件: st.top++; st.data[st.top] = data;
（4）出棧條件: st.data[st.top] = 0; st.top–;
順序棧基本操作
#include “stdafx.h”
#include
#define MAXSIZE 10
typedef int ElemType;
/* 順序棧結構 */
typedef struct
{
ElemType data[MAXSIZE]; //存放棧中元素
int top; //棧指標
} SqStack;
void InitStack(SqStack &stack;)
{
stack.top = –1;
};
bool IsStackEmpty(SqStack stack)
{
if (–1 == stack.top)
{
return true;
}
return false;
}
int Push(SqStack &stack;, ElemType data)
{
if (MAXSIZE – 1 == stack.top)
{
printf(“stack is full, push failed!\r\n”);
return 1;
}
printf(“Push data : %d\r\n”, data);
stack.top++;
stack.data[stack.top] = data;
return 0;
}
int Pop(SqStack &stack;, ElemType &data;)
{
if (IsStackEmpty(stack))
{
printf(“stack is empty, pop failed!\r\n”);
return 1;
}
data = stack.data[stack.top];
printf(“Pop data : %d\r\n”, data);
stack.data[stack.top] = 0;
stack.top—;
return 0;
}
int GetTop(SqStack stack, ElemType &data;)
{
if (IsStackEmpty(stack))
{
printf(“stack is empty, get top failed!\r\n”);
return 1;
}
data = stack.data[stack.top];
return 0;
}
void PrintStack(SqStack stack)
{
int index = stack.top;
printf(“The element of stack:\r\n”);
while (index >= 0)
{
printf(“%d\t”, stack.data[index]);
index—;
}
printf(“\r\n”);
}
int main()
{
ElemType array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int i = 0;
int data = 0;
SqStack stack = { 0 };
InitStack(stack);
for (i = 0; i < sizeof(array)/sizeof(ElemType); i++)
{
Push(stack, array[i]);
}
PrintStack(stack);
Pop(stack, data);
Pop(stack, data);
GetTop(stack, data);
printf(“Top value : %d\r\n”, data);
PrintStack(stack);
return 0;
}
鏈棧
鏈棧結構：
typedef struct LinkNode
{
ElemType data;
struct LinkNode *next;
} LiStack;
鏈棧四個要素：
（1）棧空條件：NULL == st->next
（2）棧滿條件: 不存在棧滿情況
（3）進棧條件: node->next = st->next; st->next = node;
（4）出棧條件: node = st->next; data = node->data; st->next = node->next; free(node);
鏈棧基本操作
#include “stdafx.h”
#include
typedef int ElemType;
typedef struct LinkNode
{
ElemType data;
struct LinkNode* next;
} STACK;
void InitStack(STACK *&stack;)
{
if (NULL == stack)
{
stack = (STACK *)malloc(sizeof(STACK));
stack->next = NULL;
}
}
bool IsEmpty(STACK *stack)
{
if (NULL == stack->next)
{
return true;
}
return false;
}
void Push(STACK *&stack;, ElemType data)
{
STACK *pNewNode = NULL;
pNewNode = (STACK *)malloc(sizeof(STACK));
pNewNode->data = data;
pNewNode->next = stack->next;
stack->next = pNewNode;
}
void Pop(STACK *&stack;, ElemType &data;)
{
STACK *pTmpNode = NULL;
if (NULL == stack->next)
{
return;
}
pTmpNode = stack->next;
data = pTmpNode->data;
stack->next = pTmpNode->next;
free(pTmpNode);
}
int GetTop(STACK *stack)
{
if (NULL != stack->next)
{
return stack->next->data;
}
return 0;
}
void PrintStack(STACK *stack)
{
STACK *node = stack->next;
while (NULL != node)
{
printf(“%d\t”, node->data);
node = node->next;
}
printf(“\r\n”);
}
int _tmain(int argc, _TCHAR* argv[])
{
ElemType array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int i = 0;
int x = 0;
STACK *stack = NULL;
InitStack(stack);
for (i = 0; i < sizeof(array)/sizeof(ElemType); i++)
{
Push(stack, array[i]);
}
PrintStack(stack);
Pop(stack, x);
Pop(stack, x);
PrintStack(stack);
}
覺得本文有幫助？請分享給更多人
關註「演演算法愛好者」，修煉程式設計內功
