棧

棧的基本操作有初始化棧，判棧是否為空，入棧，出棧，擷取棧頂元素。

棧可分為兩種存儲結構：順序棧和鍊棧。

順序棧

順序棧結構：

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 <stdlib.h>

#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;
}      

View Code

鍊棧

鍊棧結構：

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 <stdlib.h>

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);
}